《人工智能及其应用》第3章搜索技术.pptx

第3章 搜索技术;3.1 搜索的概念;3.1.1 基本概念;3.1.1 基本概念; 解决组合爆炸问题的方法实际上就是选用好的搜索策略，使得只需搜索状态空间中很小的部分就能找到解。通过以上分析，状态空间、搜索空间和解路径的关系如下图所示。; 通常，设计一个具体搜索策略需要考虑如下几个问题：首先，问题有解时，否是一定能找到解；其次，当搜索到解时，找到的是否为最佳解；再次，搜索过程是否能终止运行或是否会陷入一个死循环；最后，搜索的时间与空间复杂性如何或搜索的效率如何。 ;3.1.2 搜索的分类;3.2 状态空间搜索 ;3.2.1 状态空间搜索的一般过程; (1) 上述过程是状态空间搜索的一般过程，具有通用性。在此之后讨论的各种搜索策略都可看作是它的一个特例。各种搜索策略的主要区别是对OPEN表中节点排序的准则不同。 (2) 一个节点经一个操作算子操作后一般只生成一个子节点，但对一个节点可适用的操作算子可能有多个，此时就会生成一组子节点。在这些子节点中可能有些是当前扩展节点的父节点、祖父节点，此时不能把这些先辈节点作为当前扩展节点的子节点。 (3) 一个新生的子节点，它可能是第一次被生成的节点，也可能是最先前已作为其它节点的后继节点被生成过，而当前又作为另一个节点的后继节点被再次生成。那么将它作为哪个节点的后继节点呢？一般情况是由初始状态节点到该节点路径上的代价决定，即哪条路径代价小，则它就作为该路径上的相应节点的后继节点。 (4) 在搜索过程中，一旦某个被考察的节点是目标状态节点就得到了一个解。 (5) 由上述搜索过程可以看出，问题求解过程实际上就是搜索过程，问题求解的状态空间图是通过搜索逐步形成的，边搜索边形成，而且搜索每前进一步，就要检查一下是否达到了目标状态，这样就可以尽量少生成与问题求解无关的状态，即节省了存储空间，又提高了求解效率。 (6) 在搜索过程中CLOSED表中的节点及方向指针就构成了一个树，即搜索树。;3.2.2 盲目搜索策略; 1.广度优先搜索 总是把扩展当前节点后生成的子节点置于OPEN表的后端，将OPEN表作为队列表使用。广度优先搜索算法如下： ① 把初始状态节点S0放入OPEN表中； ② 若OPEN表为空，则搜索失败，退出。 ③ 取OPEN表中前面第一个节点放在CLOSED表中，令该节点为x并以顺序编号n； ④ 若目标状态节点Sg=x，则搜索成功，结束。 ⑤ 若x不可扩展，则转步②； ⑥ 扩展x，将其所有子节点配上指向x的指针依次放入OPEN表尾部，转步②。;; 广度优先搜索复杂度 假设一颗搜索树最大深度为d（对于树的节点的深度定义如下：根节点的深度为0；除根节点外，其它节点的深度是其父节点的深度加1。），每个节点的分枝因子都为b。广度优先搜索的时间复杂度与搜索的节点数目成正比。 对于d层搜索树，搜索的最小节点数目为; 2. 深度优先搜索 深度优先搜索总是把扩展当前节点后生成的子节点置于OPEN表的前端，将OPEN表作为栈使用。算法如下： ① 把初始状态节点S0放入OPEN表中； ② 若OPEN表为空，则搜索失败，退出。 ③ 取OPEN表中前面第一个节点放入CLOSED表中，令该节点为x并以顺序编号n； ④ 若目标状态节点Sg=x，则搜索成功，结束。 ⑤ 若x不可扩展，则转步②； ⑥ 扩展x，将其所有子节点配上指向x的返回指针依次放入OPEN表的首部，转步②。 ;图3-4 八数码游戏的深度优先搜索 ; 深度优先搜索复杂度 假设搜索树有深度为d，分枝因子为b。如果深度优先搜索在d层最左边找到了目标，则检查的节点数为(d+1)；而在最右边找到了目标，则检查了树种所有的节点，数目为 。所以，平均检查节点数目为两者求平均， 由此可知深度优先搜索的平均时间复杂度为 。; 3. 有界深度优先搜索 有界深度优先搜索的过程总体上是按深度优先搜索方式进行，但对搜索深度需要给出一个深度限制dm，当深度达到dm时，如果还未找到解，就停止对该分支的搜索，换到另外一个分支进行搜索。算法如下： ① 把S0放入OPEN表中，置S0的深度d(S0)=0； ② 若OPEN表为空，