findet die minimale Summe der Matrix (n x n), der nur eine in jeder Zeile und Spalte auszuwählen

Question

Dies ist ein weiteres Algorithmen Problem dynamische Programmierung im Zusammenhang

Hier ist das Problem:

finden, die minimale Summe der gegebenen Matrix, so dass eine Auswahl in jeder Zeile und Spalte

Zum Beispiel:

3 4 2

8 9 1

7 9 5

das Minimum: 4 + 1 + 7

ich glaube, die Lösung ist Netzwerk-Flow (max Fluss / min geschnitten), aber ich denke, es ist nicht so schwer sein sollte, wie es ist

Meine Lösung: seperate n Liste [Spalte], column1, column2 ... Spalte n

dann Punkt beginnen (S) -> column1 -> column2 -> ... -> Spalte n -> (E) Endpunkt und implementieren max Fluss / min Schnitt

Answer 1

This is the Assignment Problem which can be considered a special case of minimum weight perfect matching in graphs. The classic way to solve the Assignment Problem is to use the Hungarian Algorithm.