作者hichcock (快乐一整年 ^^~~~)
看板Prob_Solve
标题Re: [问题] 求走遍N个座标点的最短路径
时间Thu Jun 21 17:01:34 2012
※ 引述《miick (Mick)》之铭言：
: ※ [本文转录自 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的时候程式大概我这辈子跑不完了...
: 请问有没有甚麽比较好的解法呢?
: 谢谢！
用 greedy 的方式来解决
先算出每个点两两的距离
因为路线可以 "交叉", 所以就算直线距离就好
有x, y 座标的话算直线距离应该不是问题
然後将距离最近的两点相连
再找距离头尾最近的点连接至串列上
依此类推, 应该可找出最短距离及路线
--
不想因为什麽都不努力而後悔....
如果我因为什麽都不努力而後悔....
我更希望 勇敢尝试之後却失败了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 60.248.105.226
1F：→ chunhsiang:因该是较短距离吧 这有人有证明是最短? 06/21 18:15
2F：→ chunhsiang:如果有两个点离某个点一样短 06/21 18:17
3F：→ chunhsiang:那选起来的顺续可能就对跳过最佳解 06/21 18:21
4F：→ flere:同意一楼的说法,(0,0)(2,0)(100,-1)(100,1)(100,2)原PO 06/21 19:05
5F：→ flere:的做法就有可能是错误的~ 06/21 19:05
6F：→ flere:最後一个(100,2)改成(100,5)好了> < 06/21 19:06
7F：→ hichcock:同意这并非最佳解...因为给出答案就可以同时写论文了 06/22 10:07
8F：→ hichcock:如果只是要一个近似解...应该差不多了 06/22 10:08