第五章 状态空间搜索策略

1、状态空间的搜索策略北京师范大学信息科学与技术学院王醒策概述n教学内容n搜索的概念及种类n盲目搜索策略n启发式搜索策略n教学重点n宽度优先搜索、深度优先搜索及代价树的搜索算法，A*搜索算法n教学难点n利用各种搜索算法解决实际问题，尤其是估价函数的选取概述n有哪些常用的搜索算法。n问题有解时能否找到解。n找到的解是最佳的吗？n什么情况下可以找到最佳解？n求解的效率如何。概述n搜索是人工智能中的基本问题n搜索中的知识表示n状态空间表示法n与/或树表示法n很多问题可以转化为搜索问题搜索的概念以及分类n搜索的概念n根据问题的实际情况，按照一定的策略或者规划，从知识库中寻找可以利用的知识，从而构造出一条使

2、得问题获得解决的推理路线的过程n搜索的两层含义n要找到从初始事实到问题最终答案的一条推理路线n找到的这条路线是时间和空间复杂度最小的求解路线搜索的种类n搜索可以分为盲目搜索和启发式搜索两种n盲目搜索n又称为无信息搜索。也就是在搜索的过程中只按预先的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略n启发式搜索n称为有信息搜索。它是指在问题搜索过程中，根据问题本身的特征或者搜索过程中产生出来的一些信息来不断地改变或者调整搜索方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。人工智能领域中已有搜索方法 n（1）求任一解路的搜索策略n回溯法（Backtracking）n爬山法

3、（Hill Climbing）n宽度优先法（Breadth-first）n深度优先法（Depth-first）n限定范围搜索法（Beam Search）n好的优先法（Best-first）人工智能领域中已有搜索方法n（2）求最佳解路的搜索策略n大英博物馆法（British Museum）n分枝界限法（Branch and Bound）n动态规划法（Dynamic Programming）n最佳图搜索法（A）人工智能领域中已有搜索方法n（3）求与或关系解图的搜索法n一般与或图搜索法（AO）n极小极大法（Minimax）n剪枝法（Alpha-beta Pruning）n启发式剪枝法（Heurist

4、ic Pruning）回溯搜索（Backtracking strategies）n回溯搜索策略是盲目搜索中的一种。思想为：n首先将规则给出一个固定的排序；n在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则；n在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态；n得到的新状态重新设置为当前状态，并重复以上搜索；n如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。n重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。回溯搜索n举例说明：四皇后问题n在一个44

5、的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不许相互俘获。回溯搜索n给出棋盘的几个势态，其中a，b满足目标条件，c，d，e为不合法状态，即不可能构成满足目标条件的中间态势回溯搜索n搜索方法的实现递归实现n递归方法的特点n递归必须要有出口n递归公式中，每一次调用必须距出口更近一些回溯搜索回溯搜索n算法步骤Backtrack(DATA)n如果当前状态DATA为目标状态，则找到目标。n该状态不合法，则过程返回失败信息 ，必须回溯。n计算DATA（当前状态）的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。n如果规则

6、用完未找到目标，过程返回FAIL，必须回溯。回溯搜索n取头条可应用规则。n删去头条规则，减少可应用规则表的长度。n调用规则R作用于当前状态，生成新状态（RDATA）。n对新状态递归调用本过程。n当PATHFAIL时，递归调用失败，则转移回第四步，调用另一规则进行测试。n过程返回解路径规则表（或局部解路径子表）。回溯搜索n回溯搜索会出现的问题n深度问题n死循环问题回溯搜索n回溯中失败原因的分析多步回溯问题n回溯搜索中知识的应用盲目搜索策略n状态空间图的搜索策略n宽度优先搜索策略n深度优先搜索策略n代价树的宽度优先搜索n代价树的深度优先搜索n盲目搜索的性质总结状态空间图的搜索策略n算法思想：n首先

7、将问题的初始状态（即状态空间中的初始节点）当作是当前状态。n选择一个合适的算符作用于当前状态，生成一组后继状态（或称为）后继节点，n然后检查这组后继状态中有没有目标状态。n如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，n重复上述的过程直到目标状态不在出现或者不再有可供操作的状态及算符为止。状态空间图的搜索策略n图论中的几个术语n节点深度：n初始节点（根节点）的深度为0n任何其它节点的深度等于父节点的深度加1n路径：n设一节点的序列为（n0,n1,ni,nk）i=1k若在任意一个节点ni-1都有一个后继的

