非平方矩阵的匈牙利算法 [英] Hungarian Algorithm for non square matrix

问题描述

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

I'm trying to implement the Hungarian algorithm. Everything is fine except for when the matrix isn't square. All the methods I've searched are saying that I should make it square by adding dummy rows/columns, and filling the dummy row/column with the maximum number in the matrix. My question is that won't this affect the final result? Shouldn't the dummy row/column be filled with at least max+1?

推荐答案

伪值都应为零.关键是选择哪一个都无关紧要，最终您将忽略这些选择，因为它们不在原始数据中.通过将它们设置为零(开始时)，您的算法将不必费劲地寻找不使用的值.

The dummy values should all be zero. The point is that it doesn't matter which one you choose, you're going to ignore those choices in the end because they weren't in the original data. By making them zero (at the start), your algorithm won't have to work as hard to find a value you're not going to use.

这篇关于非平方矩阵的匈牙利算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！