[問題] 棋盤走路的問題 soheadsome PTT批踢踢實業坊

[問題] 棋盤走路的問題

作者: soheadsome (師大狗鼻哥) 2014-03-13 01:46:47

不好意思這算半個作業文
題目的內容大概是
一個棋盤會給定起點和終點
然後棋盤上每一格都會有值
求起點到終點的所經過的最小值
我大概知道要用BFS來解決
但我想到說起點和終點會不固定
如果我剛好這次的iterate有兩個以上相同的值
我應該是依貪婪的方式選擇離終點最近的
但我想是該直接去量兩者之間的距離
還是應該直接選方位呢?
(若終點在左上我應當選這次可走的最左或最上方為主)
這邊卡了滿久
希望有大大能幫忙解惑謝謝

作者: scwg ( ) 2014-03-13 02:01:00

因為每一格會有不同權重, BFS 應該不夠, 試試看最短路徑i.e. Dijkstra

作者: s89162504 (阿本) 2014-03-13 10:20:00

如果是棋盤的話純Dijkstra很容易爆，要優化

作者: tkcn (say) 2014-03-13 12:19:00

可以說明一下為何會爆嗎？棋盤有什麼特別？優化又是指什麼？

作者: wasidada (dada) 2014-03-13 12:41:00

a* 搜索

作者: soheadsome (師大狗鼻哥) 2014-03-13 18:15:00

因為作業是要比較bfs ids的效能所以我想先做bfs

作者: EdisonX (卡卡獸) 2014-03-13 22:24:00

我想順便問一下，這題適合用動態規劃做嗎？

作者: DJWS (...) 2014-03-14 11:28:00

為什麼要找最短路徑? 不是要找棋盤最小值嗎?

作者: soheadsome (師大狗鼻哥) 2014-03-14 14:29:00

的確是最小路徑沒錯我的說明不太清楚

作者: DJWS (...) 2014-03-14 16:19:00

如果是bfs/ids的話那麼你應該是人工智慧的課程？這樣的話應該就不會用到dijkstra了 dijkstra是圖論的東西

作者: soheadsome (師大狗鼻哥) 2014-03-15 02:17:00

沒錯是ai的課

繼續閱讀

Re: [問題] 大地排關問題eieio Re: [問題] 大地排關問題bleed1979 Re: [問題] 大地排關問題tkcn Re: [問題] 大地排關問題bleed1979 [問題] 大地排關問題qaz00123 [問題] 畫面最佳比率dlikeayu Re: [問題] 不能跟一樣的人坐在一起的問題KOFXI [問題] 不能跟一樣的人坐在一起的問題entryword [問題] 一元四次方程式sayitagain [問題] 最佳分配的問題jimshsu