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

《人工智能原理第2章搜索技术下.ppt》由会员分享，可在线阅读，更多相关《人工智能原理第2章搜索技术下.ppt（83页珍藏版）》请在三一办公上搜索。

1、人工智能原理第2章 搜索技术（下）,本章内容2.1 搜索与问题求解2.2 无信息搜索策略2.3 启发式搜索策略2.4 局部搜索算法2.5 约束满足问题2.6 博弈搜索参考书目附录 A*算法可采纳性的证明,第2章 搜索技术,2.4 局部搜索算法2.4.1 局部搜索与最优化2.4.2 爬山法搜索2.4.3 模拟退火搜索2.4.4 局部剪枝搜索2.4.5 遗传算法,第2章 搜索技术,4,局部搜索算法,前面的搜索算法都是保留搜索路径的，到达目标的路径就是问题的解然而许多问题中到达目标的路径是无关紧要的与系统地搜索状态空间(保留各种路径)相对，不关心路径的搜索算法就是局部搜索算法局部搜索从一个单独的当前

2、状态出发，通常只移动到相邻状态典型情况下搜索的路径不保留,第2章 搜索技术,5,局部搜索算法的应用,集成电路设计工厂场地布局车间作业调度自动程序设计电信网络优化车辆寻径文件夹管理,第2章 搜索技术,6,2.4.1 局部搜索与最优化问题,局部搜索算法的优点：只使用很少的内存(通常是一个常数)经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解最优化问题根据一个目标函数找到最佳状态/只有目标函数，而不考虑(没有)“目标测试”和“路径耗散”局部搜索算法适用于最优化问题,第2章 搜索技术,7,状态空间地形图(1),第2章 搜索技术,8,状态空间地形图(2),在状态图中，既有“位置”(用状态表示

3、)又有“高度”(用耗散值或目标函数值表示)如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰如果存在解，则完备的局部搜索算法能够找到解而最优的局部搜索算法能够找到全局最大或最小值,第2章 搜索技术,9,局部搜索算法,本节简要介绍以下4种局部搜索算法/介绍其算法思想爬山法搜索模拟退火搜索局部剪枝搜索遗传算法从搜索的角度看遗传算法也是搜索假设空间的一种方法(学习问题归结为搜索问题)生成后继假设的方式,第2章 搜索技术,10,2.4.2 爬山法搜索,爬山法(hill-climbing)就是向值增加的方向持续移动登高过程/如果相邻状态

4、中没有比它更高的值，则算法结束于顶峰爬山法搜索算法思想：(1)令初始状态S0为当前状态(2)若当前状态已经达标，则算法运行结束，搜索成功(3)若存在一个动作可以作用于当前状态以产生一个新状态，使新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转(2)(4)取当前状态为相对最优解，停止执行算法,第2章 搜索技术,11,爬山法搜索的局限,爬山法是一种局部贪婪搜索，不是最优解算法(或是不完备的)/其问题是：局部极大值比其邻居状态都高的顶峰，但是小于全局最大值(参照状态空间地形图)山脊一系列的局部极大值高原评价函数平坦的一块区域(或者山肩),第2章 搜索技术,12,爬

5、山法搜索的变形,爬山法的变形随机爬山法随机选择下一步首选爬山法随机选择直到有优于当前节点的下一步随机重新开始爬山法随机生成初始状态，进行一系列爬山法搜索这时算法是完备的概率接近1,第2章 搜索技术,13,2.4.3 模拟退火搜索,将爬山法(停留在局部山峰)和随机行走以某种方式结合，以同时获得完备性和效率模拟退火的思想想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中如果只让其在表面滚动，则它只会停留在局部极小点/如果晃动平面，可以使乒乓球弹出局部极小点/技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出,第2章 搜索技术,14,模拟退火的解决思路(1),思路开始使劲晃动

6、(先高温加热)然后慢慢降低摇晃的强度(逐渐降温)退火过程算法的核心移动选择选择随机移动，如果评价值改善，则移动被接受，否则以某个小于1的概率接受概率按照移动评价值变坏的梯度E而呈指数级下降/同时也会随着作为控制的参数“温度”T的降低(数值减小)而降低接受概率=eE/T(注意此时E 0),第5章 搜索技术,15,模拟退火的解决思路(2),温度T是时间的函数，按照模拟退火的思想，数值应该逐渐减小(降温)因为接受概率=eE/T且E 0，所以当温度高时，接受概率较大(接近1)/而T越来越低时，E/T变大，因而接受概率降低可以证明，如果T下降得足够慢，则算法找到全局最优解的概率接近1,第5章 搜索技术,

