匈牙利算法選擇0

Question

我有非常相似的一個問題在這裏找到：

Hungarian algorithm - assign systematically

他建議可能會或可能無法正常工作的解決方案...但它並不完全似乎邏輯聽起來。

是否有確定的動態算法來確定哪一組0將是一個可行的解決方案？ （意味着每行每列僅包括一個0）

參見第9步：http://www.wikihow.com/Use-the-Hungarian-Algorithm

一個將如何實現的算法來執行這項任務？

謝謝！

Answer 1

本質上，您可以將n * n矩陣看作是代表雙向圖。行表示圖的左側部分的頂點，列表示右側部分的頂點。行i中的零點col j表示在左側的頂點i和右側的vetex j之間存在邊緣。

您想要找到一個完整的二部分匹配，即一組沒有公共頂點的n個邊。爲此，您可以使用您最喜歡的匹配算法，例如Hopcroft-Karp。

找到匹配項後，選擇與匹配中的邊相對應的零。匹配屬性保證每行/列中不多於一個選定的零。