graph-theory - 二部最小エッジ

Question

二部グラフのエッジの中で最小の加重エッジを取得する単純なアルゴリズムを探しています。私が検索したところ、2部グラフがあり、各エッジに数の重みがあり、それらの中で最小の数を取得する方法がある場合、2部のカバーエッジを意味することをすべて知ることができました

Answer 1

この質問の提起方法は、非常に不明確です。私が得た解釈の 1 つは、「加重二部グラフ G が与えられた場合、G の最小エッジ カバーを取得するにはどうすればよいか?」というものでした。その場合、ハンガリーのアルゴリズム( http://reference.wolfram.com/mathematica/ref/FindEdgeCover.htmlも参照) が問題を解決します。

Answer 2

ハンガリーのアルゴリズムが必要です。 講義ノートを入手するには、ここをクリックしてください。

処理する前に、各エントリがノード A からノード B へのエッジ コストであるコスト マトリックスが必要です。マッチングの手順は次のとおりです。

---

1. 各行の最小エントリを減算します
2. 各列の最小エントリを減算します
3. コスト マトリックスのすべてのゼロ エントリがカバーされ、そのような行の最小数が使用されるように、適切な行と列に線を引きます。
4. 最適なテスト: (1) カバーする行の最小数が n の場合、最適な割り当てが可能であり、終了します。(2) カバーする行の最小数が n 未満の場合、ゼロの最適な割り当てはまだ可能ではありません。ステップ 5 に進みます。
5. どの行にも含まれていない最小のエントリを決定します。カバーされていない各行からエントリを減算し、カバーされている各列に追加します。手順 3 に戻ります。

---

上記のアルゴリズムは、次の数学定理に基づいています。

• コスト マトリックスの任意の 1 行または 1 列のすべてのエントリに対して数値が加算または減算される場合、結果のコスト マトリックスの最適な割り当ては、元のコスト マトリックスの最適な割り当てでもあります。

Answer 3

他の回答で示唆されているように、ハンガリーのアルゴリズムよりもさらに優れているのは、Jonker-Volgenant ( LAPJV ) アルゴリズムです。

Bipartite Solverという適切な名前のこの GitHub リポジトリを見てください。これは基本的に、コードで LAPJV を実装する方法に関するチュートリアルであり、実行可能なグラフィカル サンプルを完備しています。

非常に高速で、1000 から 1000 を 1 秒以内に実行できます。

ライブラリには欲張り検索も含まれており、これはさらに高速ですが、最適性を保証するものではありません。

ソースからビルドせずにアルゴリズムを試してみたい場合は、ライブラリにいくつかの実行可能ファイルもあります。