Fw: [問題] 求走遍N個座標點的最短路徑

[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的時候程式大概我這輩子跑不完了...

請問有沒有甚麼比較好的解法呢?

謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.214.215
※ 編輯: miick           來自: 114.32.214.215       (06/19 18:17)
→ hilorrk:travelling salesman?
→ EdisonX:tsp 問題沒錯,不過..你的 N 是多少 ?
→ chunhsiang:有要回到起點嗎?
推 flydragon198:Kruskal演算法，在剩餘的點裡找有最短邊的連接起來
→ loveme00835:如果和語言無關建議轉Prob_Solve, 轉完後刪文
推 suhorng:對,所以還有一個問題是,每個點到底可不可以重複經過?
→ suhorng:但即使可重複經過也並不是就是MST
推 gundan:N個點所有的排列組合很少的話就不會出現ga sa這種東西了
→ hilorrk:這個問題不是minimum spanning tree吧
→ hilorrk:就算可重複經過, optimal 還是跟 TSP 一樣(三角不等式)
→ hilorrk:一般方法用一些特性(ex:degree)也能加速不少..被強者電過
→ hilorrk:不對, 沒事... 上一句話當我沒說XDD
→ miick:N可能是無限大, 另外每一個點不能重複, 不需要回到原點
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: miick (114.32.214.215), 時間: 06/21/2012 10:16:10
※ 編輯: miick           來自: 114.32.214.215       (06/21 10:18)