8、节点ni，则称该节点序列为节点n0到nk长度为k的一条路径。状态空间图的搜索策略n路径耗散值：n令C( ni, nj)为节点ni到nj这段路径（或弧线）的耗散值，一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和。n初始节点S0到任意节点的x的路径耗散值称为路径代价，记为g(x)n路径耗散值可按如下递归公式计算：g(nj)=g(ni)+C(ni,nj)状态空间图的搜索策略n已扩展节点和未扩展节点n扩展节点n所谓已扩展节点就是用合适的算符对某个节点操作后生成的一组后继节点。扩展的过程实际上就是求得后继节点的过程。n已扩展节点n对状态空间图中的某个节点，如果求出了它的后继节点，则此节点称

9、为已扩展节点。n未扩展节点n对状态空间图中的某个节点，如果未求出它的后继节点，则称此节点为未扩展节点。状态空间图的搜索策略n一般来讲，习惯于将未扩展的节点存放于一个名为open的表中，而将已扩展的节点存放于名为closed的表中。nOpen 表和closed表的数据结构如下所示：状态空间图的搜索策略n状态空间的搜索算法：n1 建立一个只含有初始节点S0的搜索图G，把S0放入到open表中n2 建立closed表，并且将其置为空表n3 判断open表是否为空表，若为空，则问题无解，退出。n4 若open表非空，则选择open表中的第一个节点，把它从open表中移出，并放入closed表中，将此节

10、点标记为节点n。状态空间图的搜索策略n5 考察节点n是 否为目标节点，如果是，则问题有解，并且成功退出。问题的解既可从图G中沿着指针从n到S0的这条路径得到。n6 扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中。状态空间图的搜索策略n7 对于那些未曾在G中出现过的（即未曾在open表上或closed表上出现过的）M中的节点，设置一个指向父节点（即节点n）的指针，并把这些节点加入到open表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点（n节点）的指针；对于那些先前已经在G中出现并且已在closed表中的那些M中的节点

11、，确定是否需要修改通向它们后继点的指针。n8 按照某一种方式或者某种策略重排open表中的节点的顺序n9 转到第（3）步。状态空间图的搜索策略n解释；n这里给出的是一个图搜索的一般框架，不是一个具体的算法，n关键是算法的第8步，按不同的原则对open表进行排序，将得到不同的图搜索算法。 n上面的搜索过程实际上就是问题的求解过程。在利用状态空间搜索法来求解问题时，并不是将问题的状态空间图全部输入计算机，而只是存入与问题有关的部分状态空间图，这种部分状态空间图是在搜索过程中生成的，并且每计算一步都要检查是否达到了目标节点，这样就可能尽量少地生成与问题无关的状态。状态空间图的搜索策略n节点类型说明状

12、态空间图的搜索策略n修改指针的说明状态空间图的搜索策略状态空间图的搜索策略状态空间图的搜索策略宽度优先搜索策略n宽度优先n又称为是广度优先；n是一种盲目的搜索策略。n它的基本思想是：n从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点。在对下层的节点进行扩展或者是搜索之前，必须完成对当前层的所有节点的扩展或者是搜索。nOpen表的节点排队准则：n先进入open表中，先进入的节点排在前面，后进入的节点排在后面。宽度优先搜索策略n算法：状态空间图的宽度优先搜索算法n把初始节点S0放入到open表中n判断open表是否为空，若为空，则问题无解，退出，否则继续。n选择open表中的第一个节

13、点（标记为节点n ），把它从open表中移出，并放入closed表中。宽度优先搜索策略n考察节点n是 否为目标节点，若是，则求解结束，得到解路径。n若节点n不可扩展，则转到第2步，否则执行第6步。n对节点n进行扩展，将它的所有后继节点放入open表的末端，并为这些节点设置指向父节点n的指针，然后转到第2步。初始节点S放入到OPEN表OPEN表为空？OPEN表的第一个节点移出(节点n)，放入CLOSED表中对节点n进行扩展节点n为目标节点？节点n不可扩展？宽度优先搜索框图宽度优先搜索框图问题无解NYYNNY求解结束，回溯得到解路径将它的所有后继节点放入OPEN表的末端，并为这些节点设置指向父节点