7、16,2.4.4 局部剪枝搜索,基本思想与只从一个单独的起始状态出发不同，局部剪枝搜索从k个随机生成的状态开始，每步生成全部k个状态的所有后继状态/如果其中之一是目标状态，算法停止；否则从全部后继状态中选择最佳的k个状态继续搜索在局部剪枝搜索过程中，有用的信息在k个并行的搜索线程之间传递算法会很快放弃没有成果的搜索而把资源放在取得最大进展的搜索上,第2章 搜索技术,17,随机剪枝搜索,如果k个状态缺乏多样性，则局部剪枝搜索会受其影响，性能变差算法的变种随机剪枝搜索帮助缓解这一问题随机剪枝搜索不是选择最好的k个后代，而是按照一定概率随机地选择k个后继状态/选择给定后继状态的概率是状态值的递增函数

8、类似于自然选择过程状态对应生物体，其值对应于适应性，后代就是后继状态,第2章 搜索技术,18,2.4.5 遗传算法,遗传算法(generic algorithm/GA)是随机剪枝的变种不是通过修改单一状态而是通过把两个父状态结合以生成后继状态与剪枝搜索一样，遗传算法也是从k个随机状态开始这k个状态称为种群，每个状态称为个体个体用有限长的字符串(通常为0/1串)表示每个状态用其评价函数(适应度函数)给出评价值(适应值)随后的操作包括选择/杂交/变异,第2章 搜索技术,19,遗传算法的操作,选择(或者称繁殖)按照一定概率随机地选择两对个体进行繁殖(即生成后继状态)杂交(或者称交叉)杂交点是在表示状

9、态的字符串中随机选择的一个位置，以此形成新状态后代是父串在杂交点上进行杂交(各取一部分)得来的变异在新生成的串中各个位置都会按照一个独立的小概率随机变异,第2章 搜索技术,20,遗传算法简要描述,(1)定义问题和目标函数(2)选择候选解作为初始种群，每个解作为个体用二进制串表示(个体相当于染色体，其中的元素相当于基因)(3)根据目标函数，对于每个个体计算适应函数值(4)为每个个体指定一个与其适应值成正比的被选择概率(繁殖概率)(5)根据概率选择个体，所选个体通过交叉/变异等操作产生新一代种群(6)如果找到了解或者某种限制已到，则过程结束；否则转(3),第2章 搜索技术,21,遗传算法的特点,遗

10、传算法也结合了“上山”趋势和随机搜索，并在并行搜索线程之间交换信息遗传算法的主要优势来自于杂交数学上可以证明，如果基因编码的位置在初始时就随机转换的话，杂交就没有优势杂交的优势在于它能够将独立发展的若干个相对固定的字符(能够执行有用的功能“砖块”)组合起来，提高了搜索的粒度所谓有用的砖块，就是几个结合起来可以构造问题的解参见书中的八皇后问题举例,第2章 搜索技术,22,遗传算法的模式,遗传算法上述特点可以用模式(schema)来解释模式是某些位置上的数字尚未确定的一个状态子串能够匹配模式的字符串称为该模式的实例如果一个模式的实例的平均适应值超过均值，则种群内这个模式的实例数量会随时间而增长遗传

11、算法在模式和解的有意义成分相对应时才会工作得最好遗传算法有很多应用，但是在什么情况下它会达到好效果，还有很多研究要做,第2章 搜索技术,2.5 约束满足问题2.5.1 约束满足问题的定义2.5.2 CSP的回溯搜索2.5.3 变量赋值次序的启发式2.5.4 变量约束的启发式2.5.5 关于失败变量的启发式,第2章 搜索技术,24,2.5.1 约束满足问题的定义,约束满足问题(Constraint Satisfying Problem,CSP)由一个变量集合X1Xn和一个约束集合C1Cm定义每个变量都有一个非空可能值域Di每个约束指定了包含若干变量的一个子集内各变量的赋值范围CSP的一个状态对一

