5 代价树的广度优先搜索
边上标有代价（或费用）的称为代价树
用c(x1,x2)标是从父节点x1到子节点x2的代价
从初始节点s0到节点x的代价用g(x)表示
代价计算公式：g(x2)=g(x1)+c(x1,x2)
(1)基本思想：每次从OPEN表中选择节点往CLOSE表传送时，总是选择其代价为最小的节点。
(2)搜索过程
<1> OPEN:=S0,g(S0):=0
<2> LOOP:IF OPEN=( ) THEN EXIT(FAIL)
<3> n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSE)
<4> IF GOAL(n) THEN EXIT(SUCCESS)
<5> IF EXPAND(n)=( ) GO LOOP
<6> IF EXPAND(n)?M{mi},ADD(mi,OPEN),mi^->n,g(xj):=g(xi)+C(xi+xj),(OPEN)|,GO LOOP
例 五城市间的交通间路图，A是出发地，E是目的地，两城市间的交通费用（代价）如图中数字所示，求从A到E的最小路费用交通路线。

<1>从初始节点A开始，把与它直接相邻的节点作为它的子节点
<2>若一个节点已作为某节点的直系先辈节点时，就不能再作为这个节点的子节点
<3>图中除起始节点外，其它节点都可能要在代价树中出现多次，为区别之，用下标1，2，3....标出

点击图片看大图
 
6 代价树的深度优先搜索
(1)基本思想：代价树的深度优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入close表进行考察。代价树的深度优先搜索有可能进入无穷分支路径，因此它是不完备的。
(2)搜索过程
<1> OPEN:=S0
<2> LOOP IF OPEN=( ) THEN EXIT(FAIL)
<3> n:=FIRST(OPEN),ROMOVE(n,OPEN),ADD(n,CLOSE)
<4> IF GOAL(n) THEN EXIT(SUCCESS)
<5> IF EXPAND=( ) GO LOOP
<5> EXPAND(n)?M{mi},ADD(mi,OPEN),mi^->n,
g(xj):=g(xi)+C(xi,xj), (OPEN)|, GO LOOP
7 启发式搜索：要用到问题自身的某些特性信息，以指导搜索朝着有希望的方向前进。搜索效率高。
(1)启发性信息与估价函数
估价函数一般形式：f(x)=g(x)+h(x)
g(x):从S0到节点x已经实际付出的代价。指出了搜索的横向趋势、完备性好、但效率差。
h(x):是从节点x到目标节点sg的最优路径的估计代价称为启发函数
f(x):从S0经过节点x到达目标节点sg的最优路径的代价估计值，作用是估价OPEN表中各节点的重要性，决定OPEN表的次序。
g(x)和h(x)各占适当的比重
例 有如下结构的移动将牌游戏
B:代表黑色将牌
W:代表白色将牌
E:代表该位置为空
游戏规则：
将一个将牌移入相邻的空位置时，费用为一个单位
一个将牌至多可以跳过两个将牌进入空位置，其费用等于跳过的奖牌数加1。
要求：把所有的B移至所有的W的右边，计算h(x)
解：因为W左边的B越少越接近目标，用W左边的个数
作为h(x),h(x)=3(每个W左边B的个数的总和）
h(x)=3(2+2+3)=21