14、n的指针算法实现过程OPEN表ClOSED表SLF宽度优先搜索策略宽度优先搜索策略n例题：八数码难题n设在一个3*3的方格模型上，摆放八个数码1、2、3、4、5、6、7、8，其中有一个时空格，空格可以执行如下操作：空格左移，空格上移，空格下移，空格右移。初始状态和目标状态如下所示：宽度优先搜索策略深度优先搜索n深度优先是一种盲目的搜索策略n深度优先思想：n首先最先扩展最先产生的节点，即从初始节点S0开始，在它的后继节点种选择一个节点，对其进行考察。若它不是目标节点，则对该节点进行扩展，并再度从它的后继节点种选择一个节点进行考察，以此类推，一直搜索下去，当达到某个非目标节点又无法继续扩展的点时，

15、才选择兄弟节点进行考察深度优先搜索深度优先搜索n算法：状态空间图的深度优先搜索算法n把初始节点S0放入到open表中来；n如果open表为空，则问题无解退出；n从open表中将第一个节点（节点n）移出，放入已扩展节点表closed中；n考察节点n是否为目标节点，若是则找到问题的解，给与相应的解路径，退出；n若节点n不可扩展，则转到第2步n扩展节点n，将其后继节点放到open表的前端，并为其设置指向节点n的指针，然后转向第2步。深度优先搜索n深度优先和宽度优先的区别n对节点n进行扩展的时候，其后继节点在open表中存在的位置。宽度优先搜索的将后继节点放入open表的末端而深度优先搜索则是将后得到

16、的节点放入open表的前端。有界深度优先搜索n产生原因 ：n深度优先搜索对于有限状态空间图来说，总能够找到解。但是对于无限图来讲就未必。并且相对来讲搜索效率会比较低。所以为了防止在无解的分支上进行无效的搜索，需要对搜索深度做一些限制。n思想：n任何节点如果到达了深度限制，就把它作为没有后继节点进行处理，对另一个分支进行搜索。有界深度优先搜索n有界深度优先算法n1 把初始节点S0放入open表中n2 如果open表为空，则问题无解，退出n3 把open表中的第一个节点（节点n）从open表中移到closed表中。n4 考察节点n是否为目标节点，若是则求得问题的解，并退出；否则继续执行第5步有界深

17、度优先搜索n5 如果节点n的深度等于最大深度，则转第2步n6 如果节点n不可以扩展，既没有后继节点，则转到第2步，否则转到第7步n7 扩展节点n，将后继节点放入到open表的前端，并为其设置指向节点n的指针，然后转向第2步。有界深度优先搜索n例题n设八数码难题的初始状态和目标状态如下所示，请采用有界深度优先的策略求解问题的搜索树，深度界限dm=5有界深度优先搜索n解释说明n在有界深度优先搜索算法中，深度界限的选择很重要。n在某些问题中，他的解可能就位于某一分支较深的位置上，而界限选择如果没有足够大的话，可能就会找不到问题的解。n所以有界深度优先搜索策略是不完备的。代价树的搜索n介绍n前面所介绍

18、的问题都是单位耗散问题，下面将要介绍的是非单位耗散的时候如何构造搜索策略。n这里将介绍两种方法：n代价树宽度优先搜索n代价树深度优先搜索代价树宽度优先搜索n算法的基本思想n每次从open表中选择一个代价最小的节点，移入closed表中。n因此对每一个节点扩展之后，就要计算它所有的后继节点的代价，并将它们与open表中得以有待扩展的节点按照代价的大小进行排序n从open表中选择的下一个被扩展节点是排在最前面的解点。代价树宽度优先搜索n算法：代价树宽度优先搜索算法n1 把初始节点S0放入open表中，令g(S0)=0n2 如果open表为空，则问题无解，退出n3 把open表中的代价最小的节点，即

19、排在最前端的节点（节点n）从open表中移到closed表中。n4 考察节点n是否为目标节点，若是则求得问题的解，并退出；否则继续。代价树宽度优先搜索n5 判断节点n是否可以扩展，如果不可以扩展则转向第2步，否则继续n6 对节点n进行扩展，将它们所有的后继节点放入open表中，并对每一个后继节点nj计算其代价 g(j)=g(i)+c(i,j)n7 为每一个后继节点设置指向n的指针，然后根据节点的代价大小对open表中的所有节点进行从小到大排序n8 转向第2步代价树宽度优先搜索n例题：推销员最短路径问题n假设A,B,C,D,E是五个城市，推销员要从A城出发，到达E城。需要走怎样的路径，费用才能最

