匈牙利算法选择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。

找到匹配项后，选择与匹配中的边相对应的零。匹配属性保证每行/列中不多于一个选定的零。