[問題] 最短路徑問題 noodleT PTT批踢踢實業坊

[問題] 最短路徑問題

作者: noodleT (麵T) 2016-07-25 22:25:26

http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d062
題目如上面連結。
我的做法是先求出任兩點間的最短路徑值，
接著利用貪婪法決定下一個拜訪(最近)的城市。
但如果離起點(當下位置)最近的有兩個以上，
則把這些路徑都測試過一遍。
雖然有通過測驗，但這種作法是正確的嗎？
還是運氣好罷了？
會提出這問題是因為想到 TSP 無法用貪婪解。

作者: FRAXIS (喔喔) 2016-07-25 22:37:00

這問題跟 TSP 應該是等價的吧所以 greedy 應該不 work..TSP 中的 edge weight 是輸入的一部分你想的 TSP 是 edge weight 被設定為 Euclidean distance所以只是 TSP 的特例而已..不過這題的圖是定死的而且是 grid 的 subgraph所以應該有比較快的方法作吧

作者: DJWS (...) 2016-07-26 06:52:00

運氣好

作者: FRAXIS (喔喔) 2016-07-26 11:49:00

我查了一下 TSP 在 grid graph 中還是 NPC 的HAMILTON PATHS IN GRID GRAPHS 論文 title不過如果 grid graph 上面沒有洞的話是多項式可解的

作者: noodleT (麵T) 2016-07-26 12:15:00

在這張圖上有什麼例子是貪婪解不出來的？看很久沒看出來

作者: yvb 2016-07-26 14:07:00

從 n 出發, 須拜訪 a, b, f, j, p.

作者: noodleT (麵T) 2016-07-26 19:57:00

謝謝樓上，我再想想其他解法

作者: FRAXIS (喔喔) 2016-07-26 21:38:00

應該就 backtracking 吧

作者: DJWS (...) 2016-07-28 22:00:00

TSP可以用動態規劃解時間從O(n!)變O(2^n * n) 快了很多O(2^n * n^2)

作者: noodleT (麵T) 2016-08-01 16:38:00

加入限制條件後就快多了

作者: FRAXIS (喔喔) 2016-08-01 21:01:00

你還可以嘗試 A star

作者: noodleT (麵T) 2016-08-01 21:17:00

好的

作者: FRAXIS (喔喔) 2016-08-06 22:02:00

A* 如果你 heuristic 設計的對是保證會有最佳解的..

作者: DJWS (...) 2016-08-10 07:06:00

這題的heuristic要怎麼設計？我是第一次聽說這種題目可以A*

作者: FRAXIS (喔喔) 2016-08-10 08:02:00

要設計不難啊有沒有用又是另外一回事..MST 的 cost 應該可以當 heuristic 吧

作者: DJWS (...) 2016-08-10 21:43:00

是可以，不過總共得算多少次MST呢?

繼續閱讀

Re: [問題]zerojudge競賽題目b841:104北二5.骨牌遊戲DJWS Re: [問題]zerojudge競賽題目b841:104北二5.骨牌遊戲DJWS Re: [問題]zerojudge競賽題目b841:104北二5.骨牌遊戲yr [問題]zerojudge競賽題目b841:104北二5.骨牌遊戲vagrantlike Re: [問題] 整數非線性規劃用ILP solver求解yr [問題] 整數非線性規劃用ILP solver求解PttPttPtt3 Re: [問題] 用最少比較次數找最大、最小等值cocoyan [問題] 如何將一直線轉移至另一直線位置？johnpage Re: [問題] 用最少比較次數找最大、最小等值cocoyan [問題] DFS建特定條件下的Edgedinex