3 与/或树的深度优先搜索
搜索过程
(1)把初始节点S0放入OPEN表
(2)把OPEN表中的第一个节点（n)取出放入CLOSE表
(3)如果节点n的深度大于深度界限，则转第(5)步的第<1>点
(4)如果节点n可扩展，做
<1>扩展节点n，将其子节点放入OPEN表的首部，为每个子节点配置指向父节点的指针，以备标示过程使用
<2> 考察这些子节点中是否有终止节点。有，标示这些终止节点为可解节点，应用可解标示过程对其先辈节点中的可解节点进行标示。如果初始节点S0也被标示为可解节点，搜索成功，退出。如果不能确定S0为可解，则从OPEN表中删去具有可解先辈的节点<3>转(2)
(5)如果节点n不可扩展，做
<1>标示节点n为不可解节点
<2>应用不可解标示过程对节点n的先辈节点中不可解的节点进行标示。如果S0也标示为不可解，搜索失败，退出。如果不能确定S0为不可解节点，从OPEN表中删除具有不可解先辈的节点。 <3>转(2)

点击看大图及详解
 

4 与/或树的有序搜索
根据代价决定搜索路线的方法称为与/或树的有序搜索
(1)解树的代价
<1>计算节点x代价
if x是终止节点，则定义节点x的代价h(x)=0
if x是“或节点”，y1,y2…yn是它的子节点，节点x的代价为h(x)=min{c(x,yi)+h(yi)}
if x是“与”节点，则节点x的代价为：
和代价计算：h(x)=?(c(x,yi)+h(yi))
最大代价计算：h(x)=max{c(x,yi)+h(yi)}
if x不可扩展，且又不是终止节点，h(x)=无穷大
<2>解树的代价
计算结点代价
推出父节点代价，直到S0代价
S0的代价为解树代价
例 与/或树如下，含两棵解树，一棵解树由S0,A,t1,t2组成，另一棵解树由S0,B,D,G,t4,t5组成。t1,t2,t3,t4,t5为终止节点，E,F为端节点，其代价为无穷大，边上的数字为该边的代价。

点击看大图及详解

 
(2)希望树
根据问题本身提供的启发性信息定义一个启发函数，由此启发函数估标出子节点yi的代价h(yi），然后再按和代价或最大代价算出节点x的代价值h(x)，利用h(x)可计算x的父节点、祖父节点，直到S0各先辈节点的代价h，自下而上逐层推算出来。
有序搜索的目的是求出最优解树，每次选择扩展的节点时，都应选择有希望成为最优解树的一部分的节点进行扩展—希望树，希望树是不断变化的，但它包含S0，是对最优解树近根部分的某种估计
**希望树的定义：
初始节点S0在希望树T中
如果节点x在希望树T中，则一定有
如果x是具有子节点y1,y2…yn的或节点，则具有 min{c(xi,yi)+h(yi)}值的那个子节点yi也应在T中
如果x是“与”节点，则它的全部子节点都应在T中