AI 筆記13 - Search演算法小整理

用Domain knowledge（heuristics) 來劃分

informed: Greedy search, A*, IDA*
uninformed: BFS, DFS, DLS, IDS, UCS。

DFS

把每個branch搜尋完，才會backtrack到sibling的branch。frontier包含了目前尚未explored的siblings:

IDS

把每個深度限制內的subtree搜尋完，才會搜尋下一個深度的subtree。每個深度限制內就是一次DFS：

BFS

BFS是layer (深度）based search，其實有點像是IDS，但是IDS深度限制內是DFS (用LIFO)，而BFS是FIFO，所以layer是自然形成的，不是透過depth limitation。

fringe裡面放的是下一層child nodes：

UCS

UCS是以true path cost當作explore的一句，所以也會形成layer-based search，但是這是search space中抽象概念上的layer(同樣cost的會形成一個layer)，在search graph上表現會是不規則的前進：

Layers vs Subtrees

BFS是layer-based search，意思就是同樣的depth的node會先被explored。

UCS也是layer-based search，layer的依據是 true path cost g

Greedy search也是layer-based search，layer的依據是heuristics h

A*也是layer-based search，layer的依據是 estimated cost f = g+h

IDS是subtree-based search，雖然同樣也是以depth當作explored順序，但單位是“subtree”，所以每次都會從root開始從新搜尋depth = d的subtree，每個subtree的搜尋方法卻是DFS (注意，會把整個subtree search完）。


IDA*是subtree-based search，每次搜尋f limit增加的“subtree”，每個subtree搜尋方法是一個A* search。