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