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

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

该问题在运营管理中被称为分配问题，可以通过匈牙利算法有效解决。在您的情况下，距离可以被视为一种“成本”函数，它将在其总数中最小化。

幸运的是，scipy已经实现了一个很好的linear_sum_assignment()（请参阅官方文档和示例），因此您不必重新发明轮子。该函数返回匹配的索引。

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])