作者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)