20、省？n五个城市的交通图以及每两个城市间的旅行费用如下所示，图中的数字就是旅行费用。代价树的深度优先搜索策略n代价树的深度优先搜索和宽度优先搜索的区别n代价树宽度优先搜索每次都从open表中选择一个代价最小的节点移入closed表中，并对这一节点判断是否为目标点或者扩展n而代价树宽度优先搜索则是从刚刚扩展的节点的后继节点种选择一个代价最小的节点移入closed表中，并进行扩展或者判断代价树的深度优先搜索策略n代价树深度优先搜索策略算法n1 把初始节点S0放入open表中，令g(S0)=0n2 如果open表为空，则问题无解，退出n3 把open表中的代价最小的节点，即排在最前端的节点（节点n）从

21、open表中移到closed表中。n4 考察节点n是否为目标节点，若是则求得问题的解，并退出；否则继续。代价树的深度优先搜索策略n5 判断节点n是否可以扩展，如果不可以扩展则转向第2步，否则继续n6 对节点n进行扩展，将它们所有的后继节点按照有向边的代价从小到大的排序之后放入open表的前端。n7 为每一个后继节点设置指向n的指针n8 转向第2步代价树深度优先搜索n例题：推销员最短路径问题n假设A,B,C,D,E是五个城市，推销员要从A城出发，到达E城。需要走怎样的路径，费用才能最省？n五个城市的交通图以及每两个城市间的旅行费用如下所示，图中的数字就是旅行费用。性质总结n我们来总结一下深度优先

22、和宽度优先的性质 n深度优先n一般不能保证找到最优解n解与深度限制有密切的关系n深度优先搜索的效率n与回溯方法的差别n是一个通用的方法性质总结n宽度优先n当问题有解的时候，一定能找到n当问题为单位耗散值的时候，且问题有解，则找到的一定是最优解n方法与问题无关，是一种通用的搜索策略n效率比较低下n属于图搜索的范围渐进式深度优先搜索n目的n解决宽度优先搜索方法的空间问题和深度优先方法和回溯方法不能找到最优解的问题n思想 n先给定深度优先搜索一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或者是遍寻过所有的分支为止。启发式搜索策略n概述n最佳优先搜索n局部最佳优先搜索算法n全局最佳优先搜索算法

23、n最佳图搜索法nA算法nA算法启发信息与估价函数n搜索过程中，关键的一步是确定如何选择下一个要被考察的点，不同的选择方法面对着不同的搜索策略。n启发信息n可以用来指导搜索过程且与具体问题求解有关的控制信息称为启发信息启发信息与估价函数n启发信息的种类n用于决定要扩展的下一个节点，以避免像深度优先或者宽度优先那样盲目地扩展n在扩展节点的过程中，用于决定要生成哪一个或者那几个后继节点，以免盲目地生成所有可能的后继节点n用于确定某些应该从搜索树中抛弃或者修剪的节点。启发信息与估价函数n估价函数（Evlauation function）n用来度量或者是估算节点的“希望”程度的函数。n估价函数的定义基本

24、原则n一个节点处在最佳路径上的概率n求出任意一个节点与目标节点集之间的距离度量或者差异度量n根据格局（博弈）问题或者状态的特点来打分启发信息与估价函数n启发式信息对算法的影响n强强：启发式信息强，可以降低搜索的工作量，但可能丢失最优解。n弱弱：启发式信息弱，搜索的工作量加大，但是一般容易找到最优解。最佳优先搜索n算法概述n又称为有序搜索或者择优搜索，n算法思想n最佳优先搜索算法总是挑选最有希望的节点作为下一个要扩展的节点，而这种最有希望的顺序是按照估价函数f(x)的值来挑选。一般估价函数的值越小，它的希望程度越大局部最佳优先搜索n算法概述n局部最佳优先搜索算法有些类似于深度优先搜索算法，但是由

25、于使用了与问题特征有关的估价函数来确定下一个带扩展节点，所以它是一种启发是搜索算法。局部最佳优先搜索n算法思想n当对某一个节点扩展之后，对它的每一个后继节点计算估价函数f(x)的值，并在这些后继节点的范围内，选择一个f(x)值最小的节点，作为下一个要考察的节点n由于他每次只是在后继节点的范围内选择一个要考察的点，范围比较小，所以称为局部局部最佳优先搜索最佳优先搜索或者局部择优搜索局部择优搜索局部最佳优先搜索n算法：局部最佳优先搜索算法n1 把初始节点S0放入open表中，令f(S0)=0n2 如果open表为空，则问题无解，退出。否则转第三步。n3 把open表中选取第一个节点（节点n）从op

