0

Hungarian Algorithm の実装を見つけましたが、「スター付きゼロ」と「プライミング ゼロ」の意味について質問があります。これは、マークされたゼロを指すために使用されていると思いますが、よくわかりません。それが正しいか？

これはコードです: http://ccp.uchicago.edu/khetarpal/code/edit-distance/HungarianAlgorithm.java

ありがとう。

4

1 に答える 1

4

ご存じのとおり、ハンガリー語 (または Kuhn-Munkres) アルゴリズムは、割り当て問題を解決する組み合わせ最適化アルゴリズムです。これは、正方行列に適用される一連の操作で構成されます。そのセルの値は、「タスク」i を「ワーカー」j に割り当てるコスト、または「ワーカー」i を「タスク」j に割り当てるコストの関数です。i と j はそれぞれ行番号と列番号です。ここでは、使用している実装の簡単な説明を含めて、セル (またはゼロ) をスターリングおよびプライミングする目的を理解できるようにします。

ステップ 0 : 各要素がワーカーの 1 つをジョブの 1 つに割り当てるコストを表すコスト マトリックスと呼ばれるマトリックスを作成します。ステップ1へ

ステップ 1 ( reduceMatrix ): 各行について、最小の要素を見つけて、その行のすべての要素から減算します。ステップ 2に進みます。

ステップ 2 ( initStars ): 結果の行列でゼロ (Z) を見つけます。その行または列にスター付きゼロがない場合は、スター Z. 行列の各要素に対して繰り返します。ステップ 3に進みます。

ステップ 3 ( coverColumnsOfStarredZeroes ): スター付きゼロを含む各列をカバーします。K 列がカバーされている場合、星付きのゼロは、一意の割り当ての完全なセットを表します。この場合はDONEに進み、それ以外の場合はStep 4に進みます。

ステップ 4 ( primeSomeUncoveredZero ): カバーされていないゼロを見つけて素数にします。このプライム付きゼロを含む行にスター付きゼロがない場合は、手順 5に進みます。それ以外の場合は、この行をカバーし、スター付きのゼロを含む列を明らかにします。カバーされていないゼロがなくなるまで、この方法を続けます。カバーされていない最小値を保存し、ステップ 6に進みます。

ステップ 5 ( incrementSetOfStarredZeroes ): 次のように、一連のプライム付きゼロとスター付きゼロを交互に構築します。Z0 は、ステップ 4 で見つかったカバーされていないプライミングされたゼロを表します。Z1 は、Z0 の列のスター付きゼロを示します (存在する場合)。Z2 が Z1 の行のプライミングされたゼロを表すとします (常に 1 つ存在します)。シリーズが、その列にスター付きのゼロがないプライミングされたゼロで終了するまで続行します。シリーズの各スター付きゼロのスターを外し、シリーズの各プライミング ゼロのスターを付け、すべての素数を消去し、マトリックス内のすべての行を明らかにします。ステップ 3に戻ります。

ステップ 6 ( makeMoreZeroes ): ステップ 4 で見つかった値を、カバーされた各行のすべての要素に追加し、カバーされていない各列のすべての要素から減算します。星、素数、またはカバーされた線を変更せずに、手順 4に戻ります。

DONE : 割り当てペアは、コスト マトリックス内の星印の付いたゼロの位置によって示されます。C(i,j) がスター付きゼロの場合、行 i に関連付けられた要素が列 j に関連付けられた要素に割り当てられます。

お役に立てれば。

于 2014-05-05T06:23:33.397 に答える