AI 摘要

搜尋演算法概念

Uninformed Search（無資訊搜尋）

盲目遍歷狀態空間，無任何篩選決策。

Breadth-First Search (BFS)

逐層擴展所有節點，保證最短路徑（等成本前提）。記憶體消耗大

路遍歷方式如上圖所示，從起點優先考慮鄰近點，此時演算法需要開始紀錄每一個鄰近遍歷過程，才能比較出最短徑

時間複雜度： $O(b^d)$
空間複雜度： $O(b^d)$

（$b$ 為分支因子，$d$ 為最淺解之深度）

Depth-First Search (DFS)

沿路徑深入至終點或死路後回溯。記憶體需求低，不保證最短路徑

時間複雜度： $O(b^m)$
空間複雜度： $O(bm)$

（$m$ 為搜尋樹最大深度）

---

Informed Search（資訊搜尋 / 啟發式搜尋）

利用估計函數衡量節點距離目標的代價，提高搜尋效率。

Greedy Best-First Search

每次擴展啟發值最低的節點，快速但不保證最短路徑。

$f(n) = h(n)$

只依賴啟發資訊，忽略實際成本。

---

A* Search

結合實際成本與啟發值選擇節點。若 $h(n)$ 可接受且一致，保證最短路徑。

$f(n) = g(n) + h(n)$

其中 $g(n)$ 為已行進成本，$h(n)$ 為到目標的估計成本。

• 適用：最短路徑、遊戲 AI、路徑規劃

---

Optimization Search（最佳化 / 隨機搜尋）

Hill-Climbing

每次選擇鄰近節點中的最優解。簡單快速，但易陷入局部最優。

• 適用：小型優化問題或局部改進

---

Simulated Annealing

引入隨機性，以一定機率接受較差解，模擬金屬退火過程。可跳出局部最優。

$P(\Delta E) = e^{-\Delta E / T}$

其中 $T$ 為溫度（退火進度），需設定溫度排程。

• 適用：組合優化問題（排程、旅行推銷員問題）