12、些或全部变量的赋值 Xi=vi,Xj=vj,第2章 搜索技术,25,CSP问题的解,一个不违反任何约束的对变量的赋值称为相容赋值或合法赋值对每个变量都进行赋值称为完全赋值一个(一组)既是相容赋值又是完全赋值的对变量的赋值就是CSP问题的解CSP问题常常可以可视化，表示为约束图，更直观地显示问题，帮助思考问题的答案,第2章 搜索技术,26,从搜索角度看待CSP问题,CSP看作搜索问题的形式化初始状态空赋值集合，所有变量都是未赋值的后继函数给未赋值的变量一个赋值，要求该赋值与先前的变量赋值不冲突目标测试测试当前的赋值(组)是否是完全赋值路径耗散每步耗散均为常数(1)每个解必须为完全赋值/如果有n个

13、变量，则解出现的深度为n(有限)/常使用深度优先搜索,第2章 搜索技术,27,例1：澳大利亚地图染色问题(1),澳大利亚地图：用红绿蓝3色标出各省，相邻者颜色不同,第2章 搜索技术,28,对应于澳大利亚地图的约束图,相互关联的节点用边连接,第5章 搜索技术,例1：澳大利亚地图染色问题(2),WA,NT,SA,NSW,Q,V,T,西澳大利亚 WA北领地 NT南澳大利亚 SA昆士兰 Q新南威尔士 NSW维多利亚 V塔斯马尼亚 T一组满足约束的完全赋值 WA=R,NT=G,Q=R,SA=B,NSW=G,V=R,T=R,29,例2：密码算术问题(1),算式T W O+T W O F O U R直观地求

14、解此问题：F=1如不考虑O/U有进位，则R/U/O为偶数R=4,6,8 O=2?,3?,4!R=8/O=4则T=7(由O/R/U/W共同限制)T=7则U=6/W=3 由此得到一组解1468|734考虑U有进位：R=0,2,4,6,8 O=5,R=0/O=5(有进位)/T=7/W=6/U=3 解=1530|765,第2章 搜索技术,30,各算式约束,四列算式约束O+O=R+10*X1X1+W+W=U+10*X2X2+T+T=O+10*X3X3=F对应的约束超图如右六个变量互不相等约束可化为两两不等约束二元约束,第2章 搜索技术,例2：密码算术问题(2),F,T,W,U,O,R,X3,X1,X2,

15、约束：互不相等，两两不等,31,CSP问题的分类,变量离散值域 有限值域如地图染色问题无限值域如作业规划，要使用约束语言(线性约束/非线性约束)变量连续值域如哈勃望远镜实验日程安排/线性规划问题约束的类型一元约束只限制一个变量的取值二元约束与2个变量相关高阶约束涉及3个或更多变量,第2章 搜索技术,32,CSP问题求解的复杂度,搜索相容的完全赋值，最朴素的想法是依次取变量的赋值组合并检查其是否满足约束条件指数级计算量若CSP问题的任何一个变量的最大值域为d，那么可能的完全赋值数量为O(dn)有限值域CSP问题包括布尔CSP问题其中有一些NP完全问题，如3SAT问题(命题逻辑语句的可满足性)/最

16、坏情况下不会指望低于指数级时间复杂性解决该问题,第2章 搜索技术,33,2.5.2 CSP的回溯搜索,CSP问题具有一个性质：可交换性变量赋值的顺序对结果没有影响/所有CSP搜索算法生成后继节点时，在搜索树每个节点上只考虑单个变量的可能赋值CSP问题的求解使用深度优先的回溯搜索算法思想：每次给一个变量赋值，当没有合法赋值(不满足约束时)就要推翻前一个变量的赋值，重新给其赋值，这就是回溯,第2章 搜索技术,34,简单回溯法生成的搜索树,澳大利亚地图染色问题的搜索树,第2章 搜索技术,35,回溯搜索的通用算法,可以改善上述无信息搜索算法的性能，这些改进是一些通用性的考虑：变量赋值的次序对性能的影响

17、在若干变量已经赋值的条件下，如果下一步赋值有多个选择，该选择哪一个？当前变量的赋值会对其他未赋值变量产生什么约束？怎样利用这种约束以提高效率？当遇到某个失败的变量赋值时，怎样避免同样的失败？就是说找到对这种失败起到关键作用的某个变量赋值,第2章 搜索技术,36,2.5.3 变量赋值次序的启发式,随机的变量赋值排序难以产生高效率的搜索如：在WA=red/NT=green条件下选取SA赋值比Q要减少赋值次数(1:2)/并且一旦给定SA赋值以后，Q/NSW/V的赋值只有一个选择因此，选择合法取值最少的变量或者称为最少剩余值(MRV)启发式，或者称为最受约束变量/失败优先启发式称为失败优先启发式是因为

