algorithm - 0 を選択するハンガリーのアルゴリズム

Question

ここにあるものと非常によく似た質問があります。

ハンガリーのアルゴリズム - 体系的に割り当てる

彼は、うまくいくかもしれないしうまくいかないかもしれない解決策を提案しました...しかし、それは論理的に正しいとは思えません。

どの0のセットが実行可能なソリューションになるかを判断するために使用する確実な動的アルゴリズムはありますか? (つまり、行ごとおよび列ごとに 1 つの 0 のみを意味します)

次の手順 9 を参照してください: http://www.wikihow.com/Use-the-Hungarian-Algorithm

そのタスクを実行するアルゴリズムをどのように実装しますか?

ありがとう！

Answer 1

基本的に、n*n 行列は 2 部グラフを表すものと見なすことができます。行はグラフの左側の頂点を表し、列は右側の頂点を表します。行 i、列 j のゼロは、左側の頂点 i と右側の頂点 j の間にエッジがあることを意味します。

共通の頂点を持たない n 個のエッジのセットである完全な二部一致を見つけたいとします。これには、Hopcroft-Karp などのお気に入りのマッチング アルゴリズムを使用できます。

一致が見つかったら、一致のエッジに対応するゼロを選択します。一致するプロパティは、各行/列に複数の選択されたゼロがないことを保証します。