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

[hichcock (快樂一整年 ^^~~~)]

※ 引述《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
→ chunhsiang:因該是較短距離吧 這有人有證明是最短?
→ chunhsiang:如果有兩個點離某個點一樣短
→ chunhsiang:那選起來的順續可能就對跳過最佳解
→ flere:同意一樓的說法,(0,0)(2,0)(100,-1)(100,1)(100,2)原PO
→ flere:的做法就有可能是錯誤的~
→ flere:最後一個(100,2)改成(100,5)好了> <
→ hichcock:同意這並非最佳解...因為給出答案就可以同時寫論文了
→ hichcock:如果只是要一個近似解...應該差不多了