18、它可以很快找到失败的变量，从而引起搜索的剪枝，避免更多导致同样失败的搜索,第2章 搜索技术,37,MRV启发式,当有多个变量需要选择时优先选择在当前约束下取值最少的变量当赋值的变量有多个值选择时优先选择为剩余变量的赋值留下最多选择的赋值如，WA=red/NT=green时，如果给Q赋值，则Q=blue的选择不好，此时SA没有一个可选择的了如果要找出问题的所有解，则排序问题无所谓,第2章 搜索技术,38,度启发式,对于初始节点，选择什么变量更合适？度启发式选择涉及对其他未赋值变量的约束数量大(与其他变量关联最多)的变量地图染色例子中，度(SA)=5/其他均为2/3实际上，一旦选择了SA作为初始节

19、点，应用度启发式求解本问题，则可以不经任何回溯就找到解SA=red NT=green Q=blue NSW=green WA=blue V=blue,第2章 搜索技术,39,2.5.4 变量约束的启发式,在搜索中尽可能早地考虑某些约束，以便减少搜索空间前向检验如果X被赋值，前向检验就是检查与X相连的那些变量Y，看看它们是否满足相关约束，去掉Y中不满足约束的赋值,第2章 搜索技术,WA=redQ=greenV=blue,蓝色字体为赋值结果,40,前向检验,地图染色问题中的前向检验前向检验与MRV启发式相结合实际上，MRV要做的就是向前找合适的变量赋值V=blue引起矛盾，此时SA赋值为空，不满足

20、问题约束算法就要立刻回溯注意这里只是检验一步，即和当前节点是否矛盾/至于被检验节点之间的约束检验还不能进行改进：约束传播,第2章 搜索技术,41,约束传播弧相容,约束传播将一个变量的约束内容传播到其他变量希望约束传播检验更多的变量/花费的代价更少快速弧相容依次检验约束图中各个相关节点对(这里弧是有向弧)例如：给定SA/NSW当前值域，对于SA的每个取值x，NSW都有某个y和x相容，则SA到NSW的弧是相容的/反过来是NSW到SA的弧相容,第2章 搜索技术,42,弧相容(1),在地图染色约束的前向检验图中：第三行SA=blue/NSW=red,blue，则SA的取值有一个NSW=red与之相容/

21、反过来NSW=blue，则SA为空值，即不相容通过删除NSW值域中的blue可使其相容同样，弧相容检测也能更早地发现矛盾如第二行SA/NT值域均为blue，如必须删去SA=blue，则发现不相容保持弧相容(MAC)算法思想反复检测某个变量值域中的不相容弧，进行值删除，直到不再有矛盾,第2章 搜索技术,43,弧相容(2),弧相容算法思想：用队列记录需要检验不相容的弧每条弧Xi,Xj依次从队列中删除并被检验，如果任何一个Xi值域中的值需要删除，则每个指向Xi的弧Xk,Xi都必须重新插入队列进行检验因为指向这个变量的弧可能产生新的不相容(因为原来可能就是因为这个值产生了它们之间的相容)时间复杂度二元

22、CSP约束至多有O(n2)条弧/每条弧至多插入队列d次(d个取值)，检验一条弧为O(d2)/算法最坏情况下为O(n2d2),第2章 搜索技术,44,特殊约束,实际问题中出现的特殊约束，其效率要比通用的约束高很多变量取值各不相同AllDiff，如果约束涉及m个变量，所有变量共有n个取值，如果mn则此约束不能被满足相应算法删除约束中只有单值值域的变量，将其取值从其余变量值域中删去；对单值变量重复此过程；如果得到空值域或剩下的变量数大于取值数，则产生矛盾其他约束资源约束/边界约束,第2章 搜索技术,45,2.5.5 关于失败变量的启发式,在回溯算法中，当发现不满足约束即搜索失败时，则回到上一个变量并

