2022年人工智能第五章状态空间搜索策略山东大学期末考试知识点复习.docx

精选学习资料 - - - - - - - - - 学习必备 欢迎下载第五章 状态空间搜寻策略搜寻是人工智能的一个基本问题,题的一种方法,是依据问题的实际情形,是推理不行分割的一部分； 搜寻是求解问 依据肯定的策略或规章, 从学问库中寻找可利用的学问, 从而构造出一条使问题获得解决的推理路线的过程；搜寻包含两层含义： 一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线；搜寻可分为盲目搜寻和启示式搜寻两种； 11 盲目搜寻策略 1状态空间图的搜寻策略为了利用搜寻的方法求解问题, 第一必需将被求解的问题用某种形式表示出来；一般情形下, 不同的学问表示对应着不同的求解方法；状态空间表示法是一种用“ 状态” 和“ 算符” 表示问题的方法；状态空间可由一个三元组表示 S0,F,Sg ；利用搜寻方法求解问题的基本思想是：第一将问题的初始状态 即状态空间图中的初始节点 当作当前状态,选择一适当的算符作用于当前状态,生成一组后继状态 或称后继节点 ,然后检查这组后继状态中有没有目标状态；假如有,就说明搜寻胜利,从初始状态到目标状态的一系列算符即是问题的解；如没有,就依据某种掌握策略从已生成的状态中再选一个状态作为当前状态,重复上述过程,直到目标状态显现或不再有可供操作的状态及算符时为止；算法 51 状态空间图的一般搜寻算法建立一个只含有初始节点S0的搜寻图 G,把 S0放入 OPEN表中；建立 CLOSED表,且置为空表；判定 OPEN表是否为空表,如为空,就问题无解,退出；选择 OPEN表中的第一个节点, 把它从 OPEN表移出,并放入 CLOSED表中,名师归纳总结 - - - - - - -第 1 页,共 6 页精选学习资料 - - - - - - - - - 将此节点记为节点n；学习必备欢迎下载考察节点 n 是否为目标节点,如是,就问题有解,并胜利退出；问题的解即可从图 G中沿着指针从 n 到 S0 的这条路径得到；扩展节点 n 生成一组不是 n 的祖先的后继节点,并将它们记作集合 M,将M中的这些节点作为 n 的后继节点加入图 G中；对那些未曾在 G 中显现过的 即未曾在 OPEN表上或 CLOSED表上显现过的M 中的节点,设置一个指向父节点 即节点 n 的指针,并把这些节点加入 OPEN表中；对于已在 G中显现过的 M中的那些节点, 确定是否需要修改指向父节点 n节点 的指针；对于那些从前已在G中显现并且已在 COLSED表中的 M中的节点,确定是否需要修改通向它们后继节点的指针； 2按某一任意方式或按某种策略重排 OPEN表中节点的次序；转第步；宽度优先搜寻策略宽度优先搜寻是一种盲目搜寻策略；其基本思想是,从初始节点开头,逐层对节点进行依次扩展,并考察它是否为目标节点,在对下层节点进行扩展 或搜索 之前,必需完成对当前层的全部节点的扩展 或搜寻 ；在搜寻过程中,未扩展节点表 OPEN中的节点排序准就是：先进入的节点排在前面,后进入的节点排 在后面 即将扩展得到的后继节点放于 OPEN表的末端 ；宽度优先搜寻的盲目性较大,搜寻效率低,这是它的缺点；但宽度优先搜寻策略是完备的,即只要问题有解,用宽度优先搜寻总可以找到它的解； 3深度优先搜寻深度优先搜寻也是一种盲目搜寻策略,其基本思想是： 第一扩展最新产生的 即最深的 节点,即从初始节点 S0 开头,在其后继节点中选择一个节点,对其进行考察, 如它不是目标节点, 就对该节点进行扩展, 并再从它的后继节点中选择名师归纳总结 - - - - - - -第 2 页,共 6 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载一个节点进行考察；依此类推, 始终搜寻下去, 当到达某个既非目标节点又无法连续扩展的节点时,才选择其兄弟节点进行考察；深度优先搜寻与宽度优先搜寻的区分就在于：在对节点 n 进行扩展时, 其后继节点在 OPEN表中的存放位置；宽度优先搜寻是将后继节点放入 OPEN表的末端,而深度优先搜寻就是将后继节点放入 OPEN表的前端； 4有界深度优先搜寻对于很多问题, 其状态空间搜寻树的深度可能为无限深；为了防止搜寻过程沿着无穷的路径搜寻下去, 往往对一个节点扩展的最大深度进行限制；任何节点假如达到了深度界限, 就把它作为没有后继节点进行处理,即对另一个分支进行搜寻；在有界深度优先搜寻算法中,深度界限的选择很重要；选择过大,可能会影响搜寻的效率； 选择的过小,有可能求不到解；有界深度优先搜寻策略是不完备 的； 5代价树的宽度优先搜寻前面的搜寻算法没有考虑搜寻的代价问题,即假设状态空间图中各节点之间的有向边的代价是相同的； 在实际问题求解中, 往往是将一个状态变换成另一个状态时所付出的操作代价 或费用 是不一样的,即状态空间图中各有向边的代价是不一样的；把有向边上标有代价的搜寻树称为代价搜寻树,简称代价树；代价树宽度优先搜寻的基本思想是：每次从OPEN表中选择一个代价最小的节点,移入 COLSED表；因此,每当对一节点扩展之后,就要运算它的全部后继节点的代价,并将它们与OPEN表中已有的待扩展的节点按代价的大小从小到大依次排序；而从 OPEN表选择被扩展节点时即选择排在最前面的节点 代价最小 ；代价树的宽度优先搜寻算法是一个完备算法； 6代价树的深度优先搜寻代价树的深度优先搜寻和宽度优先搜寻的区分是：宽度优先搜寻法每次从名师归纳总结 - - - - - - -第 3 页,共 6 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载OPEN表中的全体节点中选择代价最小的节点移入CLOSED表,并对这一节点进行扩展或判定 是否为目标节点 ,而深度优先搜寻法就是从刚刚扩展的节点之后继节点中选择一个代价最小的节点移入 深度优先搜寻算法是不完备的算法,CLOSED表,并进行扩展或判定；代价树的 所求得的解不肯定是最优解, 甚至有可能进入无穷分支路径而搜寻不到问题的解； 1 2 启示式搜寻策略 利用问题自身特性信息, 以提高搜寻效率的搜寻策略, 称为启示式搜寻或有 信息搜寻； 1启示信息与估价函数在搜寻过程中, 假如在确定要被考察的节点时,能够利用被求解问题的有关特性信息,估量出各节点的重要性,就可选择重要性较高的节点进行扩展,以便提高求解的效率；通常可以构造一个函数来表示节点的“ 期望” 程度,称这种函数为估价函数；估价函数 fx 可定义为从初始节点经过节点 径的代价估量值；它的一般形式为 fx=gx+hx z 到达目标节点的最小代价路其中 gx 为初始节点 S0到节点 z 已实际付出的代价； hx 是从节点 x 到目标节点 Sg的最优路径的估量代价,搜寻的启示信息主要由 作启示函数；hx 来表达,故把 hx 称估价函数是针对详细问题构造的,是与问题特性亲密相关的；不同的问题,其估价函数可能不同；在构造估价函数时,依靠于问题特性的启示函数 hx 的 构造尤为重要；在构造启示函数时,仍要考虑到两个方面因素的影响：一个是搜寻工作量,一个是搜寻代价； 有些启示信息虽然能够大大削减搜寻的工作量,但却不能保证 求得最小代价的路径； 而我们感爱好的是, 使问题求解的路径代价与为求此路径名师归纳总结 - - - - - - -第 4 页,共 6 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载所花费的搜寻代价的综合指标为最小； 2正确优先搜寻正确优先搜寻又称为有序搜寻或择优搜寻,它总是选择最有期望的节点作为下一个要扩展的节点,而这种最有期望的节点是按估价函数 fx 的值来选择的,一般估价函数的值越小, 它的期望程度越大； 正确优先搜寻又分局部正确优先搜索和全局正确优先搜寻； 1 局部正确优先搜寻局部正确优先搜寻的思想类似于深度优先搜寻法,但由于使用了与问题特性相关的估价函数来确定下一个待扩展的节点,所以它是一种启示式搜寻方法；其思想是：当对某一个节点扩展之后,对它的每一个后继节点运算估价函数 fx的值,并在这些后继节点的范畴内,选择一个fx 的值最小的节点,作为下一个要考察的节点；由于它每次只在后继节点的范畴内选择下一个要考察的节点,范畴比较小,所以称为局部正确优先搜寻或局部择优搜寻；局部正确优先搜寻与深度优先搜寻及代价树的深度优先搜寻的区分,就在于在选择下一个节点时所用的标准不一样；局部正确优先搜寻是以估价函数值作为标准；深度优先搜寻就是以后继节点的深度作为选择标准,后生成的节点先考察；而代价树深度优先就是以各后继节点到其前驱节点之间的代价作为选择标准；如果把层深函数 dx 就当作估价函数 fx ,或把代价函数 gx 当作估价函数 fx ,那么就可以把深度优先搜寻和代价树深度优先搜寻看作局部正确优先搜寻的两个特例； 2 全局正确优先搜寻全局正确优先搜寻也是一个有信息的启示式搜寻,它的思想类似于宽度优先搜寻,所不同的是, 在确定下一个扩展节点时, 以与问题特性亲密相关的估价函数 fx 作为标准, 不过这种方法是在OPEN表中的全部节点中选择一个估价函数名师归纳总结 值 fx 最小的节点,作为下一个被考察的节点；正由于选择的范畴是OPEN表中第 5 页,共 6 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载的全部节点,所以它称为全局正确优先搜寻或全局择优搜寻；全局正确优先搜寻实际是对宽度优先搜寻和代价树的宽度优先搜寻的扩展,而宽度优先搜寻和代价树的宽度优先搜寻就是它的两个特例 这时可分别令 fx等于 dx 或 gx ,dx 表示节点 x 的深度,而 gx 就表示初始节点 S0 到节点 x的代价 ；在启示式搜寻中, 估价函数的定义是特别重要的,假如定义得不好,就上述的搜寻算法不肯定能找到问题的解,即便找到解,也不肯定是最优解；所以,有必要争论如何对估价函数进行限制或定义； A* 启示式搜寻算法就使用了一种特别定义的估价函数； A* 算法具有以下一些性质：可接受性；所谓可接受性是指对于可求解的状态空间图 即从状态空间图的初始节点到目标节点有路径存在 来说,假如一个搜寻算法能在有限步内终止,并且能找到最优解,就称该算法是可接受的；单调性；所谓单调性是指在A*算法中,假如对其估价函数中的hx 部分即启示性函数, 加以适当的单调性限制条件, 就可以使它对所扩展的一系列节点 的估价函数值单调递增 或非递减 ,从而削减对 OPEN表或 CLOSED表的检查和调 整,提高搜寻效率；信息性 又称最优性 ；A*算法的搜寻效率主要取决于启示函数 hx ,在 满意 hx h*x 的前提下, hx 的值越大越好； hx 的值越大,说明它携带的 与求解问题相关的启示信息越多, 搜寻过程就会在启示信息指导下朝着目标节点 前进,所走的弯路越少,搜寻效率就会提高；名师归纳总结 - - - - - - -第 6 页,共 6 页