第五章

与/或树的搜索
--盲目搜索
----*广度优先搜索
----*深度优先搜索
--启发式搜索
----*有序搜索
----*博弈树搜索
1 与/或树的一般搜索过程
(1)概念
-*与节点：只有其子节点全部为可解节点时，它才为可解节点
-*或节点：只有其子节点全部为不可解节点时，它才为不可解节点
-*可解标示过程：由可解子节点来确定父节点，祖父节点等为可解节点的过程称为可解标示过程
-*不可解标示过程：由不可解子节点来确定其父节点、祖父节点等为不可解节点的过程称为不可解标示过程

(2)与/或树的一般搜索过程
<1>把原始问题作为初始节点S0，并把它作为当前节点
<2> 应用分解或等价变换算符对当前节点进行扩展
<3> 为每个子节点设置指向父节点的指针
<4> 选择合适的子节点作为当前节点，反复?-?步，多次调用可解标示过程和不可解标示过程，直到确定初始节点为可解或不可解节点为止可解与不可解标示过程都是由下而上进行的

（3）全局择优搜索
基本思想：每次总是从OPEN表的全体节点中选择一个估价值最小的节点搜索过程
<1> OPEN:=S0 ，f:=f(S0)
<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
<5> EXPAND(n)->M(mi), f(xi):=d(xi)+h(xi),mi^->n,ADD(mi,OPEN),(OPEN)?
<6> GO LOOP

2 与/或树广度优先搜索:先产生的节点先扩展,搜索过程
<1>OPEN:=S0
<2>LOOP：n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSE)
<3> IF EXPAND(n) THEN EXPAND(n)->M{mi},ADD(mi,OPEN),mi^->n
IF mi=END ,mi可解，对父、祖父等先辈节点中的可解节点进行标示，若S0可解节点，得到解树，搜索成功，退出；若不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点,GO LOOP
<4> IF EXPAND(n)=( ) THEN 标示节点n为不可解节点
应用不可解标示过程对节点n的先辈节点中不可解的节点进行标示，如果S0也被标示为不可解节点，则搜索失败，原问题无解，退出。如果不可能确定S0为不可解节点，则从OPEN表中删除具有不可解的先辈节点
GO LOOP
例与/或树如下，节点按图中所标注的顺序号进行扩展，其中标有t1,t2,t3,t4的节点均为终止节点，A和B为不可解节点

点击看大图及详解