23、尝试下一个取值称为历时回溯/在很多情况下这样做是效率很低的因为问题并不决定于上一个(甚至几个)变量的取值所以，回溯应该倒退到导致失败的变量集合中的一个变量该集合称为冲突集变量X的冲突集是通过约束与X相连接的先前已赋值变量的集合,第2章 搜索技术,46,冲突集,对于地图染色问题，设有不完全赋值Q=red,NSW=green,V=blue,T=red/此时，SA赋值将发现不满足任何约束SA的冲突集=Q,NSW,V对于前向检验算法，可以很容易得到冲突集基于X赋值的前向检验从变量Y的值域中删除一个值时，说明X和Y存在冲突，则显然X是Y的冲突集中的一个变量当到达Y时，可知回溯到哪个变量,第2章 搜索技术

24、,47,后向跳转,回溯检验导致失败的变量的赋值后向跳转：回溯到冲突集中时间最近(最后赋值)的变量每个被后向跳转剪枝的分支在前向检验算法中也被剪枝简单的后向跳转在前向检验(弧相容性检验)搜索中是多余的因为都是做取值相容的检测，只要在弧相容检验时增加一个变量集合记录即可,第2章 搜索技术,48,冲突指导的后向跳转,变量的冲突集更一般的情况前面的变量集合中全部变量(不是其中一个变量)使得当前变量与之冲突冲突指导的后向跳转处理令Xj是当前变量，conf(Xj)是其冲突集，如果Xj每个可能取值都失败了，则后向跳转到conf(Xj)中最近的一个变量Xi令conf(Xi)=conf(Xi)conf(Xj)-

25、Xi从Xi向前是无解的/从Xi回到某个以前的变量赋值(参考p116例子),第2章 搜索技术,2.6 博弈搜索2.6.1 极大极小决策2.6.2-剪枝,第2章 搜索技术,50,博弈搜索问题与方法,从智能体角度看，博弈是多智能体之间的竞争和对抗/在竞争的环境中，每个智能体的目的是冲突的，由此引出对抗搜索问题称为博弈本节探讨两个问题如何搜索到取胜的路径/如何提高搜索效率相应的方法最优策略(极大极小决策)/-剪枝,第2章 搜索技术,51,博弈游戏的描述,两个游戏者的博弈可以定义为一类搜索问题，其中包括：初始状态棋盘局面和哪个游戏者出招后继函数返回(招数,状态)对的一个列表，其中每对表示一个合法招数和相

26、应的结果状态终止测试判断游戏是否结束效用函数或称目标函数，对终止状态给出一个数值如输赢和平局(以-1/+1/0表示)双方的初始状态和合法招数定义了游戏的博弈树此为博弈搜索,第2章 搜索技术,52,井字棋的博弈树,第2章 搜索技术,53,2.6.1 极大极小决策,博弈搜索中，最优解是导致取胜的终止状态的一系列招数在井字棋搜索树中，因为MAX先行，所以MAX的任务是利用搜索树确定最佳招数/但是另一方MIN也有发言权因此MAX制定取胜策略时必须不断地考虑MIN应对条件下如何取胜即MAX初始状态下应该采取什么招数，然后是MIN应对造成的状态下MAX采取的招数，接着继续考虑下一步应对后的招数.,第2章

27、搜索技术,54,极大极小值(1),假设一个两层的博弈树(因为即使是井字棋的博弈树也太复杂了)，其中有MAX节点和MIN节点博弈树中，每个单方的招数(或称走步)是一层/双方各走一招称为一步(博弈树的深度是一步的)给定一棵博弈树，最优策略可以通过检查每个节点的极大极小值来决定记为MAX-MIN(n)，所以也称为极大极小决策,第2章 搜索技术,55,极大极小值(2),如果博弈双方都按照最优策略进行，那么一个节点的极大极小值就是对应状态的效用值(对应MAX)对于某个节点，极大极小函数如下定义MAX优先选择有极大值的状态/MIN则选择有极小值的状态,第5章 搜索技术,56,极大极小值(3),第2章 搜索

