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

Question

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

例如，假设我有3个对象，o1o2，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

这是Linear Assignment问题的一个例子。在

使用Hungarian Algorithm可以在O（N^3）时间内找到一个最佳解决方案，其中有一个不错的Python实现，其中包含更多信息here。在

如果你想了解匈牙利算法是如何工作的-this lecture绝对值得一看。在

如果速度很重要，那么一种可以快速返回最优解的方法是所谓的Softassign algorithm，它与Simulated Annealing相关，涉及成本矩阵的迭代行和列规范化。在

最后，当然可以用一种贪婪的方法以次优的方式快速解决这个问题，在这种方法中，最好的匹配是按顺序选择的，直到所有的赋值都完成。在