作者miick (Mick)
看板Prob_Solve
标题Fw: [问题] 求走遍N个座标点的最短路径
时间Thu Jun 21 10:16:10 2012
※ [本文转录自 C_and_CPP 看板 #1Fu55lJn ]
作者: miick (Mick) 看板: C_and_CPP
标题: [问题] 求走遍N个座标点的最短路径
时间: Tue Jun 19 18:16:13 2012
开发平台(Platform): (Ex: VC++, GCC, Linux, ...)
Visual Studio 2010
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
.Net framework 4.0
问题(Question)：
现在N个2维的座标点
不限行走的顺序
行走的点不能重复
行走的路线可以交叉
求走遍N个点的最短距离与路线。
喂入的资料(Input)：
我目前用暴力法
跑到N = 13的时候程式大概我这辈子跑不完了...
请问有没有甚麽比较好的解法呢?
谢谢！
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.32.214.215
※ 编辑: miick 来自: 114.32.214.215 (06/19 18:17)
1F：→ hilorrk:travelling salesman? 06/19 18:17
2F：→ EdisonX:tsp 问题没错,不过..你的 N 是多少 ? 06/19 18:18
3F：→ chunhsiang:有要回到起点吗? 06/19 18:47
4F：推 flydragon198:Kruskal演算法，在剩余的点里找有最短边的连接起来 06/19 19:08
5F：→ loveme00835:如果和语言无关建议转Prob_Solve, 转完後删文 06/19 19:15
6F：推 suhorng:对,所以还有一个问题是,每个点到底可不可以重复经过? 06/19 19:39
7F：→ suhorng:但即使可重复经过也并不是就是MST 06/19 19:40
8F：推 gundan:N个点所有的排列组合很少的话就不会出现ga sa这种东西了 06/19 23:07
9F：→ hilorrk:这个问题不是minimum spanning tree吧 06/20 00:33
10F：→ hilorrk:就算可重复经过, optimal 还是跟 TSP 一样(三角不等式) 06/20 00:35
11F：→ hilorrk:一般方法用一些特性(ex:degree)也能加速不少..被强者电过 06/20 00:45
12F：→ hilorrk:不对, 没事... 上一句话当我没说XDD 06/20 00:47
13F：→ miick:N可能是无限大, 另外每一个点不能重复, 不需要回到原点 06/21 10:10
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: miick (114.32.214.215), 时间: 06/21/2012 10:16:10
※ 编辑: miick 来自: 114.32.214.215 (06/21 10:18)