与或树的搜索策略_搜索的完备性与效率VIP专享

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