經典算法研究：A*、Dijkstra、雙向BFS尋路性能可視化對比

理論分析再詳細，不如一張動圖直觀。本文採用同一張網格地圖，對比五種算法的搜索覆蓋範圍、路徑長度、展開節點數，讓優劣一目了然。

對比算法陣容

1. A* (曼哈頓距離)：h=|dx|+|dy|，四方向移動最優。
2. A* (歐氏距離)：h=√(dx²+dy²)，任意角度移動可採納。
3. A* (切比雪夫距離)：h=max(|dx|,|dy|)，八方向移動最優。
4. Dijkstra：h=0，等價均勻擴展。
5. 雙向BFS：從起點終點同時擴展，相遇即停。

三大測試場景

場景一：起終點水平對齊，無障礙

觀察：三種A*直奔目標，覆蓋極窄；Dijkstra呈圓形擴展，覆蓋面積大；雙向BFS兩側擴展，中間相遇，覆蓋介於兩者間。

場景二：起終點斜向對齊，無障礙

觀察：切比雪夫A*完美貼合斜向，展開最少；曼哈頓A*呈鋸齒狀但仍遠優於Dijkstra；歐氏A*介於兩者間。

場景三：多重障礙物阻擋，需繞行

觀察：障礙物迫使所有算法擴展更多節點，但A*系列仍明顯聚焦於通道方向；Dijkstra與雙向BFS幾乎淹沒整張圖。

性能總結表

核心結論

1. A* 碾壓 Dijkstra/BFS：優秀啟發函數能將搜索空間指數級壓縮。
2. 啟發函數選擇決定生死：切比雪夫 > 歐氏 > 曼哈頓（八方向地圖）；曼哈頓 = 切比雪夫（四方向地圖）。
3. 雙向BFS 是無權圖的折中方案：無啟發信息時優於Dijkstra，但不如A*。
4. 工程建議：有地圖幾何信息 → A*；無幾何信息但邊權非負 → Dijkstra；無權圖 → 雙向BFS。

可視化代碼已開源於GitHub，歡迎自行修改地圖、啟發函數、移動規則，親自驗證結論。