一、期末專題報告架構

題目：基於搜尋演算法的智能迷宮逃脫 AI
英文題目：Intelligent Maze Escape AI Based on Search Algorithms

摘要（Abstract）

本專題旨在設計一個能夠自動生成迷宮並使用人工智慧搜尋演算法進行路徑規劃的系統。
系統以 C 語言實作，包含三種主要演算法：深度優先搜尋（DFS）、廣度優先搜尋（BFS）、以及A*。
透過比較各演算法在搜尋成本、路徑長度與執行時間上的表現，分析其優缺點與適用情境。
實驗結果顯示，A* 能在最短時間內找到最優路徑，而 BFS 雖能保證最短路徑但成本較高，DFS 則雖快速但結果不一定最短。
本研究展示了經典搜尋演算法於路徑規劃問題中的實際應用價值。

1. 研究背景與動機

迷宮問題是一個典型的路徑搜尋問題，常被用來測試人工智慧搜尋策略的效率與準確性。
在真實應用中，如自動駕駛、機器人導航與遊戲 AI，都需要有效率的路徑規劃機制。
因此，本專題希望透過迷宮逃脫遊戲的形式，實作並比較多種搜尋演算法的效能與特性。

2. 系統設計與演算法原理
   2.1 系統架構圖
   +-------------------+
   | Maze Generator | ← DFS 生成隨機迷宮
   +---------+---------+
   |
   v
   +-------------------+
   | Search Algorithms | ← DFS / BFS / A*
   +---------+---------+
   |
   v
   +-------------------+
   | Result Analyzer | ← 比較成本與路徑長度
   +-------------------+

2.2 迷宮生成演算法

使用 遞迴 DFS 生成隨機迷宮。

確保每個位置都可到達，避免死區。

2.3 搜尋演算法原理
演算法 特點 優點 缺點
DFS 深度搜尋、遞迴簡單 速度快 不保證最短路徑
BFS 廣度搜尋、逐層展開 能保證最短路徑 記憶體需求高
A* 加入啟發式函數（曼哈頓距離） 高效率、最短路徑 實作較複雜
2.4 啟發式函數（A*）
h(x,y)=∣x−xgoal∣+∣y−ygoal∣
即曼哈頓距離，用來估算節點到終點的最短距離。

3. 系統實作與模組化設計
   /maze_ai/
   ├── main.c // 主程式：介面與流程控制
   ├── maze_gen.c / .h // 迷宮生成模組
   ├── search.c / .h // 各搜尋演算法實作
   ├── display.c / .h // 文字介面顯示迷宮
   ├── analysis.c / .h // 效能統計與結果輸出
   └── result.txt // 搜尋結果紀錄

4. 實驗與結果分析
   4.1 實驗環境

CPU: Intel i5

編譯器: GCC

迷宮大小: 20×20

4.2 結果範例
演算法 擴展節點數 路徑長度 執行時間(ms)
DFS 875 72 2.51
BFS 1012 58 3.04
A* 243 58 0.91
4.3 分析

A* 能在最短時間內找到與 BFS 相同的最短路徑。

DFS 雖快但路徑偏長。

搜尋深度與節點擴展量呈正比。

5. 結論與未來展望

本專題透過 C 語言實作了迷宮生成與多種搜尋演算法，成功展示 AI 搜尋策略在路徑規劃問題中的應用。
未來可擴展方向包括：

加入圖形化介面或動畫顯示搜尋過程。

延伸至多終點或多智能體的情境。

結合強化學習改進搜尋策略。