PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 最短路徑問題

看板Prob_Solve (計算數學 Problem Solving)作者 (麵T)時間7年前 (2016/07/25 22:25), 7年前編輯推噓13(13推 0噓 14→)
留言27則, 4人參與, 最新討論串1/2 (看更多)
http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d062 題目如上面連結。 我的做法是先求出任兩點間的最短路徑值， 接著利用貪婪法決定下一個拜訪(最近)的城市。 但如果離起點(當下位置)最近的有兩個以上， 則把這些路徑都測試過一遍。 雖然有通過測驗，但這種作法是正確的嗎？ 還是運氣好罷了？ 會提出這問題是因為想到 TSP 無法用貪婪解。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.195.169 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1469456729.A.513.html ※ 編輯: noodleT (39.12.195.169), 07/25/2016 22:26:21
推
07/25 22:37, , 1F
這問題跟 TSP 應該是等價的吧 所以 greedy 應該不 work..
07/25 22:37, 1F
我認為是不等價的， TSP 中 af 距離為 sqrt(2) 而在此題中 af = ab + bf = 2 觀念若有錯請多包涵 ※ 編輯: noodleT (39.12.195.169), 07/25/2016 22:55:35
推
07/25 23:03, , 2F
TSP 中的 edge weight 是輸入的一部分
07/25 23:03, 2F
→
07/25 23:03, , 3F
你想的 TSP 是 edge weight 被設定為 Euclidean distance
07/25 23:03, 3F
→
07/25 23:03, , 4F
所以只是 TSP 的特例而已..
07/25 23:03, 4F
推
07/25 23:05, , 5F
不過這題的圖是定死的 而且是 grid 的 subgraph
07/25 23:05, 5F
→
07/25 23:06, , 6F
所以應該有比較快的方法作吧
07/25 23:06, 6F
推
07/26 06:52, , 7F
運氣好
07/26 06:52, 7F
推
07/26 11:49, , 8F
我查了一下 TSP 在 grid graph 中還是 NPC 的
07/26 11:49, 8F
→
07/26 11:49, , 9F
HAMILTON PATHS IN GRID GRAPHS 論文 title
07/26 11:49, 9F
→
07/26 11:50, , 10F
不過如果 grid graph 上面沒有洞的話是多項式可解的
07/26 11:50, 10F
→
07/26 12:15, , 11F
在這張圖上有什麼例子是貪婪解不出來的？
07/26 12:15, 11F
→
07/26 12:16, , 12F
看很久沒看出來
07/26 12:16, 12F
推
07/26 14:07, , 13F
從 n 出發, 須拜訪 a, b, f, j, p.
07/26 14:07, 13F
→
07/26 19:57, , 14F
謝謝樓上，我再想想其他解法
07/26 19:57, 14F
→
07/26 21:38, , 15F
應該就 backtracking 吧
07/26 21:38, 15F
目前利用一張表來儲存子問題(應該是屬於動態規劃解)，但效果不彰。 從 a 出發把所有點走一遍需要跑 30 秒左右(答案 15?) unsigned SortestVisitWithBacktracking (char begin,const std::vector<char> &visit)const { //map<pair<起點,拜訪點向量>,最小路徑> static std::map<std::pair<char,std::vector<char> >,unsigned> table; //... } 在思考是不是需要改成 unsigned SortestVisitWithBacktracking (char begin,const std::vector<char> &visit,unsigned 剩餘步數限制)const 利用貪婪求一開始的剩餘步數限制， 然後每次遞迴都更新(縮小)剩餘步數限制 ※ 編輯: noodleT (110.28.205.127), 07/28/2016 00:00:13
推
07/28 09:16, , 16F
應該是要的吧 不然你的方法就等同產生所有排列了..
07/28 09:16, 16F
推
07/28 22:00, , 17F
TSP可以用動態規劃解 時間從O(n!)變O(2^n * n) 快了很多
07/28 22:00, 17F
→
07/28 22:04, , 18F
O(2^n * n^2)
07/28 22:04, 18F
→
08/01 16:38, , 19F
加入限制條件後就快多了
08/01 16:38, 19F
推
08/01 21:01, , 20F
你還可以嘗試 A star
08/01 21:01, 20F
→
08/01 21:17, , 21F
好的
08/01 21:17, 21F
→
08/06 21:48, , 22F
a start 似乎沒有保證最佳解
08/06 21:48, 22F
推
08/06 22:02, , 23F
A* 如果你 heuristic 設計的對是保證會有最佳解的..
08/06 22:02, 23F
推
08/10 07:06, , 24F
這題的heuristic要怎麼設計？我是第一次聽說這種題目可以A*
08/10 07:06, 24F
推
08/10 08:02, , 25F
要設計不難啊 有沒有用又是另外一回事..
08/10 08:02, 25F
→
08/10 08:03, , 26F
MST 的 cost 應該可以當 heuristic 吧
08/10 08:03, 26F
推
08/10 21:43, , 27F
是可以，不過總共得算多少次MST呢?
08/10 21:43, 27F
‣ 更多 noodleT 的文章
文章代碼(AID): #1NbY5PKJ (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 noodleT 的文章
文章代碼(AID): #1NbY5PKJ (Prob_Solve)