Re: [問題] 最短路徑問題
看板Prob_Solve (計算數學 Problem Solving)作者pttworld (批踢踢世界)時間8年前 (2016/08/12 00:25)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/2 (看更多)
※ 引述《noodleT (麵T)》之銘言：
: http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d062
: 題目如上面連結。
: 我的做法是先求出任兩點間的最短路徑值，
: 接著利用貪婪法決定下一個拜訪(最近)的城市。
: 但如果離起點(當下位置)最近的有兩個以上，
: 則把這些路徑都測試過一遍。
: 雖然有通過測驗，但這種作法是正確的嗎？
: 還是運氣好罷了？
: 會提出這問題是因為想到 TSP 無法用貪婪解。
本題使用Floyd Warshall後Depth First Search得解。
著名最短路徑兩種演算法：Dijkstra及Floyd Warshall對應單點至全圖及全點全圖。
（如果跑n次Dijkstra也可以）
得到所有點單對單的最短距離後進行n-1次（扣掉起點）的最短加總。
因為最短可能不只一組點對，使用DFS展開。
如沒有記憶體量及執行時間限制可以只使用BFS。
--
排了二萬多順位註冊的隊，首發
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.43.36.13
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1470932721.A.70A.html
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
