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

看板Prob_Solve作者 (Mick)時間12年前 (2012/06/21 10:16), 編輯推噓0(0推 0噓 0→)
留言0則, 0人參與, 最新討論串1/2 (看更多)
※ [本文轉錄自 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)
→
06/19 18:17, , 1F
travelling salesman?
06/19 18:17, 1F
→
06/19 18:18, , 2F
tsp 問題沒錯,不過..你的 N 是多少 ?
06/19 18:18, 2F
→
06/19 18:47, , 3F
有要回到起點嗎?
06/19 18:47, 3F
推
06/19 19:08, , 4F
Kruskal演算法，在剩餘的點裡找有最短邊的連接起來
06/19 19:08, 4F
→
06/19 19:15, , 5F
如果和語言無關建議轉Prob_Solve, 轉完後刪文
06/19 19:15, 5F
推
06/19 19:39, , 6F
對,所以還有一個問題是,每個點到底可不可以重複經過?
06/19 19:39, 6F
→
06/19 19:40, , 7F
但即使可重複經過也並不是就是MST
06/19 19:40, 7F
推
06/19 23:07, , 8F
N個點所有的排列組合很少的話就不會出現ga sa這種東西了
06/19 23:07, 8F
→
06/20 00:33, , 9F
這個問題不是minimum spanning tree吧
06/20 00:33, 9F
→
06/20 00:35, , 10F
就算可重複經過, optimal 還是跟 TSP 一樣(三角不等式)
06/20 00:35, 10F
→
06/20 00:45, , 11F
一般方法用一些特性(ex:degree)也能加速不少..被強者電過
06/20 00:45, 11F
→
06/20 00:47, , 12F
不對, 沒事... 上一句話當我沒說XDD
06/20 00:47, 12F
→
06/21 10:10, , 13F
N可能是無限大, 另外每一個點不能重複, 不需要回到原點
06/21 10:10, 13F
※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: miick (114.32.214.215), 時間: 06/21/2012 10:16:10 ※ 編輯: miick 來自: 114.32.214.215 (06/21 10:18)
‣ 更多 miick 的文章
文章代碼(AID): #1FueFiHp (Prob_Solve)
‣ 更多 miick 的文章
文章代碼(AID): #1FueFiHp (Prob_Solve)