人工智能第五章

《人工智能第五章》由会员分享，可在线阅读，更多相关《人工智能第五章（68页珍藏版）》请在金锄头文库上搜索。

1、5.1 搜索的概念及种类 搜索是人工智能的一个基本问题，是推理不 可分割的一部分。一个问题的求解过程其实就是 搜索过程，所以搜索实际上就是求解问题的一种 方法。与搜索技术相对应的知识表示法一般有两 种：状态空间表示法、另一种是与/或树表示法。 第五章 状态空间搜索策略一搜索的概念 现实世界中的大多数问题都是非结构化问题，一 般不存在现成的求解方法来求解这样的问题，而只能 利用已有的知识一步一步的搜索着前进。在这一过程 中，所要解决的问题是如何寻找可利用的知识，即如1 1西南科技大学西南科技大学 信息工程学院信息工程学院何确定推理路线，才能使在付出尽量少的代价的 前提下把问题圆满解决。如果存在多

2、条路线可实现对问题求解，那就 又存在这样的问题 ，即如何从这多条求解路线中 ，选出求解代价最小的一条，以提高求解程序的 运行效率。 概念：根据问题的实际情况，按照一定的策略或规则 ，从知识库中寻找可利用的知识，从而构造出一条使 问题获得解决的推理路线的过程，称为搜索。 两层含义： 1)要找到从初始事实到问题最终答案的一条推理路线 ； 2)找到的这条路线是时间和空间复杂度最小的求解路 线。 2 2西南科技大学西南科技大学 信息工程学院信息工程学院二搜索的种类： 1盲目搜索（无信息搜索）在搜索过程中，只按预先规定的搜索控制策略 进行搜索，而没有任何中间信息来改变这些控制 策略，即问题本身的特性对搜

3、索控制策略没有如 何影响，使得搜索带有盲目性，效率不高。 缺点：如果碰到比较复杂的问题时，求解的效率 可能相当低。所以盲目搜索只用于解决比较简单 得问题。 2启发式搜索（有信息搜索）在搜索过程中，根据问题本身的特性或搜索过 程中产生的一些信息来不断地改变或调整搜索的方 向，使搜索朝着最有希望的方向前进，加速问题的 求解，并找到最优解。 3 3西南科技大学西南科技大学 信息工程学院信息工程学院启发式搜索由于考虑到问题本身的特性并利用这 些特性，从而使搜索求解的效率更高，更易于求解复 杂的问题。但并不是对所有的问题都能方便地抽取出 问题的相关特性和信息，因此尽管启发式搜索好于盲 目搜索，但盲目搜索

4、也会在很多问题的求解中得到应 用。 在状态空间表示法中，可以采用图示的方式表示 ，即状态空间图。状态空间图是一个有向图。当把一 个待求解的问题表示为状态空间以后，就可以通过对 状态空间的搜索，实现对问题的求解。 5.2盲目搜索策略如果从状态空间图的角度来看，则对问题的求解就 相当于在有向图上寻找一条从某一节点（初始状态节点 ）到另一节点（目标状态节点）的路径。4 4西南科技大学西南科技大学 信息工程学院信息工程学院但是，若要把表示问题的整个状态空间都存入计 算机，往往需要占据巨大的存储空间，尤其对比较复 杂的问题，这几乎是不可能实现的，并且一般也无这 种必要。因为对于一个具体的问题，其解往往只

5、与状 态空间的一部分相关，只要计算机生成并存储与问题 有关的解状态空间部分，即可将问题解决。但如何来 生成并存储与问题有关的部分状态空间呢？这就是人 工智能中所研究的搜索技术问题。 一状态空间图的搜索策略 搜索法求解问题的基本思想：首先将问题的初始状态（即状态空间图中的初始 节点）当作当前状态，选择一适当的算符作用于当前 状态，生成一组后继状态（或称后继节点），然后检 查这组后继状态中有没有目标状态。如果有，则说明5 5西南科技大学西南科技大学 信息工程学院信息工程学院搜索成功，从初始状态到目标状态的一系列算符即是 问题的解；若没有，则按照某种控制策略从已生成的 状态中再选一个状态作为当前状态

