關於此實驗
地圖導航、機器人和電玩遊戲都要解決同一個問題：找到從起點到目標點成本最低的路線。在這個網格中，沿道路前進一步的成本為 1，進入泥地一步的成本為 5，而牆壁無法穿越。觀察三種經典演算法如何從 S 向外擴展。廣度優先搜尋統計步數，不考慮泥地；戴克斯特拉演算法總是優先探索成本最低的格子；A* 則會加入對剩餘距離的估算，從而直奔目標。繪製自己的地圖，比較每種演算法需要完成多少工作。
學習目標
- 將地圖表示為一個由相鄰格子連接而成的圖，並為每一步設定成本
- 描述廣度優先搜尋如何按步數相同的環狀層級進行探索
- 說明為什麼每一步的成本不同時，Dijkstra 仍能找到成本最低的路徑
- 說明 A* 的啟發式如何在不錯過最佳路徑的情況下，減少探索的格子數量
- 比較各演算法找到的路徑成本，以及它們所需的工作量
使用方法
- 1選擇 BFS 並按下「搜尋」。它找到的路徑會經過泥地嗎？在表格中查看路徑成本。
- 2選擇 Dijkstra 並再次搜尋。比較它與 BFS 找到的路徑及其成本。
- 3選擇 A*。它的路徑成本和 Dijkstra 相同嗎？它少探索了多少個格子？
- 4觀察搜尋過程中的藍色邊界。Dijkstra 和 A* 的邊界形狀有什麼不同？
- 5畫一堵牆，封住泥地周圍的道路。哪個演算法會改變路徑？為什麼？
- 6按下「清除地圖」，然後把 S 和 G 拖遠。沒有障礙物時，每種演算法會探索多少個格子？
模型
假設
- 只能向上、向下、向左或向右移動。進入道路格子的代價為 1，進入泥地格子的代價為 5；牆壁格子無法進入。
- BFS 在搜尋時將每一步的代價都視為 1，因此會找到步數最少的路徑。表中該路徑的代價是真實代價，其中包括泥地的代價。
- 如果兩個格子的優先順序相同，先加入的格子會先被探索，因此在相同地圖上每次執行的探索順序都完全相同。
- 一旦目標從前沿集合中取出，搜尋就會停止，因為此時已經確定到達目標的最低代價。
在課堂上試試這個實驗
- Q1為什麼 BFS 使用的步數較少，找到的路徑代價卻可能高於 Dijkstra？
- Q2如果所有格子都是道路，BFS 和 Dijkstra 找到的路徑代價會相同嗎？為什麼？
- Q3如果估算值 h 是曼哈頓距離的十倍，A* 會有什麼變化？
- Q4為什麼目標位於開闊區域時，A* 探索的格子較少；而在迷宮中，探索的格子數卻與 Dijkstra 大致相同？
- Q5衛星導航能在不到一秒的時間內，為穿越一個擁有數百萬個道路交叉口的國家找到快速路線。這個實驗中的哪些概念讓這一切成為可能？
常見問題
哪種演算法最好？
這取決於問題。如果每一步的成本都相同，BFS 簡單且正確。成本各不相同時則使用 Dijkstra。如果能妥善估算到目標的距離，A* 就能在探索較少格子的情況下，得出與 Dijkstra 相同的結果。
什麼是邊界集合（frontier）？
前沿是已抵達但尚未探索的格子集合。每種演算法每次都會從前沿取出一個格子；它們之間的差異僅在於決定下一步取出哪個格子的規則。
這些演算法能處理負成本嗎？
Dijkstra 和 A* 假設每一步的成本都不是負數。如果存在負成本，先前已確定的格子之後可能會出現成本更低的路線，因此需要使用 Bellman-Ford 等其他演算法。