Pythonの2つの点セット間の合計距離を最小にする

Question

n次元空間に2セットの点がある場合、各点が1回だけ使用され、ポイントのペアは最小化されていますか？例えば

、

import matplotlib.pyplot as plt 
import numpy as np 

# create six points in 2d space; the first three belong to set "A" and the 
# second three belong to set "B" 
x = [1, 2, 3, 1.8, 1.9, 3.4] 
y = [2, 3, 1, 2.6, 3.4, 0.4] 

colors = ['red'] * 3 + ['blue'] * 3 

plt.scatter(x, y, c=colors) 
plt.show() 

そこで、上記の例では、目標は、各青色点は一度だけ使用され、合計されるように、青い点にそれぞれ赤色点をマッピングすることであろうポイント間の距離の最小化が図られる。ポイントのすべてのペアscipy.spatial.distance.cdist()機能を使用して間セット間の距離を計算 -

は、私は、問題の最初の部分を解決するために役立ちます this questionに出くわしました。

そこから、おそらく各行の単一要素のすべての置換をテストし、最小値を見つけることができます。

私が気にしているアプリケーションは、3次元空間のデータポイントの数がかなり少ないため、ブルートフォースのアプローチはうまくいくかもしれませんが、誰かがより効率的で洗練されたソリューションを知っているかどうかを確認します最初。

Answer 1

における実装を見つけることができます。

import numpy as np 
import matplotlib.pyplot as plt 
from scipy.spatial.distance import cdist 
from scipy.optimize import linear_sum_assignment 

np.random.seed(100) 

points1 = np.array([(x, y) for x in np.linspace(-1,1,7) for y in np.linspace(-1,1,7)]) 
N = points1.shape[0] 
points2 = 2*np.random.rand(N,2)-1 

C = cdist(points1, points2) 

_, assigment = linear_sum_assignment(C) 

plt.plot(points1[:,0], points1[:,1],'bo', markersize = 10) 
plt.plot(points2[:,0], points2[:,1],'rs', markersize = 7) 
for p in range(N): 
    plt.plot([points1[p,0], points2[assigment[p],0]], [points1[p,1], points2[assigment[p],1]], 'k') 
plt.xlim(-1.1,1.1) 
plt.ylim(-1.1,1.1) 
plt.axes().set_aspect('equal') 

Answer 2

あり、このために知られているアルゴリズムは、だThe Hungarian Method For Assignment、O（nは）時間で動作しています。

はscipyのダウンロードでは、和のユークリッド距離が最小となるように、点の別のセットの要素を指しに一組の（マッピング）要素を割り当てる例scipy.optimize.linear_sum_assignment