与或树的搜索策略 搜索的完备性与效率.ppt

与或树的搜索策略_搜索的完备性与效率 与/或树的搜索策略
一般搜索过程
宽度优先搜索
深度优先搜索
博弈树搜索
-剪枝技术
可解节点与不可解节点
在与/或树上执行搜索过程，目的在于表明起始节点有解或无解。
可解节点的递归定义为：
终叶节点是可解节点，直接和本原问题相关连；
非终叶节点含有“或”子节点时，只要子节点中有一个是可解节点，该非终叶节点便为可解节点；
非终叶节点含有“与”子节点时，只有子节点全为可解节点时，该非终叶节点才是可解节点。
注意：终叶节点一定是端节点，但端节点不一定是终叶节点。
由可解子节点来确定先辈节点是否为可解节点的过程称为可解标示过程。
由不可解子节点来确定先辈节点是否为可解节点的过程称为不可解标示过程。
不可解节点的定义为：
关于可解节点的三个条件全部不满足的节点，称为不可解节点；
一般搜索过程流程
(1)把原始问题作为初始节点S，并把它作为当前节点。
(2)应用分解或等价变换算符对当前节点进行扩展。
(3)为每个子节点设置指向父节点的指针。
(4)选择合适子节点作为当前节点，反复执行第(2)、(3)步，在此期间多次调用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点为止。
由这个搜索过程所形成的节点和指针结构称为搜索树。
搜索中，通过可解标示过程确定初始节点是可解的，则由此初始节点及其下属的可解节点就构成了解树。
提高与/或树搜索效率的两个性质
与/或搜索有两个特有性质，可用来提高搜索效率：
如果已确定某个节点为可解节点，其不可解的后裔节点不再有用，可从搜索树中删去；
若已确定某个节点是不可解节点，其全部后裔节点都不再有用，可从搜索树中删去。但当前这个不可解节点还不能删去，在判断其先辈节点的可解性时还要用到。
宽度优先搜索算法流程
基本思想：先产生的节点先扩展，先进先出。
把初始节点S放入OPEN表。
把OPEN表中的第一个节点(记为节点n)取出放入CLOSLD表。
如果n可扩展，则做下列工作：
①扩展n，将其子节点放入OPEN表的尾部，并为每个子节点配置父指针，以备标示过程使用。
②考察子节点中是否有终叶节点。若有，则标示这些终叶节点为可解节点，并应用可解标示过程对其先辈节点中的可解节点进行标示。若S也被标示为可解节点，就得到了解树，搜索成功，退出搜索过程；若无法确定S可解，则从OPEN表中删去具有可解先辈的节点。
③转步骤2。
宽度优先搜索算法流程
4. 如果n不可扩展，则做下列工作：
①标示n为不可解节点。
②应用不可解标示过程对n的先辈节点中不可解的节点进行标示。如果S被标示为不可解节点，则搜索失败，原始问题无解，退出搜索过程；如果无法确定S不可解，则从OPEN表中删去具有不可解先辈的节点。
③转步骤2。
宽度优先搜索算法流程
宽度优先搜索算法流程
例：与/或树的宽度优先搜索
例：设有如图所示的与/或树，其中t1，t2，t3，t4均为终叶节点，A和B是不可解的端节点。
试采用与/或树的宽度优先搜索法对该图进行搜索。
例：与/或树的宽度优先搜索
Step1：扩展1号节点，得到2、3号节点。
2、3都不是终叶节点，接着扩展2。
OPEN
CLOSED
1
2,3
1
3
2,1