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

[問題] LC 505 the maze ii 時間複雜度估算

看板Prob_Solve (計算數學 Problem Solving)作者 (.)時間6年前 (2019/01/11 12:38), 6年前編輯推噓3(3推 0噓 9→)
留言12則, 1人參與, 6年前最新討論串1/1
Leetcode 505. The Maze II 時間複雜度怎麼計算? 這題鎖上了。題目請見這篇：http://www.cnblogs.com/grandyang/p/6725380.html leetcde 解法1 每個點不斷的暴力更新 https://paste.ubuntu.com/p/mdmfBFFgJf/ 每次bfs的時候加一層while loop來模擬滾動 time complexity m*n*max(m,n) 我的理解：總共m*n個點，每個點都有m or n的滾動的可能 (這應該正確吧?) leetcde 解法2 用一個heap來代替que以實現最短路徑 https://paste.ubuntu.com/p/HP5v93dQKf/ 我最早的想法：總共m*n個點，heap裡面最多就是m*n， 所以每次彈出的複雜度就是log(m*n) 總共m*n個點，所以是m*n*log(m*n) 每次彈出之後有滾動，那麼就變成 m*n*log(m*n)*max(m,n) (很明顯不對，這樣就比上面的暴力還慢) 解答上寫 m*n*log(m*n) <-- 那麼每一個點彈出之後的滾動呢？ 謝謝大家的回答 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.189.14.17 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1547181489.A.0B2.html ※ sean72:轉錄至看板 Programming 01/11 12:39 ※ 編輯: sean72 (73.189.14.17), 01/11/2019 14:25:17
推
01/12 11:40, 6年前 , 1F
你頂多只有 m*n 個點 m*n*4 條邊 所以你頂多插入 m*n*4 次
01/12 11:40, 1F
謝謝你的推文，但我還是不太明白，可以麻煩你再解釋多一些嗎? 計算用heap 但是每次彈出一個點之後，都需要用while loop滾動，這部分怎麼加入估算呢? ※ 編輯: sean72 (73.189.14.17), 01/12/2019 16:16:50
推
01/12 22:59, 6年前 , 2F
你滾動的那部份應該可以作 preprocess 吧
01/12 22:59, 2F
該如何做preprocess呢? 謝謝 ※ 編輯: sean72 (73.189.14.17), 01/13/2019 09:44:31
推
01/14 05:40, 6年前 , 3F
一個簡單的方法 就是先把 Graph 直接建起來
01/14 05:40, 3F
→
01/14 05:40, 6年前 , 4F
每一個點 可以滾動到哪些點 在搜尋之前先建好
01/14 05:40, 4F
→
01/14 05:41, 6年前 , 5F
在建的時候要有技巧 因為點 u 朝方向 d 最終滾到 v 的話
01/14 05:41, 5F
→
01/14 05:41, 6年前 , 6F
那 u ~ v 上面的所有點 向 d 滾動必定也都會滾到 v
01/14 05:41, 6F
→
01/14 05:42, 6年前 , 7F
利用這個性質就可以避免重複計算
01/14 05:42, 7F
→
01/14 05:42, 6年前 , 8F
然後在搜尋的時候就可以不用計算滾動了
01/14 05:42, 8F
→
01/14 05:43, 6年前 , 9F
要加速的話 就一邊搜尋一邊建圖
01/14 05:43, 9F
→
01/14 05:44, 6年前 , 10F
或是用 A* 搜尋，這種 2D Grid Graph 的 Heuristic
01/14 05:44, 10F
→
01/14 05:44, 6年前 , 11F
已經有很多人研究過了
01/14 05:44, 11F
→
01/14 05:44, 6年前 , 12F
01/14 05:44, 12F
‣ 更多 sean72 的文章
文章代碼(AID): #1SE1sn2o (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 sean72 的文章
文章代碼(AID): #1SE1sn2o (Prob_Solve)