26、en表中移到closed表中。n4 考察节点n是否为目标节点，若是则求得问题的解，并退出；否则继续。局部最佳优先搜索n5 判断节点n是否可以扩展，如果不可以扩展则转向第2步，否则继续n6 对节点n进行扩展，并对它所有的后继节点计算估价函数f(x)的值，并按照估价函数f(x)从小到大的顺序依次放入open表的前端。n7 为每个后继节点设置指向n的指针n8 转向第2步局部最佳优先搜索n局部最佳优先搜索与深度优先及代价树深度优先搜索的区别n选择下一个节点时所用的标准不一样局部最佳优先搜索n局部最佳优先搜索n估价函数的值作为标准n深度优先搜索n后继节点的深度作为选择标准，后生成的节点先考察n代价树深度

27、优先搜索n各后继节点到其前驱节点之间的代价作为选择标准。局部最佳优先搜索n如果把层深度函数d(x)当作估价函数f(x)，或者是把代价函数g(x)当作估价函数f(x)，那么就可以把深度优先搜索和代价树深度优先搜索看作是局部最佳优先搜索的两个特例。全局最佳优先搜索n算法概述n由信息的启发式搜索，类似于宽度优先搜索。n所不同的事，在确定下一个扩展节点时，以与问题特性密切相关的估价函数作为标准，不过这种方法实在open表中的全部节点中选择一个估价函数值f(x)最小的节点，作为下一个被考察的节点。全局最佳优先搜索n算法概述n正因为选择的范围是open表中的全部节点，所以它成为全局最佳优先搜索全局最佳优先

28、搜索或者是全局择全局择优搜索。优搜索。全局最佳优先搜索n算法：n1 把初始节点S0放入open表中，计算f(S0)n2 如果open表为空，则问题无解，退出。n3 把open表中选取第一个节点（节点n）从open表中移到closed表中。n4 考察节点n是否为目标节点，若是则求得问题的解，并退出；否则继续。全局最佳优先搜索n5 判断节点n是否可以扩展，如果不可以扩展则转向第2步，否则继续n6 对节点n进行扩展，并对它所有的后继节点计算估价函数f(x)的值，为每个后继节点设置指向n的指针。n7把所有的后继节点送入到open表中，然后对open表中所有的节点按照估价值从小到达进行排序。n8 转向第

29、2步全局最佳优先搜索n全局最佳优先搜索实际上是对宽度优先搜索和代价树宽度优先搜索的一个扩展，而宽度优先搜索和代价树宽度优先搜索可以认为是它的一个特例。全局最佳优先搜索n例题：n用全局最佳优先搜索方法求解八数码难题，假设八数码难题的初始状态和目标状态分别如下所示，请用全局最佳优先搜索算法来求解从S0到Sg的转换路径。最佳图搜索法n在启发式搜索中，估价函数的定义是非常重要的，如果定义的不好，则上述的搜索算法不一定能找到最优解，即便找到解，也不一定是最优解。所以必须要讨论如何对估价函数进行限制和定义。最佳图搜索法n良好的解n我们一般用启发能力的强弱来比较不同的搜索方法的效果。n在大多数实际问题中，让

30、人感兴趣的是路径耗散值和求解路经所需搜索的耗散值两者的组合最小。最佳图搜索法n良好的解n更为一般的情况下是考虑搜索方法对于所有可能预见的问题，其平均的组合耗散值最小。n启发式度量只能根据使用方法的实际经验作出判断，并没有必要去追求严格的最优结果。A算法n概述n启发式搜索算法A，一般简称为A算法n算法思想n定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点进行扩展。A算法n评价函数n形式：f(n)=g(n)+h(n)n其中n是要被评价的节点，n那么f(n)、g(n)和h(n)都表示什么哪？为此我们先看一下下面的几个函数的含义。A算法n解释：ng*(n):从初始节点S0到节点n之

31、间的最小代价路径的实际代价nh*(n):从节点n到目标节点Sg的最小代价路径的代价nf*(n)=g*(n)+h*(n)nf*(n):表示节点S0到节点n的一条最佳路径的实际代价加上从节点n到目标节点的一条最佳路径的代价之和。A算法nf(n),g(n)和h(n)则分别是对上面的三个函数的估计值，是一种预测。nA算法就是按照这种预测，来达到有效搜索的目的。A算法n启发式搜索算法An1 把初始节点S0放入open表中，令f(S0)=0n2 如果open表为空，则问题无解，退出。n3 把open表中选取第一个节点（节点n）从open表中移到closed表中。n4 考察节点n是否为目标节点，若是则求得问题的解，并退出；否则继续.n5如果节点n可扩展，则转6，否则转2A算法n6 扩展节点n，