Wie man Zahlen in einer Matrix hinzufügt, um ein minimales Ergebnis zu erzielen? - C ++, Algorithmus, Matrix

Dies ist eher ein algorithmisches / mathematisches Problem, aber ich hoffe, eine Lösung in C ++ zu implementieren.

Angenommen, ich habe eine Matrix wie folgt, in der die Punkte ganze Zahlen darstellen:

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

Wie würde ich das Mindestergebnis erzielen, wenn ich aus jeder Spalte eine Zahl auswählen müsste, so dass aus jeder Reihe höchstens eine Zahl besteht?

Zum Beispiel könnte ich wählen AW BX CY DZ oder AZ BX CY DW aber nicht AW BW CZ DZ

Der Brute-Force-Ansatz scheint n zu nehmen! Berechnungen. Gibt es einen schnelleren Weg? Schließlich möchte ich Zahlen in Matrizen der Größe ~ 60 hinzufügen.

Außerdem liegen alle Zahlen zwischen 0 und 256.

Antworten:

Und wenn Sie es nicht selbst programmieren, Sie"Harte Arbeit und nette Publikation" könnte jemand anderes verwenden. Dieses in Haskell, löst eine 60x60 zufällige Matrix in weniger als zwei Zehntel einer Sekunde auf meinem alten Laptop. Was für ein großartiger Algorithmus!

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

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