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