最小化Python中两组点之间的总距离 [英] Minimize total distance between two sets of points in Python

问题描述

给定 n 维空间中的两组点，如何将一个点从一组映射到另一组，使得每个点只使用一次并且点对之间的总欧氏距离最小?

例如

将 matplotlib.pyplot 导入为 plt将 numpy 导入为 np# 在二维空间中创建六个点；前三个属于集合A"，而# 第二个三个属于集合B"x = [1, 2, 3, 1.8, 1.9, 3.4]y = [2, 3, 1, 2.6, 3.4, 0.4]颜色 = ['红色'] * 3 + ['蓝色'] * 3plt.scatter(x, y, c=colors)plt.show()

所以在上面的例子中，目标是将每个红点映射到一个蓝点，这样每个蓝点只使用一次，并且点之间的距离总和最小.

我遇到了

Given two sets of points in n-dimensional space, how can one map points from one set to the other, such that each point is only used once and the total euclidean distance between the pairs of points is minimized?

For example,

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

So in the example above, the goal would be to map each red point to a blue point such that each blue point is only used once and the sum of the distances between points is minimized.

I came across this question which helps to solve the first part of the problem -- computing the distances between all pairs of points across sets using the scipy.spatial.distance.cdist() function.

From there, I could probably test every permutation of single elements from each row, and find the minimum.

The application I have in mind involves a fairly small number of datapoints in 3-dimensional space, so the brute force approach might be fine, but I thought I would check to see if anyone knows of a more efficient or elegant solution first.

解决方案

An example of assigning (mapping) elements of one set to points to the elements of another set of points, such that the sum Euclidean distance is minimized.

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

这篇关于最小化Python中两组点之间的总距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！