[問題] 棋盤走路的問題

看板Prob_Solve作者 (師大狗鼻哥)時間11年前 (2014/03/13 01:46), 編輯推噓4(4推 0噓 8→)
留言12則, 7人參與, 最新討論串1/2 (看更多)
不好意思 這算半個作業文 題目的內容大概是 一個棋盤會給定起點和終點 然後棋盤上每一格都會有值 求起點到終點的所經過的最小值 我大概知道要用BFS來解決 但我想到說起點和終點會不固定 如果我剛好這次的iterate有兩個以上相同的值 我應該是依貪婪的方式 選擇離終點最近的 但我想是該直接去量兩者之間的距離 還是應該直接選方位呢? (若終點在左上 我應當選這次可走的最左或最上方為主) 這邊卡了滿久 希望有大大能幫忙解惑 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.122.216.115
→
03/13 02:01, , 1F
因為每一格會有不同權重, BFS 應該不夠, 試試看最短路徑
03/13 02:01, 1F
→
03/13 02:01, , 2F
i.e. Dijkstra
03/13 02:01, 2F
推
03/13 10:20, , 3F
如果是棋盤的話純Dijkstra很容易爆，要優化
03/13 10:20, 3F
→
03/13 12:19, , 4F
可以說明一下為何會爆嗎？棋盤有什麼特別？ 優化又是指什麼？
03/13 12:19, 4F
→
03/13 12:41, , 5F
a* 搜索
03/13 12:41, 5F
→
03/13 18:15, , 6F
因為作業是要比較bfs ids的效能 所以我想先做bfs
03/13 18:15, 6F
→
03/13 22:24, , 7F
我想順便問一下，這題適合用動態規劃做嗎？
03/13 22:24, 7F
推
03/14 11:28, , 8F
為什麼要找最短路徑? 不是要找棋盤最小值嗎?
03/14 11:28, 8F
→
03/14 14:29, , 9F
的確是最小路徑沒錯 我的說明不太清楚
03/14 14:29, 9F
推
03/14 16:19, , 10F
如果是bfs/ids的話 那麼你應該是人工智慧的課程？
03/14 16:19, 10F
推
03/14 16:22, , 11F
這樣的話應該就不會用到dijkstra了 dijkstra是圖論的東西
03/14 16:22, 11F
→
03/15 02:17, , 12F
沒錯是ai的課
03/15 02:17, 12F
‣ 更多 soheadsome 的文章
文章代碼(AID): #1J89sAs4 (Prob_Solve)
‣ 更多 soheadsome 的文章
文章代碼(AID): #1J89sAs4 (Prob_Solve)