图的搜索：

　　无信息搜索（盲目搜索）：深度优先搜索DFS、宽度优先搜索BFS、有界深度搜索DLS、等代价搜索UCS（BFS的扩展版本）、迭代加深搜索IDS

　　有信息搜索（启发式搜索）：A算法，A*算法

图的搜索所需的数据结构：

　　OPEN表：记录还没有扩展的点

　　CLOSED：记录已经扩展的点

　　节点结构中需要有指向父节点的指针：记住从目标返回的路径

启发式搜索：

　　引入启发式函数heuristic function：h(n)。利用h(n)来决定节点的扩展顺序。

估价函数evaluation function ： f(n)

对f的不同定义导致了不同的搜索策略。

 

g*(n)：开始S到某n点的最佳路径的实际代价

h*(n)：从这个n点到目标goal的最小代价路径的代价

f*(n) ：g*(n)+f*(n)

f(n)：希望估价函数，是f*(n)的一个估计f(n)=gn+hn(开始缩写偷懒)

         gn是g*n的估计，hn是h*n的估计

gn从各个弧加起来的最小值给出。gn>=g*n

hn依赖于各个领域的启发信息

A算法：fn=hn+gn

          如果所有的hn<=h*n称hn是h*n的下界

A*算法：采用下界hn为启发函数的A算法，当hn=0，A*变成有序搜索算法