关于本章

graph search algorithm是非常之多的，因此需要首先建立起一个完整的视图，本章主要参考如下两篇文章:

1、umn CSci 4511w: Class Notes on Search

2、washington Search: Cost & Heuristics

3、wikipedia graph and tree search algorithm

参见下面的"wikipedia graph and tree search algorithm"段

Relation-based algorithm model

graph search algorithm是典型的Relation-based algorithm model（参见Relation-structure-computation\Computation\index.md）。

wikipedia graph and tree search algorithm

Graph and tree search algorithms
α–β A* B* Backtracking Beam Bellman–Ford Best-first Bidirectional Borůvka Branch & bound BFS British Museum D* DFS Dijkstra Edmonds Floyd–Warshall Fringe search Hill climbing IDA* Iterative deepening Johnson Jump point Kruskal Lexicographic BFS LPA* Prim SMA*
Listings
Graph algorithms Search algorithms List of graph algorithms
Related topics
Dynamic programming Graph traversal Tree traversal Search games

Classification

分类方法是参考的：umn CSci 4511w: Class Notes on Search “3. classes of search algorithms.”。

uninformed VS informed

uninformed 即 Blind search

informed 即 Heuristic search

类别	Example	说明
Blind search	- Depth first search (DFS) - Breadth first search (BFS) - Iterative deepening depth-first search (IDS)
Heuristic search	- Best first search - Uniform cost search (UCS) - Greedy search - A* - Iterative Deepening A* (IDA*) - Beam search - Hill climbing

上述example是参考的washington Search: Cost & Heuristics。

local VS global

类别	Example	说明
local	- greedy - hill-climbing
global	- uniform cost - A*

与此相关的是：局部最优与全局最优。

systematic VS stochastic

类别	Example	说明
systematic	- depth-first - A*
stochastic	- genetic algorithms（遗传算法）