匈牙利算法在非方阵矩阵中的应用

Question

匈牙利算法在非方阵矩阵中的应用

7

我正在尝试实现匈牙利算法。当矩阵不是方阵时，一切都很好，除了这一点。我查找的所有方法都说我应该通过添加虚拟行/列来使其成为方阵，并用矩阵中的最大数填充虚拟行/列。我的问题是，这样做不会影响最终结果吗？难道虚拟行/列填充的数字不应该至少为 max+1 吗？

- Sarah K

我同意您的评估。我总是使用max+1。 - mikeTronix

2

我应该指出，这完全取决于您是设置最小化成本还是最大化吞吐量。在后一种情况下，将这些额外的行/列设置为零，正如Yay295所建议的那样。 - mikeTronix

如果任何权重为负数，则零在最大化情况下不起作用。 - fuglede

2

需要注意的是，如果您关心性能，添加虚拟变量的方法通常会比使用专门针对非方阵情况的算法增加解决问题所需的时间。例如，可以参考Bijsterbosch、Volgenant的论文《解决矩形分配问题及其应用》（2010年，《运筹学报告》181(1)：443-462）。DOI: 10.1007/s10479-010-0757-3。 - fuglede

2个回答

2

匈牙利算法的主要思想建立在这样一个事实之上："如果从矩阵的任一行或列的所有条目中添加/减去一个数字，则作业的最佳分配保持不变"。因此，使用虚拟值作为“max、max+1或0”并不重要。它可以设置为任何数字，最好是0（正如 Yay295 所说，如果条目已经为0，该算法将更愿意工作）。

- IY4

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yay295 · Accepted Answer

所有的虚拟值都应该为零。这个意思是无论你选择哪一个，最终你都会忽略那些选择，因为它们不在原始数据中。通过在开始时将它们设为零，你的算法就不必费力去找一个你不会使用的值。