6、，重复上述过程， 直到目标状态出现或不再有可供操作的状态及算符时 为止。 几个概念：扩展：用合适的算符对某个节点进行操作生成一组后继 节点的过程。扩展过程实际上就是求后继节点的过程。 已扩展节点：对状态空间图中的某个节点，如果求出了 它的后继节点，则称此节点为已扩展节点。 未扩展节点：对状态空间图中那些尚未求出其后继节点 的节点称为未扩展节点。 6 6西南科技大学西南科技大学 信息工程学院信息工程学院OPEN和CLOSED表：为了记录搜索过程，建立两个名字分别为OPEN 和CLOSED的表，用于分别存放未扩展节点和已扩展 节点。它们的数据结构如下： 表1 OPEN表结构 状态节点父节点表2 C

7、LOSED表结构 编号状态节点父节点7 7西南科技大学西南科技大学 信息工程学院信息工程学院状态空间图的搜索算法如下： Step1：建立一个只含有初始节点S0的搜索图G，把S0 放入OPEN表中。Step2：建立CLOSED表，且置为空表。 Step3：判断OPEN表是否为空表。若为空，则问题无 解，结束。Step5：考察节点n是否为目标节点。若是，则问题有 解，并成功退出。问题的解即可从图G中沿着指针从 n到S0的这条路径得到。Step4：选择OPEN表中的第一个节点，把它从OPEN表 移出，并放入CLOSED表中，将此节点记为节点n。Step6：扩展节点n生成一组不是n的祖先的后继节点，8

8、 8西南科技大学西南科技大学 信息工程学院信息工程学院并将它们记作集合M，将M中的这些节点作为n的后继 节点加入图G中。 Step7：对那些未曾在G中出现过的（即未曾在OPEN表 上或CLOSED表上出现过的）M中的节点，设置一个指 向父节点（即节点n）的指针，并把这些节点加入OPEN 表中；对于已在G中出现过的M中的那些节点，确定是否 需要修改指向父节点（即节点n）的指针；对于那些先前 已在G中出现并已在CLOSED表中的那些M中的节点， 确定是否需要修改通向它们后继节点的指针。Step8：按某一任意方式或按某种策略重排OPEN表中 节点的顺序。Step9：转Step3。搜索过程的流程图如图

9、1所示。 9 9西南科技大学西南科技大学 信息工程学院信息工程学院YNNY开 始初始化：把S0放入OPEN中，CLOSED表置空把OPEN表中的第一个节点(n)移至CLOSED表中若n的后继节点未曾在搜索图G中出现，则将其放入OPEN 表的末端，并提供返回节点n的指针中。根据后继节点在搜索图G中的出现情况修改指针方向重排OPEN表失败，退出成功，退出OPEN为空表？n为目标节点吗？图1 状态空间 的搜索过程框图1010西南科技大学西南科技大学 信息工程学院信息工程学院这一搜索算法具有通用性。以后讨论的各种搜索 策略都可以看作是它的一个特例。各种策略的主要区 别就在于Step8对OPEN表中的节

10、点排序的算法不同。 在Step8中，对OPEN表中的节点排序时，主要希望从 未扩展节点中选出一个最有希望的节点作为Step4扩展 来用。 若这时的排序是任意的或者是盲目的，则搜索即 为盲目搜索；如果是按某种启发信息或准则进行排序 ，则其就是启发式搜索。 搜索图：在搜索过程中，生成了一个图G，它是问题 状态空间图的一部分，称为搜索图。搜索树：由搜索图G中的所有节点及Step7设置的指向 父节点的反向指针，所构成的集合T称为搜索树。1111西南科技大学西南科技大学 信息工程学院信息工程学院搜索图G中，除初始节点S0外的每个节点，都有一 个指向G中一个父辈节点的指针，该父辈节点就定为搜 索树中对应节

11、点的唯一父辈节点。 搜索解：在搜索过程中，当某个被选作扩展的节点，是 目标节点时（在Step5），则就找到了问题的一个解。 所找到的解就是从初始节点S0到目标节点路径上的算符 所构成的序列。而路径则是通过目标节点按Step7设置的指针指向 初始节点回溯而得到的。如果在搜索中一直找不到目标 节点，而且OPEN表中又不再具有可供扩展的节点，则 搜索失败，在Step3退出结束。这样的搜索过程实际上就是问题的求解过程。在利 用状态空间搜索法求解问题时，并不是将整个问题的状 态空间图全部输入计算机，而是只存入与问题解有关的1212西南科技大学西南科技大学 信息工程学院信息工程学院部分状态空间图。这种部分

