我需要一种算法来对 2D 平面中的多个点列表进行排序，以便每个列表的对应点最小化它们之间的距离。
即对于两个长度相等的列表，第一个列表的第一个点到第二个列表的第一个点的距离最小，第一个的第二个点到第二个的第二个点的距离最小，等等。
我的第一个想法是简单地按 x 和 y 坐标的平均值排序，但我觉得这并不完全准确。
问问题
1015 次
1 回答
1
如果您试图最小化相邻点之间的总距离，这根本不是一个排序任务。
相反，您似乎正在尝试解决二维空间中的哈密顿路径问题。对于点之间的任意距离，这是 NP 完全的。在您的情况下，即使对欧几里得距离的限制仍然是 NP-complete，但是有近似算法；见https://www.ads.tuwien.ac.at/teaching/ws10/AlgGraphen/ag3-2x2.pdf。一般来说，由于 Sanjeev Arora 的工作，欧几里得 TSP 可以在多项式时间内逼近，他为此获得了哥德尔奖：
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.6765
搜索欧几里得旅行商问题，您还将获得其他科学论文的链接，讨论如何近似解决此问题。
于 2013-03-14T01:38:21.103 回答