匈牙利算法-从中选择0的最后一步，使得每一行和每一列仅选择一个

Question

我正在尝试在Java中实现匈牙利算法。我有一个NxN成本矩阵。我正在逐步遵循本指南，并已达到第9步-

“通过选择一组零来选择匹配项，以便每一行或每一列都只有一个被选择。”

我已经有了0的矩阵。我试图弄清楚这一点，对我有用的唯一方法是蛮力方法。

我还想到选择遇到的第一个0，删除该列和行并重复；但是这种方法不起作用。

有什么技巧或方法吗？不太复杂的东西吗？任何建议将不胜感激。

谢谢

Answer 1

匈牙利人的回答：:)

• 0计算每行和每列的元素数量。（称之为row[]和column[]）
• 选择行和列的最小正值。例如，顺其自然column[3]（如果在 a 中找到最小值row，则同样适用，仅交换行和列）如果有多个具有相同值的值，请选择任意一个。
• 选择0该列中的一个元素，对其进行标记。如果有多个，请选择具有正值的任何一个row。（假设是row[1]）
• 设置column[3]为 0（下次我们不应该选择）。也设置row[1]为0。
• 迭代 中的所有元素column[3]，如果找到一个0元素，则对应的row[i]值减1
• 如果您在行或列中都没有找到正值，那么您就完成了。