您的位置：程序门 -> 专题开发/技术/项目 -> 数据结构与算法

遍历一组二维点距离为最短

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

遍历一组二维点距离为最短[已结贴,结贴人:yiguo_119]

发表于：2007-09-15 23:05:14 楼主

已知：给定100000个二维点两点间的距离为它们间坐标（x1,y1）（x2,y2)的距离
要求：从离原点开始，遍历这些二维点，使经过这些点的总距离为最短
请各位大虾帮我找一找算法思路或例子...

发表于：2007-09-16 00:29:191楼得分:0

个人看法。。
要使连线总距离最短，那么对于每个点，我们连的下一个点必然是跟当前点距离最近的点。但是总点数太多的话，我们每次都扫描一次所有没有连接的点，代价太高了。所以我设想是，把100000个点，按x坐标排序一次存为表a，按y坐标排序一次存为表b。然后对于给定的当前点p，我们只要扫描表a中p.x周围和表b中p.y周围没有连接的点，就可以大幅度减少比较次数。至于在p.x和p.y周围多大范围的点要扫描，我觉得这个范围可以自己摸索，我还没有很明确的想法。就这样。

发表于：2007-09-16 09:52:202楼得分:0

********************************************

*

二维点的分布如上图所示
sli_romen, 如你所讲的方法,遍历的总距离并不是最短

发表于：2007-09-16 10:12:303楼得分:0

n个点，要连成n-1条线。找出最短的n-1条线就可以了

发表于：2007-09-16 10:25:544楼得分:0

edwin,是图的遍历,不是求图的最短路径

发表于：2007-09-16 10:38:345楼得分:0

嗯，我的想法确实有问题，再想想

发表于：2007-09-16 11:00:106楼得分:10

嗯，发现这个问题不是我能解决的了。。。
http://topic.csdn.net/t/20050829/18/4238459.html

发表于：2007-09-17 11:03:477楼得分:10

将未遍历的点放在集合 a 中，将已遍历的有序点（路径）放在数组（或链表之类的结构）b 中；函数 d（（x1,y1),（x2,y2)) 表示两点直接的距离。

初时化：a{所以100000个点}，b{仅原点（0,0)}。
第一步：从 a 中找出一个点 p1（x1,y1)，与原点之间的距离 d（（x1,y1),（0,0)) 最短；将 p1 从 a 中删除，添加到 b 的原点后面。
第二步：从 a 中找出一个点 p2（x2,y2)，新增距离 a=d（（x2,y2),（x1,y1))+d（（x2,y2),（0,0))-d（（x1,y1),（0,0)) 或 b=d（（x2,y2),（x1,y1)) 最短（注：是所有点中同时考虑 a、b 查找最短）；将 p2 从 a 中删除，如果 a < b 那么将 p2 插入到 p1 前面，否则添加到 p2 后面。
...
第n 步：从 a 中找出一个点 pn（xn,yn)，新增距离：
　　　　　　对 b 中任意连续两个点 pi、pj（其中j=i+1），a=d（（xn,yn),（xi,yi))+d（（xn,yn),（xj,yj))-d（（xi,yi),（xj,yj))
　　　　　　到 b 中最后一个点 pk（其中 k=n-1），b=d（（xn,yn),（xk,yk))
　　　　最短（注：是所有点中同时考虑所有 a、b 查找最短）；将 pn 从 a 中删除，如果 a < b 那么将 pn 插入到 pj 前面，否则添加到 pk 后面。
...
一直到 a 为空。

关键是如何对查找点 pn 进行优化。

发表于：2007-09-18 17:14:178楼得分:10

数量少，穷举还行，产生所有组合，求最小的；1000个如果求较优的，用遗传算法什么的也还行；数量又大、还求最优的，关注中……（注；恐怕是无解）

发表于：2007-09-19 08:53:029楼得分:10

二维排序，然后按一定的半径遍历所有点。如果半径内没有另外的点，则增大半径，如果有点，找出距离最小点

发表于：2007-09-20 22:06:3410楼得分:10

一个比较经典的npc问题。

发表于：2007-09-21 02:04:2011楼得分:0

旅行商问题？

发表于：2007-09-21 16:56:0112楼得分:10

考虑用动态规划算法做,但是复杂度太大,2^n;

发表于：2007-09-21 23:06:3113楼得分:0

最后没有要求回原点，不是商旅问题吧？，应该是完全图的遍历

发表于：2007-09-22 09:12:4814楼得分:10

最优算法复杂度为o（n×lgn)，divide-and-conquer algorithm.详见 introduction to algorithms 2nd ed by corman etc. section 33.4. 中文名是算法导论

发表于：2007-09-22 09:15:3415楼得分:0

不好意思看错帖子了，这个不是travelling salesman problem 么。100000个点就不用自己想算法了，找现成的论文吧。

发表于：2007-09-23 19:19:1616楼得分:0

o,如果楼主找到了好的解法，希望能够贴出来，即使不是最优的。

发表于：2007-09-24 17:03:3317楼得分:30

最优的算法好像需要2^n数量级，在你的1000000量上这个是肯定是不能完成的任务。

不过你可以通过启发式算法找一些次优解。

下一篇：一个题目，不知道哪出错了，见鬼！！！
上一篇：一个大o的分析

其他资讯

您的位置：程序门 -> 专题开发/技术/项目 -> 数据结构与算法

遍历一组二维点 距离为最短

遍历一组二维点距离为最短