5

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

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

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

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

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

谢谢

4

1 回答 1

3

匈牙利人的回答：:)

  • 计算0每行和每列的元素数。（调用它row[]和column[]）
  • 选择行和列的最小正值。例如，让它成为column[3]（如果在 a 中找到最小值row，同样适用，仅交换行和列）如果您有多个具有相同值的值，请选择任何一个。
  • 0在该列中选择一个元素，标记它。如果您有多个，请选择具有正值的任何一个row。（假设是row[1]）
  • 设置column[3]为 0（下次我们不应该选择）。也设置row[1]为 0。
  • 迭代 中的所有元素column[3]，如果找到一个0元素，则将对应的值减row[i]1
  • 如果您在行或列中都没有找到正值，那么您就完成了。
于 2013-03-03T23:10:20.120 回答