5

Javaでハンガリーのアルゴリズムを実装しようとしています。NxNコストマトリックスがあります。私はこのガイドを段階的にたどっていて、ステップ9に到達しました-

「各行または列で1つだけが選択されるように、ゼロのセットを選択して一致するものを選択してください。」

私はすでに0の行列を持っています。私はこれを理解しようとしていましたが、私のために働いていたのはブルートフォース方式だけでした。

また、最初に遭遇した0を選択し、その列と行を削除して繰り返します。ただし、この方法は機能しません。

トリックや方法はありますか？それほど複雑ではないものはありますか？任意の提案をいただければ幸いです。

ありがとう

4

1 に答える 1

3

ハンガリー語からの回答::)

  • 0各行と列の要素数を計算します。row[]（それを呼び出してcolumn[]）
  • 行と列の最小の正の値を選択します。たとえば、次のようにしますcolumn[3]（最小値がに見つかったrow場合、同じことが適用され、行と列のみがスワップされます）同じ値を持つものが複数ある場合は、いずれかを選択します。
  • その列の要素を選択し0、マークを付けます。複数ある場合は、正のrow値を持つものを選択してください。（それがであると仮定しますrow[1]）
  • 0に設定column[3]します（次回は選択しないでください）。またrow[1]、0に設定します。
  • のすべての要素を繰り返し、要素column[3]が見つかった場合は0、対応するrow[i]値を1つ減らします。
  • 行にも列にも正の値が見つからない場合は、終了です。
于 2013-03-03T23:10:20.120 に答える