28、技术,3 12 8 2 4 6 14 5 2,MAX,MIN,MAX,57,极大极小值(4),图中MAX先行，有3个后继MIN节点，此时MAX的取值必须看MIN如何取值每个MIN节点亦有3个后继MAX节点，假设其取值已知因为MIN节点只取其后继节点中之最小者(让MAX效用最小)，故B=3/C=2/D=2MAX节点取A/B/C中最大者，故A=3最后根节点A的极大极小函数值=3引向具有最高极大极小值的后继,第2章 搜索技术,58,极大极小值算法说明,简单的递归算法按照定义计算每个后继节点的极大极小值/搜索是从目标到初始节点的反向推导算法对博弈树实行了深度优先搜索如果博弈树的最大深度为m，每个节点的

29、合法招数为b，则算法的时间复杂度是O(bm)每次生成全部后继节点的空间复杂度是O(bm)每次只生成一个后继节点的空间复杂度是O(m),第2章 搜索技术,59,极大极小值算法,Function MAX-MIN-DECISION(state)returns an actioninputs:state(current state in game)v MAX-VALUE(state)return the action in SUCCESSORS(state)with value vFunction MAX-VALUE(state)returns a utility valueif TERMINAL-T

30、EST(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 valueif TERMINAL-TEST(state)then return UTILITY(state)v+for a,s in SUCCESSORS(state)do v MIN(v,MAX-VALUE(s)return v,第2章 搜索技术,60,2.6.2-剪枝,极大极小值搜索的问题是

31、状态数随着棋局步数的数量而指数级增长不幸的是没有办法消除这种指数级增长，所幸的是可以有效将其减半剪枝技术应用于极大极小值搜索树中-剪枝剪掉那些不可能影响最后决策的分支，返回和极大极小值算法同样的结果例子的剪枝过程中 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章 搜索技术,61,博弈树的剪枝(1),第2章 搜索技术,62,博弈树的剪枝(2),第2章 搜索技术,63,博弈树的剪枝(3),第2章 搜索技术,64,-剪枝算法(1),在极大极小值算法基础上增加了剪枝功能，即在返

32、回值基础上增加了判断Function ALPHA-BETA-SEARCH(state)returns an actioninputs:state(current state in game)v MAX-VALUE(state,-,+)return the action in SUCCESSORS(state)with value v,第2章 搜索技术,65,-剪枝算法(2),Function MAX-VALUE(state,)returns a utility valueinputs:state,the value of the best alternative for MAX along t

33、he path to state,the value of the best alternative for MIN along the path to stateif TERMINAL-TEST(state)then return UTILITY(state)v-for a,s in SUCCESSORS(state)dov MAX(v,MIN-VALUE(s,)if v then return v MAX(,v)return v,第2章 搜索技术,66,-剪枝算法(3),Function MIN-VALUE(state,)returns a utility valueinputs:stat

34、e,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 stateif TERMINAL-TEST(state)then return UTILITY(state)v+for a,s in SUCCESSORS(state)dov MIN(v,MAX-VALUE(s,)if v then return v MIN(,v)return v,第2章 搜索技术,67,-剪枝算法的说明,-剪枝可以应用树的

35、任何深度，许多情况下可以剪掉整个子树/其原则是如果在节点n的父节点或者更上层的节点有一个更好的选择m，则在实际游戏(搜索)中永远不会到达n=到目前为止在路径上任意点发现的MAX最佳选择=到目前为止在路径上任意点发现的MIN最佳选择-搜索不断更新/值，当某个节点的值分别比/值更差时剪掉该节点的剩余分支,第2章 搜索技术,68,-剪枝的效率,-剪枝的效率很大程度上取决于检查后继节点的次序应该先检查那些可能最好的后继如果能够先检查那些最好的后继，则-剪枝算法只需检查O(bd/2)个节点以决定最佳招数/极大极小值算法为O(bd)有效分支因子b到b的平方根效率大大提高,第2章 搜索技术,69,本章复习提

36、示,尝试使用搜索方式求解问题/注意本章的搜索算法都是通用算法，即没有考虑具体任务的相关知识具体搜索问题的形式化表示(初始状态/后继函数/搜索代价等)了解各种搜索算法(包括局部搜索和博弈搜索)的思想、相关性质和性能尝试用启发式搜索算法(A*算法)解决一些游戏问题约束满足问题的相关概念,第2章 搜索技术,70,参考书目,Stuart Russell/Peter Norvig:AIMA 第3章/第4章/第5章/第6章陆汝钤 编著:人工智能(上册)第5章/第6章/第8章/第9章田盛丰、黄厚宽，人工智能与知识工程，中国铁道出版社，1999年8月第1版，第4章/第9章,第2章 搜索技术,附录 A*算法可采

37、纳性的证明,第2章 搜索技术,72,A*算法可采纳性,定理：A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A*算法必能结束在最佳路径上证明的过程：首先证明A*算法必定成功结束其次证明A*算法结束时中止于最佳路径,第2章 搜索技术,73,证明的步骤,证明分为三步：(1)对于有限图，A*算法一定成功结束(2)对于无限图，A*算法一定成功结束(3)A*算法必定终止于最佳路径上对于无限图情况的证明，引入2个引理(1)如果A*算法不终止，则存在f值任意大的节点(2)A*算法结束前，仍有耗散值更小的节点待扩展,第2章 搜索技术,74,定理1的证明(1),定理1对于有限图，如果从初始节点

38、S0到目标节点Sg有路径存在，则A*算法一定成功结束证明：首先证明算法必定会结束由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因此，A*算法必然会结束,第2章 搜索技术,75,定理1的证明(2),然后证明算法一定会成功结束由于至少存在一条由初始节点到目标节点的路径，设此路径为S0=n0，n1，nk=Sg算法开始时，节点n0在Open表中，而且路径中任一节点ni离开Open表后，其后继节点ni+1必然进入Open表，这样，在Open表变为空之前，目标节点必然出现在Open表中/因此，算法必定会成功结束,第2章 搜索技术,76,引理1的证明

39、(1),引理1对无限图，如果从初始节点S0到目标节点Sg有路径存在，且A*算法不终止的话，则从Open表中选出的节点必将具有任意大的f值证明：设d*(n)是A*算法生成的从初始节点S0到节点n的最短路径长度，由于搜索图中每条边的代价都是一个正数，令这些正数中最小的一个数是e,则有,第2章 搜索技术,77,引理1的证明(2),因为是最佳路径的代价，故有又因为h(n)0，故有如果A*算法不终止的话，从Open表中选出的节点必将具有任意大的d*(n)值，因此，也将具有任意大的f值,第2章 搜索技术,78,引理2的证明(1),引理2在A*算法终止前的任何时刻，Open表中总存在节点n，它是从初始节点S

40、0到目标节点的最佳路径上的一个节点，且满足证明：设从初始节点S0到目标节点t的最佳路径序列为 S0=n0，n1，nk=Sg算法开始时，节点S0在Open表中，当节点S0离开Open进入Closed表时，节点n1进入Open表,第2章 搜索技术,79,引理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*值都应相等

41、，因此有f(n)f*(S0),第2章 搜索技术,80,定理2的证明,定理2对于无限图，如果从初始节点S0到目标节点Sg有路径存在，则A*算法必然会结束证明：(反证法)假设A*算法不结束，由引理1知Open表中的节点有任意大的f值，这与引理2的结论相矛盾，因此，A*算法只能成功结束推论1Open表中任一具有f(n)f(S0)的节点n，最终都被A*算法选作为扩展节点,第2章 搜索技术,81,定理3的证明(1),定理3A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A*算法必能结束在最佳路径上证明：证明过程分以下两步进行先证明A*算法一定能够终止在某个目标节点上由定理1和定理2可知

42、，无论是对有限图还是无限图，A*算法都能够找到某个目标节点而结束,第2章 搜索技术,82,定理3的证明(2),再证明A*算法只能终止在最佳路径上(反证法)假设A*算法未能终止在最佳路径上，而是终止在某个目标节点Sg处，则有f(Sg)=g(Sg)f*(S0)由引理2可知，在A*算法结束前，必有最佳路径上的一个节点n在Open表中且有f(n)f*(S0)f(Sg)这时，A*算法一定会选择n来扩展，而不可能选择Sg，从而也不会去测试目标节点Sg，这就与假设A*算法终止在目标节点相矛盾/因此，A*算法只能终止在最佳路径上,第2章 搜索技术,83,推论2,推论2在A*算法中，对任何被扩展的任一节点n，都有f(n)f*(S0)证明：令n是由A*选作扩展的任一节点，因此n不会是目标节点，且搜索没有结束/由引理2可知，在Open表中有满足f(n)f*(S0)的节点n若n=n,则有f(n)f*(S0)否则，算法既然选择n扩展，那就必有f(n)f(n)所以有f(n)f*(S0),第2章 搜索技术,