12、状态空间图是在搜索过 程中生成的，并且每前进一部，都要检查是否到达 目标节点，这样就可以尽量地少生成与问题无关地 状态，从而提高了解题效率，节省了存储空间。 二宽度优先搜索策略宽度优先搜索又称为广度优先搜索，是一种盲 目搜索。其基本思想如下：从初始节点开始，逐层对节点进行依次扩展， 并考察它是否为目标节点，在对下层节点进行扩展 （或搜索）之前，必须完成对当前层的所有节点的 扩展（或搜索）。在搜索过程中，未扩展节点表OPEN中的节点 排序准则是：1313西南科技大学西南科技大学 信息工程学院信息工程学院先进入的节点排在前面，后进入的节点排在后面 。其搜索过程如图2所示。SLOMFPQNFFF图2

13、 宽度优先搜索过程起始节点1414西南科技大学西南科技大学 信息工程学院信息工程学院Step6：对节点n进行扩展，将它的所有后继节点放入 OPEN表的末端，并为这些后继节点设置一个指向父 节点n的指针，然后转Step2。算法2：状态空间图的宽度优先搜索算法 Step1：把初始节点S0放入OPEN表中。 Step2：如果OPEN表是空表，则没有解，失败退出 。否则继续。 Step3：把OPEN表中的第一个节点（记为节点n） 移出，并放入CLOSED表中。 Step4：判断节点n是否为目标节点。若是，则求解 结束，并用回溯法找出解的路径，退出；否则继续 执行Step5。 Step5：若节点n不可扩

14、展，转Step2；否则继续执行 Step6。1515西南科技大学西南科技大学 信息工程学院信息工程学院宽度优先算法的流程图如图3所示。 YYNNY开 始把S0放入OPEN把OPEN表中的第一个节点(n)移出放入CLOSED表扩展节点n，将其后继节点放入OPEN表的末端为每个后继节点配置指向n的指针失败，退出回溯求解路径OPEN空表？n为目标节点吗？节点n可扩展吗？N成功，退出图3 宽度优先 算法框图1616西南科技大学西南科技大学 信息工程学院信息工程学院例1 八数码难题：设在3*3的一个方格棋盘上，摆 放着8个数码1、2、3、4、5、6、7、8，有一个方 格是空格，其初始状态如图4(a)所示

15、，要求对空格 执行下列的操作（或算符）：空格左移，空格上移，空格右移，空格下移 使八个数据最终按图4(b)的格式摆放，如图4(b)称 为目标状态Sg。要求寻找从初始状态到目标状态的 路径。 2 8 3 1 4 7 6 5 S0 (a) 初始状态1 2 3 8 4 7 6 5 Sg (b) 目标状态图4 八数码难题1717西南科技大学西南科技大学 信息工程学院信息工程学院解：应用宽度优先搜索，可以得到如图5的搜索树。搜索树上的所有节点都标记它们所对应的状态描 述，每个节点旁边的数字表示节点扩展的顺序（按逆 时针方向移动空格）。 从图5中可以看出，其解的路径为：S0381627。缺点：宽度优先搜索

16、的盲目性较大，当目标节点 距离初始节点较远时，将会产生大量的无用节点 。搜索效率低。 优点：深度优先搜索策略是完备的，即只要问题有 解，用宽度优先搜索总可以找到它的解，而且是搜 索树中，从初始节点到目标节点的路径最短的解。1818西南科技大学西南科技大学 信息工程学院信息工程学院图5 八数码难题的宽度优先搜索树Sg8 3 2 1 4 7 6 58 1 3 2 4 7 6 52 8 3 7 4 6 1 52 8 3 7 1 4 6 5 1 2 3 7 8 46 51 2 3 8 4 7 6 52 8 3 7 1 4 6 58 3 2 1 4 7 6 52 3 4 1 8 7 6 52 8 36 4 1 7 52 8 3 1 6 7 5 42 8 1 4 3 7 6 52 8 3 1 4 5 7 61 2 38