匈牙利算法选择0
匈牙利算法选择0
提问于 2013-03-01 15:11:55
我有一个与这里非常相似的问题：
Hungarian algorithm - assign systematically
他提出了一个可能或不可行的解决方案。但从逻辑上讲，这似乎并不完全合理。
有没有一种可靠的动态算法来确定哪组0将是可行的解决方案？(表示每行和每列只有一个0)
请参阅上的步骤9：http://www.wikihow.com/Use-the-Hungarian-Algorithm
如何实现算法来执行该任务？
谢谢!
回答 1
Stack Overflow用户
发布于 2013-03-01 16:09:19
从本质上讲，您可以将n*n矩阵视为表示二部图。行表示图左侧的顶点，列表示右侧的顶点。行i，列j中的零表示在左侧的顶点i和右侧的vetex j之间有一条边。
您希望找到一个完全的二部匹配，即没有公共顶点的n条边的集合。为此，您可以使用您喜欢的匹配算法，例如Hopcroft-Karp。
找到匹配后，选择与匹配中的边相对应的零。matching属性保证每行/每列中不超过一个选定的零。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15152476
复制相关文章
相似问题
腾讯云开发者
