我有一个与此类似的问题：匈牙利算法-系统地分配。他提出了一种可能有效的解决方案，但似乎并不完全合理。是否有一种确定哪组0将是可行解的可靠动态算法？（即每行和每列只有一个0）。请参见步骤9：http://www.wikihow.com/Use-the-Hungarian-Algorithm。如何实现一个执行该任务的算法？谢谢！
1个回答
1
基本上，你可以将n * n矩阵看作表示二分图。行表示图左侧的顶点，列表示图右侧的顶点。在第i行、第j列中的零意味着左侧顶点i和右侧顶点j之间存在一条边。
你想找到一个完全二分匹配，即一组没有公共顶点的n个边。为此，你可以使用你喜欢的匹配算法，例如Hopcroft-Karp算法。
一旦你找到了匹配，选择与匹配中的边对应的零。匹配属性保证在每行/列中不会有超过一个被选中的零。
你想找到一个完全二分匹配，即一组没有公共顶点的n个边。为此，你可以使用你喜欢的匹配算法，例如Hopcroft-Karp算法。
一旦你找到了匹配，选择与匹配中的边对应的零。匹配属性保证在每行/列中不会有超过一个被选中的零。
- us2012
1
这是我唯一行之有效的方法 - 贪心算法似乎在你用它们处理成千上万个随机矩阵时都能正常工作，但总会有一些例子不起作用。 - Eric Ferreira
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接