在最小点对距离的总和 [英] Minimize sum of distances in point pairs
问题描述
我有一个2维网格一束点。我想组的点数成对，同时最小化对的点之间的欧氏距离的总和。
I have a bunch of points on a 2-dimensional Grid. I want to group the Points into pairs, while minimizing the sum of the euclidean distances between the points of the pairs.
例如：
Given the points:
p1: (1,1)
p2: (5,5)
p3: (1,3)
p4: (6,6)
Best solution:
pair1 = (p1,p3), distance = 2
pair2 = (p2,p4), distance = 1
Minimized total distance: 1+2 = 3
我怀疑这个问题可能是可解的匈牙利算法的变种？！
什么是解决问题的最快方法是什么？
What is the fastest way to solve the problem?
（小注：我总应该有不少于12分）
(Little Remark: I always should have less than 12 points.)
推荐答案
正在试图解决的问题是通过一个完全连接（网）的网络，你在哪里不允许访问每个顶点/节点类似的最短路径不止一次，你不关心连接最小的对。
The problem you are trying to solve is similar to the shortest path through a fully connected (mesh) network, where you are not allowed to visit each vertex/node more than once, and you don't care about connecting the minimal pairs.
This problem is approachable when using techniques from graph theory, metric spaces, and other results from computational geometry.
这个问题类似于在最近的两个点的问题和文章提供有关的 Voroni图和 Delaunay三角，以及如使用递归分而治之算法来解决这个问题。
This problem is similar the wiki article on the Closest pair of points problem, and the article offers some useful insights regarding Voroni diagrams and Delaunay triangulation, as well as using Recursive Divide and Conquer algorithms to solve the problem.
请注意，解决最接近点对不是解决办法，因为你可以有四点（A，B，C，D）在一条线上，其中d（B，C）是最不重要的，但你也要有D（A，D），并且总和会比D（A，B）和D（C，D）。大
Note that solving the closest pair of points is not the solution, as you could have four points (A,B,C,D) in a line, where d(B,C) is least, but then you would also have d(A,D), and the sum would be larger than d(A,B) and d(C,D).
这<一href="http://stackoverflow.com/questions/1602164/shortest-distance-between-points-algorithm">stackoverflow问题的解释如何找到两个点之间的最短距离，并且有一个有用的暗示跳过计算平方根而比较距离。答案建议使用分而治之的办法（线性），但观察到拆分X和Y坐标可能更适合的分区。
This stackoverflow question explains how to find the shortest distance between two points, and has a useful hint to skip computing the square root while comparing distances. Answers suggest using a divide and conquer approach (linear), but observe that splitting both X and Y coordinates might partition more appropriately.
这<一href="http://math.stackexchange.com/questions/581831/calculating-the-shortest-distance-between-n-number-of-points-on-a-scatter-graph">math stackexchange问题解决类似的问题，并建议使用 Prim算法，<一个HREF =http://en.wikipedia.org/wiki/Kruskal%27s_algorithm相对=nofollow> Kruskal算法或指出，这是旅行商问题，这是的 NP难。
This math stackexchange question addresses a similar problem, and suggests using Prim's algorithm, Kruskal's algorithm, or notes that this is a special case of the Travelling Salesman problem, which is NP-hard.
我的做法是用贪心算法来计算最小生成树解决你的问题（配对的最近点），然后从生成树1/2的边缘（离开断开对）删除。有可能使用一个贪心算法的第二（变种）。
My approach would be to solve your problem (pairing the closest points) using a greedy algorithm to compute a minimal spanning tree, and then remove from the spanning tree 1/2 the edges (leaving disconnected pairs). Likely using a second (variant) of a greedy algorithm.
这篇关于在最小点对距离的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
