一个找点对应关系，使得所有点移动距离和最小的问题

htgo

如附件图，散乱的蓝色点为初始化位置
现：经过移动变为红色3×3 队列；
问题：如何规划每一个蓝色点移到哪个对应的红色点，使得所有蓝色点移动的距离和最短。
如果没有最优解，是否有优化解。
备注：
1. 个点，希望有一种针对 n个点的算法。满足条件初始化为固定的任意形状，目标队列也为固定的任意形状，求最优的对应关系；
2. 最龊的方法是所有的映射关系遍历，复杂度为 O(n!)，实不可取；
3. 我试过用 PCA算法进行分块对应，块中再分别映射，复杂度为O(a!b!...(n-a-b..)! ) ，a,b,...,n-a-b... 满足 a + b + ... + ( n-a-b... ) = n；

musicbug88

这个问题比较有趣。我有一个初步算法。让红蓝点集中距离最小的一对儿对应，让蓝点走到红点。去掉这对儿，再对其余点用这个方法。找距离最小可以用Voronoi图来试试能不能减少计算量。

musicbug88

[这个贴子最后由musicbug88在 2009/12/29 02:40pm 第 1 次编辑]

如果能证明最优方案一定是距离最小的一对儿配对儿，那就能证明我说的方法就是最优的[br][br][color=#990000]-=-=-=-=- 以下内容由 musicbug88 在 时添加 -=-=-=-=-
我用在单位正方形内产生随机点的方法，编写了一个小程序，找到了反例。也就是距离最小的一对儿配对儿不一定是最优的。或许能找到公式算出我在2楼上说的方案与最优解距离和比值的估计值。[br][br][color=#990000]-=-=-=-=- 以下内容由 musicbug88 在 时添加 -=-=-=-=-
反例数目大约占1/5左右，说明2楼的方案有获得次优解得希望

musicbug88

搜索到一些资料，这个问题被称为最小欧几里得匹配问题
链接在  http://maven.smith.edu/~orourke/TOPP/P6.html
我说吗，这么有趣的问题一定有人研究了。为了防止这个网址以后失效，内容贴出如下
Problem 6: Minimum Euclidean Matching in 2D
Statement
What is the complexity of computing a minimum-cost Euclidean matching for 2n points in the plane? The cost of a matching is the total length of the edges in the matching.
Origin
Uncertain, pending investigation.
Status/Conjectures
Open.
Partial and Related Results
An algorithm that achieves the minimum and runs in nearly O(n2.5) time has long been available [Vai89]. This was improved to O(n1.5log5n) in [Var98]. Recently Arora showed how to achieve a (1 + )-approximation in n(log n)O(1/) time [Aro98], and this has been improved to O((n/)log6n) time [VA99].
A special case of considerable interest is bipartite matching, in which the points are red or blue and the matching connects points of different color. Here O(n2+) has been achieved [AES99], and a (1 + )-approximation can be found in O((n/)1.5log5n) time [VA99].
Appearances
[MO01]
Categories
shortest paths
Entry Revision History
J. O';Rourke, 2 Aug. 2001; 30 Aug. 2001; 13 Dec. 01 (thanks to M. Sharir).
Bibliography
Aro98
Sanjeev Arora.
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.
J. Assoc. Comput. Mach., 45(5):753-782, 1998.

AES99
P. K. Agarwal, A. Efrat, and Micha Sharir.
Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications.
SIAM J. Comput., 29:912-953, 1999.

MO01
J. S. B. Mitchell and Joseph O';Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.

Var98
K. Varadarajan.
A divide and conquer algorithm for min-cost perfect matching in the plane.
In Proc. 39th Annu. IEEE Sympos. Found. Comput. Sci., pages 320-329, 1998.

Vai89
P. M. Vaidya.
Geometry helps in matching.
SIAM J. Comput., 18:1201-1225, 1989.

VA99
K. R. Varadarajan and Pankaj K. Agarwal.
Approximation algorithms for bipartite and non-bipartite matching in the plane.
In Proc. 10th ACM-SIAM Sympos. Discrete Algorithms, pages 805-814, 1999.