6

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

4

2 回答 2

3

虚拟值应全部为零。关键是你选择哪一个并不重要，你最终会忽略那些选择，因为它们不在原始数据中。通过使它们为零（在开始时），您的算法将不必费力地找到您不会使用的值。

于 2018-07-07T14:06:54.763 回答
1

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

于 2019-05-24T09:02:48.657 回答