《数据结构域算法设计-AI_3 搜索技术》由会员分享，可在线阅读，更多相关《数据结构域算法设计-AI_3 搜索技术（81页珍藏版）》请在金锄头文库上搜索。
1、第三章 搜索技术,教学内容： 1、搜索的概念及种类2、盲目搜索策略 3、启发式搜索策略,第三章 搜索技术,教学重点：宽度优先搜索、深度优先搜索及代价树的搜索算法，最佳优先搜索算法。 教学难点：利用各种搜索算法解决实际问题，尤其是估价函数的选取。,第三章 搜索技术,上一章我们学习了知识的表示，接下来要研究的是实现问题求解的过程，采用的基本方法包括搜索和推理。本章介绍搜索技术，将讨论问题求解的搜索原理及常用的搜索技术。,3.1 搜索的概念及种类,3.1.1 搜索的概念根据问题的实际情况，按照一定的策略和规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的最优的推理路线的过程称为搜索。搜
2、索包含两层含义，一层含义是从问题的初始状态到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。,3.1 搜索的概念及种类,3.1.2 搜索的种类搜索分为盲目搜索和启发式搜索。盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。我们将学习的宽度优先搜索和深度优先搜索，属于盲目搜索方法。把利用启发信息的搜索方法叫做启发式搜索。这种搜索技术一般需要某些有关具体问题领域的特性的，与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息，把此种信息叫做启发信息。,3.2 盲目搜索策略,3.2.1 图搜索策略可把图搜索策略看成一种在图中寻找路径的
3、方法。我们已经介绍过有关图的表示方法。图中的节点对应于状态，而连线对应于操作符。,3.2 盲目搜索策略,在介绍图搜索策略之前，让我们来看一个例子。 例：从某张姓家族的四代中找张A的后代且其寿命为X的人。 张A：寿命47，有儿子张B1、张B3、张B2 张B1：寿命77，有儿子张C1、张C2 张B3：寿命52，有儿子张D1 张B2：寿命65，有儿子张E1、张E2 张F1：寿命32 张G1：寿命96 张C2：寿命87，有儿子张F1 张D1：寿命77，没有儿子 张E1：寿命57，有儿子张G1,3.2 盲目搜索策略,张E2：寿命92，有儿子张H1 张C1：寿命27，没有儿子 张H1：寿命51 若X=57
4、，下面讨论一种可通用的图搜索策略求解此问题。 如果是一个N代的家族表中找其寿命为X的人，我们最可能用的手工方法是从家族表的开始往下，本例中还要求所找的人是某人的后代，就比较复杂了。如果用图来表示，就很容易了。图中把姓氏省去，每个成员的后代按例子中给出名字的先后顺序。图示为：,3.2 盲目搜索策略,图 3.1 用图表示方法的家族表,3.2 盲目搜索策略,图搜索算法中的几个重要名词 1）已扩展节点和未扩展节点：所谓扩展就是用适合的算符对某个节点进行操作生成一组后继节点，扩展过程实际就是求后继节点的过程；所以，对状态空间图的某个节点，如果求了它的后继节点，则此节点为已扩展的节点；而尚未求出它的后继节
5、点的节点称为未扩展节点。未扩展节点存入OPEN表中，已扩展节点存入CLOSED表中。,3.2 盲目搜索策略,2）OPEN表和CLOSED表的数据结构如下图所示：,OPEN表,CLOSED表,3.2 盲目搜索策略,图搜索(GRAPHSEARCH)的一般过程如下： (1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中（简称OPEN表）。 (2) 建立一个叫做CLOSED的已扩展节点表（简称CLOSED表），其初始为空表。 (3) LOOP：若OPEN表是空表，则失败退出。 (4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节
6、点n，它是CLOSED表中节点的编号。 (5) 若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。,3.2 盲目搜索策略,(6) 扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。 (7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方
7、向。 (8) 按某一任意方式或按某个探试值，重排OPEN表。 (9) GO LOOP。,3.2 盲目搜索策略,此过程生成一个明确的图G(称为搜索图)和一个G的子集T(称为搜索树)，树T上的每个节点也在图G中。搜索树是由第7步中设置的指针来确定的。G中的每个节点(除S外)都有一个只指向G中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。,图(网络),搜索树,3.2 盲目搜索策略,3.2 盲目搜索策略,图搜索方法的分析： 图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨
8、论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。,3.2 盲目搜索策略,3.2.2 宽度优先搜索回顾上一节的寻找寿命为X的人的例子，如果搜索时，从节点A开始，对他的三个儿子按从左至右搜索，然后对他的所有孙子按从左至右搜索，依此下去。这种搜索方式就是宽度优先搜索。 宽度优先搜索
9、(breadth-first search)的定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。如图3.3所示：,3.2 盲目搜索策略,从图可见，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。,图3.3 宽度优先搜索示意图,3.2 盲目搜索策略,宽度优先搜索算法如下： (1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果OPEN是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。 (4) 扩展节点n。如果没有
10、后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。,3.2 盲目搜索策略,3.2 盲目搜索策略,宽度优先搜索方法分析： 宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远
11、不会终止)。,3.2 盲目搜索策略,例：利用宽度优先搜索求八数码难题所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：,3.2 盲目搜索策略,宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止)。 搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序(按顺时针方向移动空格)。图中最后一个节点是目标节点。,3.2 盲目搜索策略,图 3.5 八数码难题的宽度优先搜索树,3.2 盲目搜索策略,3.2 盲目搜索策略,3.2.
12、3 深度优先搜索另一种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。在深度优先搜索中，我们首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。,3.2 盲目搜索策略,图3.6深度优先搜索示意图,3.2 盲目搜索策略,我们定义节点的深度如下： (1) 起始节点(即根节点)的深度为0。 (2) 任何其它节点的深度等于其父辈节点深度加上1。 首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能
13、小。,3.2 盲目搜索策略,对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。,3.2 盲目搜索策略,含有深度界限的深度优先搜索算法如下： (1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。 (2) 如果OPEN为一空表，则失败退出。 (3) 把第一个节点(节
14、点n)从OPEN表移到CLOSED表。 (4) 如果节点n的深度等于最大深度，则转向(2)。 (5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。 (6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。,3.2 盲目搜索策略,3.2 盲目搜索策略,例：按深度优先搜索生成的八数码难题搜索树，我们设置深度界限为5。 图3.8绘出了搜索树，粗线条的路径表明含有5条应用规则的一个解。从图可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，然后再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最后两步
15、有差别的那些路径，等等。,3.2 盲目搜索策略,3.2 盲目搜索策略,3.2.4 等代价搜索宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。在等代价搜索算法中，不是沿着等长度层次进行的扩展，而是沿着等代价路径层次进行的扩展。,3.2 盲目搜索策略,符号的说明： 起始节点记为S； 从节点i到它的后继节点j的连接弧线代价记为c(i,j)；从起始节点S到任一节点i的路径代价记为g(i)；则g(j) g(i) c(i,j) 。在搜索树上，我们假设g(i)也是从起始节点S到节点i的最少代价路径上的代价；等代价搜索方法以g(
16、i)的递增顺序扩展节点。,3.2 盲目搜索策略,等代价搜索方法以g(i)的递增顺序扩展其节点，其算法如下： (1) 把起始节点S放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解;否则令g(S)=0。 (2) 如果OPEN是个空表，则没有解而失败退出。 (3) 从OPEN表中选择一个节点i，使其g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点i(要是有目标节点的话)；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。 (4) 如果节点i为目标节点，则求得一个解。 (5) 扩展节点i。如果没有后继节点，则转向第(2)步。 (6) 对于节点i的每个后继节点j，计算g(j)=g(i)+c(i,j)，并把所有后继节点j放进OPEN表。提供回到节点i的指针。 (7) 转向第(2)步。,
