Tree Search（樹狀搜尋)

一、什麼是 Tree Search（樹狀搜尋）？

在人工智慧（AI）與演算法中，許多問題都可以表示成一棵樹(圖一)：

        起點(A)
       /   |   \
      B    C    D
     /|\   |   / \
    E F G  H  I  J

每個節點(Node)代表一種狀態(State)。

例如：

• 迷宮中的位置
• 棋局的盤面
• 路徑規劃中的城市
• 遊戲中的決策

搜尋演算法的目的：

從起點找到目標節點（Goal Node）

---

二、Breadth First Search (BFS)

核心思想

先搜尋離起點最近的節點。

一層一層往外擴展。

Level 0: A

Level 1: B C D

Level 2: E F G H I J

搜尋順序：

A
B C D
E F G H I J

圖一結果：

A → B → C → D → E → F → G → H → I → J

---

使用資料結構

Queue（佇列）

FIFO：

First In First Out
先進先出

例如：

Queue:

A

取出A
加入B,C,D

Queue:
B,C,D

---

BFS特性

優點

如果邊權重相同：

BFS一定找到最短路徑。

缺點

需要大量記憶體。

假設每個節點有10個子節點：

深度5：

10^5 = 100000

需要保存很多節點。

---

時間複雜度

O(V + E)

V = Vertex（節點數）

E = Edge（邊數）

---

三、Depth First Search (DFS)

核心思想

一路往下走到底。

不能走才回頭。

A
|
B
|
E

然後：

A
|
B
|
F

---

搜尋順序

圖一結果：

A
B
E
F
G
C
H
D
I
J

---

使用資料結構

Stack（堆疊）

LIFO

Last In First Out
後進先出

例如：

push(B)
push(C)
push(D)

pop()
=> D

---

DFS特性

優點

記憶體需求小。

只需保存：

目前路徑

即可。

---

缺點

可能找到很差的解。

例如：

A
├── Goal
└── 巨大子樹

DFS可能先跑完整個巨大子樹。

---

時間複雜度

O(V+E)

---

四、Best-First Search

為什麼需要它？

BFS和DFS都很「盲目」。

不知道哪條路比較接近目標。

因此加入：

Heuristic
啟發函數

---

Heuristic h(n)

代表：

目前節點到目標的預估距離

例如：

Node	h(n)
B	1
C	6
D	3

表示：

B 最有希望
D 次之
C 最差

---

選擇方式

每次選：

h(n) 最小

的節點。

---

例子

Open:
B(1)
C(6)
D(3)

選：

B

因為：

1 最小

---

搜尋順序

圖一結果：

A
B
E
F
G
D
I
J

---

優點

搜尋速度快。

---

缺點

可能不是最佳解。

因為：

只看 h(n)

不看已經花費的成本。

---

五、A* Search

A* 是人工智慧最重要的搜尋演算法之一。

例如：

• Google Maps
• 遊戲尋路
• 機器人導航

都可能使用A*或其變種。

---

A* 的核心公式

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

---

g(n)

已經走過的成本

例如：

A → D

成本=4

則：

g(D)=4

---

h(n)

預估剩餘成本

例如：

D → Goal

估計=3

則：

h(D)=3

---

f(n)

總評分：

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

例如：

D

g=4
h=3

f=7

---

範例

圖一中的計算：

B:
f=5+1=6

C:
f=2+6=8

D:
f=4+3=7

因此選：

B

---

搜尋順序

A
B
D
J

---

為何A*這麼強？

Best-First：

只看 h(n)

A*：

看 g(n)+h(n)

因此兼顧：

• 已花費成本
• 未來預估成本

---

A*最佳性條件

若：

h(n)
永遠不高估真實距離

(admissible heuristic)

則：

A*
一定找到最佳解

---

六、四種演算法比較

項目	BFS	DFS	Best-First	A*
使用結構	Queue	Stack	Priority Queue	Priority Queue
考慮成本	否	否	h(n)	g(n)+h(n)
最短路徑	是(無權圖)	否	不一定	是(條件成立)
記憶體	高	低	中	中~高
搜尋速度	中	快/慢不一定	快	很快
AI應用	少	少	中	非常多

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.