python - 给定一个矩阵，如何在不重复的情况下为每一行找到最佳单元格

Question

我有一个矩阵，行是对象，列是目标，每一行代表一个对象到一个目标的距离。

例如，假设我有 3 个对象 O1 O2 O3 和 3 个目标，OA OB OC，矩阵将类似于

   | OA OB OC
-------------
O1 | 2  4  6
O2 | 1  2  8
O3 | 3  5  3

我只是用随机数据填充它，可能没有意义，但它可能对问题有用。

我期望的输出是：O2-OA、O1-OB 和 O3-OC

所以虽然OA是O1的承载目标，但由于OA已经被OA使用，它转到下一个。

Answer 1

这是线性分配问题的一个例子。

使用Hungarian Algorithm可以在 O(N^3) 时间内找到最佳解决方案，这里有一个不错的 Python 实现以及更多信息。

如果您想了解匈牙利算法的工作原理 -这个讲座绝对值得一看。

如果速度很重要，那么一种可以快速返回最优解的方法（尽管-据我所知-不能保证这样做）是所谓的Softassign 算法，它与Simulated Annealing相关，涉及迭代行和列成本矩阵的归一化。

最后，当然可以使用贪婪方法以次优方式快速解决这个问题，其中按顺序选择最佳匹配，直到完成所有分配。