10

これはアルゴリズム/数学の問題ですが、C++ で解決策を実装したいと考えています。

ドットが整数を表すような行列があるとします。

   W  X  Y  Z
A  .  .  .  . 
B  .  .  .  .
C  .  .  .  .
D  .  .  .  .

各行から最大で 1 つの数値が存在するように、各列から 1 つの数値を選択する必要がある場合、最小の結果を得るにはどうすればよいでしょうか?

たとえば、私はAW BX CY DZ or を選択できますが、そうではありAZ BX CY DW ませんAW BW CZ DZ

ブルート フォース アプローチは n! 計算。より速い方法はありますか？最終的に、サイズが ~60 の行列に数値を追加したいと思います。

また、すべての数値の範囲は 0 ～ 256 です。

4

1 に答える 1

1

また、自分でコーディングしたくない場合は、他の誰かの勤勉で親切な出版物をいつでも使用できます。Haskell のこれは、私の古いラップトップで 10 分の 2 秒未満で 60x60 のランダム行列を解決します。なんて素晴らしいアルゴリズムでしょう！

import Data.Algorithm.Munkres
import Data.Array.Unboxed
import Data.List (transpose)

solve n matrix = 
  hungarianMethodInt (listArray ((1,1),(n,n)) $ concat $ transpose matrix)
于 2013-07-04T05:32:36.353 に答える