[問題] 棋盤走路的問題

[soheadsome (師大狗鼻哥)]

不好意思 這算半個作業文

題目的內容大概是

一個棋盤會給定起點和終點

然後棋盤上每一格都會有值

求起點到終點的所經過的最小值

我大概知道要用BFS來解決

但我想到說起點和終點會不固定

如果我剛好這次的iterate有兩個以上相同的值

我應該是依貪婪的方式 選擇離終點最近的

但我想是該直接去量兩者之間的距離

還是應該直接選方位呢?

(若終點在左上 我應當選這次可走的最左或最上方為主)

這邊卡了滿久

希望有大大能幫忙解惑 謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.122.216.115
→ scwg:因為每一格會有不同權重, BFS 應該不夠, 試試看最短路徑
→ scwg:i.e. Dijkstra
推 s89162504:如果是棋盤的話純Dijkstra很容易爆，要優化
→ tkcn:可以說明一下為何會爆嗎？棋盤有什麼特別？ 優化又是指什麼？
→ wasidada:a* 搜索
→ soheadsome:因為作業是要比較bfs ids的效能 所以我想先做bfs
→ EdisonX:我想順便問一下，這題適合用動態規劃做嗎？
推 DJWS:為什麼要找最短路徑? 不是要找棋盤最小值嗎?
→ soheadsome:的確是最小路徑沒錯 我的說明不太清楚
推 DJWS:如果是bfs/ids的話  那麼你應該是人工智慧的課程？
推 DJWS:這樣的話應該就不會用到dijkstra了  dijkstra是圖論的東西
→ soheadsome:沒錯是ai的課