迷宮搜索算法的比較研究

摘要：研究面向搜救的應用，將事故環境抽象為一個迷宮，通過仿真實驗比較研究了深度優先搜索算法和三種不同啟發式函數的A^*算法在Perfect迷宮中的應用，并分別將深度優先搜索算法和A^*算法用于實際迷宮中進行實現與比較。在實驗中，迷宮環境對機器人是未知的，而由于迷宮環境的特殊性——未知的迷宮環境中很少有不會碰撞的路徑，從而增加了機器人搜索的難度。通過仿真實驗對比了不同啟發式函數的A^*算法與深度優先搜索算法的性能，最后得出在迷宮搜索中A^*算法要優于深度優先搜索算法；同時，在實際迷宮中實現了深度優先搜索算法與A^*算法的搜救應用。