Re: [問題] 求走遍N個座標點的最短路徑
看板Prob_Solve (計算數學 Problem Solving)作者hichcock (快樂一整年 ^^~~~)時間12年前 (2012/06/21 17:01)推噓0(0推 0噓 8→)留言8則, 3人參與討論串2/2 (看更多)
※ 引述《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
→
06/21 18:15, , 1F
06/21 18:15, 1F
→
06/21 18:17, , 2F
06/21 18:17, 2F
→
06/21 18:21, , 3F
06/21 18:21, 3F
→
06/21 19:05, , 4F
06/21 19:05, 4F
→
06/21 19:05, , 5F
06/21 19:05, 5F
→
06/21 19:06, , 6F
06/21 19:06, 6F
→
06/22 10:07, , 7F
06/22 10:07, 7F
→
06/22 10:08, , 8F
06/22 10:08, 8F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
