マトリックスに数値を追加して最小結果を得るにはどうすればよいですか？

Question

これはアルゴリズム的/数学的な問題ですが、私はC++でソリューションを実装したいと考えています。

は、私はドットが整数を表すので、どこのような行列があるとします。

私はから最大1つの番号が存在するように、各列から数字を1つ選ぶとした場合、私は最低限の結果をもたらすであろうどのように

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

各列？例えば

、私はAW BX CY DZまたはAZ BX CY DWではなくAW BW CZ DZ

を選ぶことができるブルートフォースアプローチは、nを取るように見えるでしょう！計算。より速い方法がありますか？最終的にはサイズ〜60の行列に数値を追加したいと思います。

また、すべての数値は0から256

Answer 1

の範囲であり、あなたは、むしろそれを自分でコーディングしたくない場合、あなたは常に他人のハードワークと種類の出版物を使用することができます。ハスケルのこの1つは、古いラップトップで2秒未満で60×60のランダムマトリックスを解きます。どのような素晴らしいアルゴリズム！

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

solve n matrix = 
    hungarianMethodInt (listArray ((1,1),(n,n)) $ concat $ transpose matrix)