[理工] Find a path of the maze

看板Grad-ProbAsk作者 (西木野真姬)時間5年前 (2020/10/17 18:52), 5年前編輯推噓3(3推 0噓 8→)
留言11則, 4人參與, 5年前最新討論串1/1
師大106 這題問 Which data structure is required to find a path of the mazing problem?(stack or queue) 我疑問的是， BFS 跟 DFS 應該都可吧？所以兩個資料結構應該都行？ 雖然程式運作上避免不掉會用到 memory stack 不過我想題目應該不是想問這個 還是說 BFS 沒辦法走迷宮？ ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.9.95 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1602931960.A.895.html
推
10/17 18:55, 5年前 , 1F
stack比較適合吧 如果走錯了你還能回到前面選別條路
10/17 18:55, 1F
的確 stack 是正常的迷宮走法，不過只是要找路徑的話 bfs也是可以的吧？
→
10/17 19:08, 5年前 , 2F
queue的話 你處理完就pop掉了要怎麼回頭重找別條路
10/17 19:08, 2F
你pop前會先把它附近的路enqueue啊
→
10/17 19:14, 5年前 , 3F
這題重點應該放在which data structure
10/17 19:14, 3F
→
10/17 19:19, 5年前 , 4F
好吧 我覺得題目沒講很清楚，走迷宮的確BFS DFS 都可以吧
10/17 19:19, 4F
→
10/17 19:19, 5年前 , 5F
？只是BFS的走法不是普遍的迷宮走法，DFS比較像真的在走
10/17 19:19, 5F
→
10/17 19:19, 5年前 , 6F
迷宮？
10/17 19:19, 6F
※ 編輯: NTUmaki (39.10.9.95 臺灣), 10/17/2020 19:22:11 ※ 編輯: NTUmaki (39.10.9.95 臺灣), 10/17/2020 19:22:47
→
10/17 19:38, 5年前 , 7F
要找路徑BFS也是可以 DFS相對比較直觀而已
10/17 19:38, 7F
→
10/17 19:38, 5年前 , 8F
以迷宮來說的話
10/17 19:38, 8F
推
10/18 07:36, 5年前 , 9F
爛題目，兩個都可以，BFS 找到的還是最短路徑勒。
10/18 07:36, 9F
推
10/19 02:58, 5年前 , 10F
BFS 的話要避免 loop 比較麻煩 而且記憶體使用量也比較高
10/19 02:58, 10F
→
10/19 02:59, 5年前 , 11F
不過 BFS 也是可以走迷宮就是了..
10/19 02:59, 11F
‣ 更多 NTUmaki 的文章
文章代碼(AID): #1VYipuYL (Grad-ProbAsk)