algorithm - 匈牙利算法选择 0

Question

我有一个与此处发现的问题非常相似的问题：

匈牙利算法 - 系统分配

他提出了一个可能有效也可能无效的解决方案……但它在逻辑上似乎并不完全合理。

是否有一个万无一失的动态算法来确定哪一组 0 将是一个可行的解决方案？（表示每行每列只有一个 0）

请参阅第 9 步：http: //www.wikihow.com/Use-the-Hungarian-Algorithm

如何实现一种算法来执行该任务？

谢谢！

Answer 1

本质上，您可以将 n*n 矩阵视为表示二分图。行表示图左侧的顶点，列表示图右侧的顶点。第 i 行中的零，col j 表示左侧的顶点 i 和右侧的顶点 j 之间有一条边。

您想找到一个完整的二分匹配，即一组没有公共顶点的 n 边。为此，您可以使用您最喜欢的匹配算法，例如 Hopcroft-Karp。

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