匈牙利算法 - 從這樣選擇0的最後一步，即每行和每列只有一個被選中

Question

我試圖在Java中實現匈牙利算法。我有一個NxN成本矩陣。我下面一步this引導臺階，並已達到第9步 -

「通過選擇一組零的選擇匹配，使得每行或列 只有一個選擇。」

我已經有了0的矩陣。 我想弄明白這一點，唯一對我有用的東西就是蠻力方法。

我也想過選擇我遇到的第一個0，刪除那一列&行並重復;但是這種方法不起作用。

有什麼技巧或方法嗎？一些不太複雜的東西？任何建議，將不勝感激。

由於

Answer 1

從匈牙利的答案：:)

• 計算0元件爲每個行和列的數量。 （稱爲row[]和column[]）
• 選擇最小值正數行和列的值。例如，假設它是column[3]（如果在row中找到最小值，則同樣適用，僅交換行和列）如果具有多個具有相同值的值，請選擇任意值。
• 在該列中選擇一個0元素，標記它。如果您有多個，請選擇任意一個。
• 設置column[3]爲0（下次不選擇）
• 迭代在column[3]的所有元素，如果你找到一個0元素，由1
• 降低相應的row[i]值。如果你沒有找到一個積極的在行或列中都沒有值，你就完成了。