人工智能原理2章搜索技术下

,*,人工智能原理,第,2,章 搜索技术（下）,1,本章内容,2.1,搜索与问题求解,2.2,无信息搜索策略,2.3,启发式搜索策略,2.4,局部搜索算法,2.5,约束满足问题,2.6,博弈搜索,参考书目附录,A*,算法可采纳性的证明,第,2,章 搜索技术,2,2.4,局部搜索算法,2.4.1,局部搜索与最优化,2.4.2,爬山法搜索,2.4.3,模拟退火搜索,2.4.4,局部剪枝搜索,2.4.5,遗传算法,第,2,章 搜索技术,3,局部搜索算法,前面的搜索算法都是保留搜索路径的，到达目标的路径就是问题的解,然而许多问题中到达目标的路径是无关紧要的,与系统地搜索状态空间,(,保留各种路径,),相对，不关心路径的搜索算法就是局部搜索算法,局部搜索从一个单独的当前状态出发，通常只移动到相邻状态,典型情况下搜索的路径不保留,第,2,章 搜索技术,4,局部搜索算法的应用,集成电路设计,工厂场地布局,车间作业调度,自动程序设计,电信网络优化,车辆寻径,文件夹管理,第,2,章 搜索技术,5,2.4.1,局部搜索与最优化问题,局部搜索算法的优点：,只使用很少的内存,(,通常是一个常数,),经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解,最优化问题,根据一个目标函数找到最佳状态,/,只有目标函数，而不考虑,(,没有,),“目标测试,”,和“路径耗散”,局部搜索算法适用于最优化问题,第,2,章 搜索技术,6,状态空间地形图,(1),第,2,章 搜索技术,山肩,目标函数,全局最大值,局部最大值,“平坦”局部最大值,状态空间,当前状态,7,状态空间地形图,(2),在状态图中，既有“位置”,(,用状态表示,),又有“高度,”(,用耗散值或目标函数值表示,),如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点,如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰,如果存在解，则完备的局部搜索算法能够找到解,而最优的局部搜索算法能够找到全局最大或最小值,第,2,章 搜索技术,8,局部搜索算法,本节简要介绍以下,4,种局部搜索算法,/,介绍其算法思想,爬山法搜索,模拟退火搜索,局部剪枝搜索,遗传算法,从搜索的角度看遗传算法也是搜索假设空间的一种方法,(,学习问题归结为搜索问题,),生成后继假设的方式,第,2,章 搜索技术,9,2.4.2,爬山法搜索,爬山法,(hill-climbing),就是向值增加的方向持续移动,登高过程,/,如果相邻状态中没有比它更高的值，则算法结束于顶峰,爬山法搜索算法思想：,(1),令初始状态,S,0,为当前状态,(2),若当前状态已经达标，则算法运行结束，搜索成功,(3),若存在一个动作可以作用于当前状态以产生一个新状态，使新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转,(2),(4),取当前状态为相对最优解，停止执行算法,第,2,章 搜索技术,10,爬山法搜索的局限,爬山法是一种局部贪婪搜索，不是最优解算法,(,或是不完备的,) /,其问题是：,局部极大值,比其邻居状态都高的顶峰，但是小于全局最大值,(,参照状态空间地形图,),山脊,一系列的局部极大值,高原,评价函数平坦的一块区域,(,或者山肩,),第,2,章 搜索技术,11,爬山法搜索的变形,爬山法的变形,随机爬山法,随机选择下一步,首选爬山法,随机选择直到有优于当前节点的下一步,随机重新开始爬山法,随机生成初始状态，进行一系列爬山法搜索,这时算法是完备的概率接近,1,第,2,章 搜索技术,12,2.4.3,模拟退火搜索,将爬山法,(,停留在局部山峰,),和随机行走以某种方式结合，以同时获得完备性和效率,模拟退火的思想,想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中,如果只让其在表面滚动，则它只会停留在局部极小点,/,如果晃动平面，可以使乒乓球弹出局部极小点,/,技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出,第,2,章 搜索技术,13,模拟退火的解决思路,(1),思路,开始使劲晃动,(,先高温加热,),然后慢慢降低摇晃的强度,(,逐渐降温,),退火过程,算法的核心,移动选择,选择随机移动，如果评价值改善，则移动被接受，否则以某个小于,1,的概率接受,概率按照移动评价值变坏的梯度,E,而呈指数级下降,/,同时也会随着作为控制的参数,“温度,”T,的降低,(,数值减小,),而降低,接受概率,=e,E,/T,(,注意此时,E,0),第,5,章 搜索技术,14,模拟退火的解决思路,(2),温度,T,是时间的函数，按照模拟退火的思想，数值应该逐渐减小,(,降温,),因为,接受概率,=e,E,/T,且,E,n,则此约束不能被满足,相应算法,删除约束中只有单值值域的变量，将其取值从其余变量值域中删去；对单值变量重复此过程；如果得到空值域或剩下的变量数大于取值数，则产生矛盾,其他约束,资源约束,/,边界约束,第,2,章 搜索技术,44,2.5.5,关于失败变量的启发式,在回溯算法中，当发现不满足约束即搜索失败时，则回到上一个变量并尝试下一个取值,称为历时回溯,/,在很多情况下这样做是效率很低的,因为问题并不决定于上一个,(,甚至几个,),变量的取值,所以，回溯应该倒退到导致失败的变量集合中的一个变量,该集合称为冲突集,变量,X,的,冲突集是通过约,束与,X,相连接的先前已赋值变量的集合,第,2,章 搜索技术,45,冲突集,对于地图染色问题，设有不完全赋值,Q=red, NSW=green, V=blue, T=red /,此时，,SA,赋值将发现不满足任何约束,SA,的冲突集,=Q, NSW, V,对于前向检验算法，可以很容易得到冲突集,基于,X,赋值的前向检验从变量,Y,的值域中删除一个值时，说明,X,和,Y,存在冲突，则显然,X,是,Y,的冲突集中的一个变量,当到达,Y,时，可知回溯到哪个变量,第,2,章 搜索技术,46,后向跳转,回溯检验导致失败的变量的赋值,后向跳转：回溯到冲突集中时间最近,(,最后赋值,),的变量,每个被后向跳转剪枝的分支在前向检验算法中也被剪枝,简单的后向跳转在前向检验,(,弧相容性检验,),搜索中是多余的,因为都是做取值相容的检测，只要在弧相容检验时增加一个变量集合记录即可,第,2,章 搜索技术,47,冲突指导的后向跳转,变量的冲突集更一般的情况,前面的变量集合中全部变量,(,不是其中一个变量,),使得当前变量与之冲突,冲突指导的后向跳转处理,令,Xj,是当前变量，,conf(Xj),是其冲突集，如果,Xj,每个可能取值都失败了，则后向跳转到,conf(Xj),中最近的一个变量,Xi,令,conf(Xi)=conf(Xi),conf(Xj)-Xi,从,Xi,向前是无解的,/,从,Xi,回到某个以前的变量赋值,(,参考,p116,例子,),第,2,章 搜索技术,48,2.6,博弈搜索,2.6.1,极大极小决策,2.6.2,-,剪枝,第,2,章 搜索技术,49,博弈搜索问题与方法,从智能体角度看，博弈是多智能体之间的竞争和对抗,/,在竞争的环境中，每个智能体的目的是冲突的，由此引出对抗搜索问题,称为博弈,本节探讨两个问题,如何搜索到取胜的路径,/,如何提高搜索效率,相应的方法,最优策略,(,极大极小决策,)/,-,剪枝,第,2,章 搜索技术,50,博弈游戏的描述,两个游戏者的博弈可以定义为一类搜索问题，其中包括：,初始状态,棋盘局面和哪个游戏者出招,后继函数,返回,(,招数,状态,),对的一个列表，其中每对表示一个合法招数和相应的结果状态,终止测试,判断游戏是否结束,效用函数,或称目标函数，对终止状态给出一个数值如输赢和平局,(,以,-1/+1/0,表示,),双方的初始状态和合法招数定义了游戏的博弈树,此为博弈搜索,第,2,章 搜索技术,51,井字棋的博弈树,第,2,章 搜索技术,X,X,X,X,X,X,X,X,X,X,O,O,X,X,O,X,O,X,X,O,X,X,O,X,X,O,X,X,O,O,X,O,O,X,X,X,X,O,O,X,X,O,X,O,O,X,MAX(X),MIN(O),MAX(X),MIN(O),TERMINAL,效用,-1,0,+1,52,2.6.1,极大极小决策,博弈搜索中，最优解是导致取胜的终止状态的一系列招数,在井字棋搜索树中，,因为,MAX,先行，所以,MAX,的任务是利用搜索树确定最佳招数,/,但是另一方,MIN,也有发言权,因此,MAX,制定取胜策略时必须不断地考虑,MIN,应对条件下如何取胜,即,MAX,初始状态下应该采取什么招数，然后是,MIN,应对造成的状态下,MAX,采取的招数，接着继续考虑下一步应对后的招数,.,第,2,章 搜索技术,53,极大极小值,(1),假设一个两层的博弈树,(,因为即使是井字棋的博弈树也太复杂了,),，其中有,MAX,节点和,MIN,节点,博弈树中，每个单方的招数,(,或称走步,),是一层,/,双方各走一招称为一步,(,博弈树的深度是一步的,),给定一棵博弈树，最优策略可以通过检查每个节点的极大极小值来决定,记为,MAX-MIN(n),，所以也称为极大极小决策,第,2,章 搜索技术,54,极大极小值,(2),如果博弈双方都按照最优策略进行，那么一个节点的极大极小值就是对应状态的效用值,(,对应,MAX),对于某个节点，极大极小函数如下定义,MAX,优先选择有极大值的状态,/ MIN,则选择有极小值的状态,第,5,章 搜索技术,55,极大极小值,(3),第,2,章 搜索技术,3 12 8 2 4 6 14 5 2,A,B,D,C,3,2,2,3,MAX,MIN,MAX,56,极大极小值,(4),图中,MAX,先行，有,3,个后继,MIN,节点，此时,MAX,的取值必须看,MIN,如何取值,每个,MIN,节点亦有,3,个后继,MAX,节点，假设其取值已知,因为,MIN,节点只取其后继节点中之最小者,(,让,MAX,效用最小,),，故,B=3/C=2/D=2,MAX,节点取,A/B/C,中最大者，故,A=3,最后根节点,A,的极大极小函数值,=3,引向具有最高极大极小值的后继,第,2,章 搜索技术,57,极大极小值算法说明,简单的递归算法,按照定义计算每个后继节点的极大极小值,/,搜索是从目标到初始节点的反向推导,算法对博弈树实行了深度优先搜索,如果博弈树的最大深度为,m,，每个节点的合法招数为,b,，则,算法的时间复杂度是,O(b,m,),每次生成全部后继节点的空间复杂度是,O(bm),每次只生成一个后继节点的空间复杂度是,O(m),第,2,章 搜索技术,58,极大极小值算法,Function,MAX-MIN-DECISION(,state,),returns,an action,inputs:,state,(current state in game),v MAX-VALUE(state),return,the,action,in SUCCESSORS(,state,) with value v,Function,MAX-VALUE(,state,),returns,a utility value,if,TERMINAL-TEST(state),then return,UTILITY(,state,),v,-,for,a, s,in SUCCESSORS(,state,),do,v MAX(v, MIN-VALUE(,s,),return,v(a=action,招数,),Function,MIN-VALUE(,state,),returns,a utility value,if,TERMINAL-TEST(,state,),then return,UTILITY(,state,),v +,for,a, s,in SUCCESSORS(,state,),do,v MIN(v, MAX-VALUE(,s,),return,v,第,2,章 搜索技术,59,2.6.2,-,剪枝,极大极小值搜索的问题是状态数随着棋局步数的数量而指数级增长,不幸的是没有办法消除这种指数级增长，所幸的是可以有效将其减半,剪枝技术,应用于极大极小值搜索树中,-,剪枝,剪掉那些不可能影响最后决策的分支，返回和极大极小值算法同样的结果,例子的剪枝过程中,MAX-MIN(n)=max(min(3,12,8), min(2,x,y), min(14,5,2)=max(3,min(2,x,y),2)=max(3,z,2)=3,第,2,章 搜索技术,60,博弈树的剪枝,(1),第,2,章 搜索技术,3,-, +,A,B,-,3,(a),-, +,12,A,B,3,-,3,(b),61,博弈树的剪枝,(2),第,2,章 搜索技术,12,A,B,3, +,3,8,3,3,(c),12,A,B,C,3, +,-,2,3,8,2,3,3,(d),62,博弈树的剪枝,(3),第,2,章 搜索技术,-,14,12,A,B,D,C,3,14,-,2,3,8,2,14,3,3,(e),12,A,B,D,C,3,3,-,2,2,2,3,8,2,14,5,2,3,3,(f ),63,-,剪枝算法,(1),在极大极小值算法基础上增加了剪枝功能，即在返回值基础上增加了判断,Function,ALPHA-BETA-SEARCH(,state,),returns,an action,inputs:,state,(current state in game),v MAX-VALUE(,state,-, +),return,the,action,in SUCCESSORS(,state,) with value v,第,2,章 搜索技术,64,-,剪枝算法,(2),Function,MAX-VALUE(,state, ,),returns,a utility value,inputs:,state, the value of the best alternative for MAX along the path to,state, the value of the best alternative for MIN along the path to,state,if,TERMINAL-TEST(,state,),then return,UTILITY(,state,),v,-,for,a, s,in SUCCESSORS(,state,),do,v MAX(v, MIN-VALUE(,s, ,),if,v,then return,v, MAX(, v),return,v,第,2,章 搜索技术,65,-,剪枝算法,(3),Function,MIN-VALUE(,state, ,),returns,a utility value,inputs:,state,the value of the best alternative for MAX along the path to,state,the value of the best alternative for MIN along the path to,state,if,TERMINAL-TEST(,state,),then return,UTILITY(,state,),v +,for,a, s,in SUCCESSORS(,state,),do,v MIN(v, MAX-VALUE(,s, ,),if,v,then return,v, MIN(, v),return,v,第,2,章 搜索技术,66,-,剪枝算法的说明,-,剪枝,可以应用树的任何深度，许多情况下可以剪掉整个子树,/,其原则是,如果在节点,n,的父节点或者更上层的节点有一个更好的选择,m,，则在实际游戏,(,搜索,),中永远不会到达,n,=,到目前为止在路径上任意点发现的,MAX,最佳选择,=,到目前为止在路径上任意点发现的,MIN,最佳选择,-,搜索不断更新,/,值，当某个节点的值分别比,/,值更差时剪掉该节点的剩余分支,第,2,章 搜索技术,67,-,剪枝的效率,-,剪枝的效率很大程度上取决于检查后继节点的次序,应该先检查那些可能最好的后继,如果能够先检查那些最好的后继，则,-,剪枝算法只需检查,O(b,d/2,),个节点以决定最佳招数,/,极大极小值算法为,O(b,d,),有效分支因子,b,到,b,的平方根,效率大大提高,第,2,章 搜索技术,68,本章复习提示,尝试使用搜索方式求解问题,/,注意本章的搜索算法都是通用算法，即没有考虑具体任务的相关知识,具体搜索问题的形式化表示,(,初始状态,/,后继函数,/,搜索代价等,),了解各种搜索算法,(,包括局部搜索和博弈搜索,),的思想、相关性质和性能,尝试用启发式搜索算法,(A*,算法,),解决一些游戏问题,约束满足问题的相关概念,第,2,章 搜索技术,69,参考书目,Stuart Russell / Peter Norvig: AIMA,第,3,章,/,第,4,章,/,第,5,章,/,第,6,章,陆汝钤 编著,:,人工智能,(,上册,),第,5,章,/,第,6,章,/,第,8,章,/,第,9,章,田盛丰、黄厚宽，人工智能与知识工程，中国铁道出版社，,1999,年,8,月第,1,版，第,4,章,/,第,9,章,第,2,章 搜索技术,70,附录,A*,算法可采纳性的证明,第,2,章 搜索技术,71,A*,算法可采纳性,定理：,A*,算法是可采纳的，即若存在从初始节点,S,0,到目标节点,Sg,的路径，则,A*,算法必能结束在最佳路径上,证明的过程：,首先证明,A*,算法必定成功结束,其次证明,A*,算法结束时中止于最佳路径,第,2,章 搜索技术,72,证明的步骤,证明分为三步：,(1),对于有限图，,A*,算法一定成功结束,(2),对于无限图，,A*,算法一定成功结束,(3)A*,算法必定终止于最佳路径上,对于无限图情况的证明，引入,2,个引理,(1),如果,A*,算法不终止，则存在,f,值任意大的节点,(2)A*,算法结束前，仍有耗散值更小的节点待扩展,第,2,章 搜索技术,73,定理,1,的证明,(1),定理,1,对于有限图，如果从初始节点,S,0,到目标节点,Sg,有路径存在，则,A*,算法一定成功结束,证明：,首先证明算法必定会结束,由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，则必然会由于,Open,表变空而结束。因此，,A*,算法必然会结束,第,2,章 搜索技术,74,定理,1,的证明,(2),然后证明算法一定会成功结束,由于至少存在一条由初始节点到目标节点的路径，设此路径为,S,0,= n,0,，,n,1,，,，,n,k,=Sg,算法开始时，节点,n,0,在,Open,表中，而且路径中任一节点,n,i,离开,Open,表后，其后继节点,n,i+1,必然进入,Open,表，这样，在,Open,表变为空之前，目标节点必然出现在,Open,表中,/,因此，算法必定会成功结束,第,2,章 搜索技术,75,引理,1,的证明,(1),引理,1,对无限图，如果从初始节点,S,0,到目标节点,Sg,有路径存在，且,A*,算法不终止的话，则从,Open,表中选出的节点必将具有任意大的,f,值,证明：,设,d*(n),是,A*,算法生成的从初始节点,S,0,到节点,n,的最短路径长度，由于搜索图中每条边的代价都是一个正数，令这些正数中最小的一个数是,e,则有,第,2,章 搜索技术,76,引理,1,的证明,(2),因为是最佳路径的代价，故有,又因为,h(n),0,，故有,如果,A*,算法不终止的话，从,Open,表中选出的节点必将具有任意大的,d*(n),值，因此，也将具有任意大的,f,值,第,2,章 搜索技术,77,引理,2,的证明,(1),引理,2,在,A*,算法终止前的任何时刻，,Open,表中总存在节点,n,，它是从初始节点,S,0,到目标节点的最佳路径上的一个节点，且满足,证明：,设从初始节点,S,0,到目标节点,t,的最佳路径序列为,S,0,= n0,，,n1,，,，,nk =Sg,算法开始时，节点,S,0,在,Open,表中，当节点,S,0,离开,Open,进入,Closed,表时，节点,n,1,进入,Open,表,第,2,章 搜索技术,78,引理,2,的证明,(2),因此，,A*,没有结束以前，在,Open,表中必存在最佳路径上的节点,设这些节点排在最前面的节点为,n,则有,f(n,)=,g(n)+h(n,),由于,n,在最佳路径上，故有,g(n,)=g*(n),从而,f(n,)=g*(,n)+h(n,),又由于,A*,算法满足,h(n),h,*(n),故有,f(n)g,*(,n)+h,*(n)=f*(n),因为在最佳路径上的所有节点的,f*,值都应相等，因此有,f(n)f,*(S,0,),第,2,章 搜索技术,79,定理,2,的证明,定理,2,对于无限图，如果从初始节点,S,0,到目标节点,Sg,有路径存在，则,A*,算法必然会结束,证明：,(,反证法,),假设,A*,算法不结束，由引理,1,知,Open,表中的节点有任意大的,f,值，这与引理,2,的结论相矛盾，因此，,A*,算法只能成功结束,推论,1Open,表中任一具有,f(n),f(S,0,),的节点,n,，最终都被,A*,算法选作为扩展节点,第,2,章 搜索技术,80,定理,3,的证明,(1),定理,3A*,算法是可采纳的，即若存在从初始节点,S,0,到目标节点,Sg,的路径，则,A*,算法必能结束在最佳路径上,证明：,证明过程分以下两步进行,先证明,A*,算法一定能够终止在某个目标节点上,由定理,1,和定理,2,可知，无论是对有限图还是无限图，,A*,算法都能够找到某个目标节点而结束,第,2,章 搜索技术,81,定理,3,的证明,(2),再证明,A*,算法只能终止在最佳路径上,(,反证法,),假设,A*,算法未能终止在最佳路径上，而是终止在某个目标节点,Sg,处，则有,f(Sg)=g(Sg)f*(S,0,),由引理,2,可知，在,A*,算法结束前，必有最佳路径上的一个节点,n,在,Open,表中且有,f(n),f*(S,0,)f(Sg),这时，,A*,算法一定会选择,n,来扩展，而不可能选择,Sg,，从而也不会去测试目标节点,Sg,，这就与假设,A*,算法终止在目标节点相矛盾,/,因此，,A*,算法只能终止在最佳路径上,第,2,章 搜索技术,82,推论,2,推论,2,在,A*,算法中，对任何被扩展的任一节点,n,，都有,f(n),f*(S,0,),证明：,令,n,是由,A*,选作扩展的任一节点，因此,n,不会是目标节点，且搜索没有结束,/,由引理,2,可知，在,Open,表中有满足,f(n)f*(S,0,),的节点,n,若,n=n,则有,f(n)f*(S,0,),否则，,算法既然选择,n,扩展，那就必有,f(n)f(n),所以有,f(n)f*(S,0,),第,2,章 搜索技术,83,