python - 如果其中一项分配必须具有无穷大的成本，为什么 scipy.optimize 中的 linear_sum_assignment 永远不会返回？

使用 scipy.optimize.linear_sum_assignment 时，如果二部图的成本矩阵的设置方式使得其中一个分配必须具有无穷大的成本，则算法将永远不会返回，并永远卡在那里。

在以下示例中，第一组中的第二个顶点将始终具有无穷大的成本，无论它与第二组中的哪个顶点匹配。这将导致程序挂起并且永远不会打印任何内容。

cost = np.array([[np.inf, np.inf, 4],
                 [np.inf, np.inf, np.inf],
                 [np.inf, 4, np.inf]])
row_ind, col_ind = linear_sum_assignment(cost)
print(cost)
print(col_ind)
print(cost[row_ind, col_ind].sum())

然而，我希望我们仍然能够找到一个任务。例如，第一组中的第二个顶点仍然可以与第二组中的第一个顶点匹配。然后我们会有一个 col_ind 的 [2 0 1] 和一个无穷大的分配总成本。

我的问题是，为什么会发生这种情况，我该如何防止这种情况发生并确保 linear_sum_assignment 始终返回？或者，有没有办法检测到这种情况会发生，而根本不运行 linear_sum_assignment ？或者有其他解决方法吗？

我还想指出，以下成本矩阵也会导致程序不打印任何内容，因此仅确保每一行至少有 1 个非无限成本是不够的。

cost = np.array([[np.inf, np.inf, 4],
                 [np.inf, 4, np.inf],
                 [np.inf, 4, np.inf]])

最后，下面的成本矩阵很好

cost = np.array([[np.inf, np.inf, 4],
                 [4, np.inf, np.inf],
                 [np.inf, 4, np.inf]])

并导致以下输出。

[[ inf  inf   4.]
 [  4.  inf  inf]
 [ inf   4.  inf]]
[2 0 1]
12.0

我不相信这是特定于版本的，但如果是，我正在运行 Python 3.5.2::Anaconda 4.2.0。

最佳答案

这是当前 scipy.optimize.linear_sum_assignment 中的 bug 。

如果使用无穷大不是绝对必要的，临时解决方法可能是避免使用无穷大的值，而是使用非常大的数字。小于无穷大的非常大的数字按预期工作。

关于python - 如果其中一项分配必须具有无穷大的成本，为什么 scipy.optimize 中的 linear_sum_assignment 永远不会返回？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42035999/