python - 最小化相互不相交的二分对之间的距离总和

Question

我有一个多维数组，它表示两组点之间的距离(分别用蓝色和红色表示)。

import numpy as np
distance=np.array([[30,18,51,55],
                   [35,15,50,49],
                   [36,17,40,32],
                   [40,29,29,17]])

每列代表红点，行代表蓝点。该矩阵中的值表示红点和蓝点之间的距离。这是一个草图，可以帮助您了解它的样子:

问题:如何找到相互不相交(蓝色、红色)对之间距离总和的最小值？

尝试

我期望在上图中找到 1=1、2=2、3=3 和 4=4。但是，如果我使用简单的 argmin numpy 函数，例如:

for liste in distance:
    np.argmin(liste)

结果是

1
1
1
3

因为 2 个红点是 1,2 和 3 个蓝点中最近的。

在这种情况下有没有办法做一些通用的事情来让事情变得更好？我的意思是不使用大量 if 语句和 while 函数。

Answer 1

该问题被称为 assignment problem在运营管理中，可以通过Hungarian Algorithm高效解决。在您的情况下，距离可以被视为一种“成本”函数，其总数将被最小化。

幸运的是，scipy 实现了一个很好的 linear_sum_assignment() (参见 official docs and example )，因此您不必重新发明轮子。该函数返回匹配的索引。

from scipy.optimize import linear_sum_assignment
distance=np.array([[30,18,51,55],
                   [35,15,50,49],
                   [36,17,40,32],
                   [40,29,29,17]])

row_ind, col_ind = linear_sum_assignment(distance)

# result
col_ind
Out[79]: array([0, 1, 2, 3])
row_ind
Out[80]: array([0, 1, 2, 3])