人工智能chpt讲义

人工智能chpt2.4局部搜索算法2.4.1局部搜索与最优化2.4.2爬山法搜索2.4.3模拟退火搜索2.4.4局部剪枝搜索2.4.5遗传算法第2章搜索技术人工智能chpt局部搜索算法前面的搜索算法都是保留搜索路径的，到达目标的路径就是问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的解—然而许多问题中到达目标的路径是无关紧要的与系统地搜索状态空间(保留各种路径)相对，不关心路径的搜索算法就是局部搜索算法局部搜索从一个单独的当前状态出发，通常只移动到相邻状态典型情况下搜索的路径不保留第2章搜索技术人工智能chpt局部搜索算法的应用应用领域集成电路设计工厂场地布局车间作业调度(JobShopSchedule)自动程序设计电信网络优化车辆寻径文件夹管理局部搜索也称为优化算法—wiki中表示为localsearch(optimization)第2章搜索技术人工智能chpt2.4.1局部搜索与最优化问题局部搜索算法的优点：只使用很少的内存(通常是一个常数)经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解最优化问题—根据一个目标函数找到最佳状态/只有目标函数，而不考虑(没有)“目标测试”和“路径耗散”局部搜索算法适用于最优化问题第2章搜索技术人工智能chpt状态空间地形图(1)第2章搜索技术山肩目标函数全局最大值局部最大值“平坦”局部最大值状态空间当前状态人工智能chpt状态空间地形图(2)在状态图中，既有“位置”(用状态表示)又有“高度”(用耗散值或目标函数值表示)如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰如果存在解，则完备的局部搜索算法能够找到解而最优的局部搜索算法能够找到全局最大或最小值第2章搜索技术人工智能chpt局部搜索算法本节简要介绍以下4种局部搜索算法/介绍其算法思想爬山法搜索模拟退火搜索局部剪枝搜索遗传算法从搜索的角度看遗传算法也是搜索假设空间的一种方法(学习问题归结为搜索问题)—生成后继假设的方式第2章搜索技术人工智能chpt2.4.2爬山法搜索爬山法(hill-climbing)—就是向值增加的方向持续移动—登高过程/如果相邻状态中没有比它更高的值，则算法结束于顶峰爬山法搜索算法思想：(1)令初始状态S0为当前状态(2)若当前状态已经达标，则算法运行结束，搜索成功(3)若存在一个动作可以作用于当前状态以产生一个新状态，使新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转(2)(4)取当前状态为相对最优解，停止执行算法第2章搜索技术人工智能chpt爬山法搜索的局限爬山法是一种局部贪婪搜索，不是最优解算法(或是不完备的)/其问题是：局部极大值—比其邻居状态都高的顶峰，但是小于全局最大值(参照状态空间地形图)山脊—一系列的局部极大值高原—评价函数平坦的一块区域(或者山肩)第2章搜索技术人工智能chpt爬山法搜索的变形爬山法的变形随机爬山法—随机选择下一步首选爬山法—随机选择直到有优于当前节点的下一步随机重新开始爬山法—随机生成初始状态，进行一系列爬山法搜索—这时算法是完备的概率接近1第2章搜索技术人工智能chpt2.4.3模拟退火搜索将爬山法(停留在局部山峰)和随机行走以某种方式结合，以同时获得完备性和效率模拟退火的思想想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中—如果只让其在表面滚动，则它只会停留在局部极小点/如果晃动平面，可以使乒乓球弹出局部极小点/技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出第2章搜索技术人工智能chpt模拟退火的解决思路(1)思路—开始使劲晃动(先高温加热)然后慢慢降低摇晃的强度(逐渐降温)[退火过程]算法的核心—移动选择选择随机移动，如果评价值改善，则移动被接受，否则以某个小于1的概率接受概率按照移动评价值变坏的梯度ΔE而呈指数级下降/同时也会随着作为控制的参数—“温度”T的降低(数值减小)而降低接受概率=eΔE/T(注意此时ΔE<0)第5章搜索技术人工智能chpt模拟退火的解决思路(2)温度T是时间的函数，按照模拟退火的思想，数值应该逐渐减小(降温)因为接受概率=eΔE/T且ΔE<0，所以当温度高时，接受概率较大(接近1)/而T越来越低时，ΔE/T变大，因而接受概率降低可以证明，如果T下降得足够慢，则算法找到全局最优解的概率接近1第5章搜索技术人工智能chpt2.4.4局部剪枝搜索基本思想—与只从一个单独的起始状态出发不同，局部剪枝搜索从k个随机生成的状态开始，每步生成全部k个状态的所有后继状态/如果其中之一是目标状态，算法停止；否则从全部后继状态中选择最佳的k个状态继续搜索在局部剪枝搜索过程中，有用的信息在k个并行的搜索线程之间传递—算法会很快放弃没有成果的搜索而把资源放在取得最大进展的搜索上第2章搜索技术人工智能chpt随机剪枝搜索如果k个状态缺乏多样性，则局部剪枝搜索会受其影响，性能变差算法的变种—随机剪枝搜索帮助缓解这一问题—随机剪枝搜索不是选择最好的k个后代，而是按照一定概率随机地选择k个后继状态/选择给定后继状态的概率是状态值的递增函数类似于自然选择过程—状态对应生物体，其值对应于适应性，后代就是后继状态第2章搜索技术人工智能chpt2.4.5遗传算法遗传算法(genericalgorithm/GA)是随机剪枝的变种—不是通过修改单一状态而是通过把两个父状态结合以生成后继状态与剪枝搜索一样，遗传算法也是从k个随机状态开始—这k个状态称为种群，每个状态称为个体个体用有限长的字符串(通常为0/1串)表示每个状态用其评价函数(适应度函数)给出评价值(适应值)随后的操作包括—选择/杂交/变异第2章搜索技术人工智能chpt遗传算法的操作选择(或者称繁殖)—按照一定概率随机地选择两对个体进行繁殖(即生成后继状态)杂交(或者称交叉)—杂交点是在表示状态的字符串中随机选择的一个位置，以此形成新状态—后代是父串在杂交点上进行杂交(各取一部分)得来的变异—在新生成的串中各个位置都会按照一个独立的小概率随机变异第2章搜索技术人工智能chpt遗传算法简要描述(1)定义问题和目标函数(2)选择候选解作为初始种群，每个解作为个体用二进制串表示(个体相当于染色体，其中的元素相当于基因)(3)根据目标函数，对于每个个体计算适应函数值(4)为每个个体指定一个与其适应值成正比的被选择概率(繁殖概率)(5)根据概率选择个体，所选个体通过交叉/变异等操作产生新一代种群(6)如果找到了解或者某种限制已到，则过程结束；否则转(3)第2章搜索技术人工智能chpt遗传算法的特点遗传算法也结合了“上山”趋势和随机搜索，并在并行搜索线程之间交换信息遗传算法的主要优势来自于杂交数学上可以证明，如果基因编码的位置在初始时就随机转换的话，杂交就没有优势杂交的优势在于它能够将独立发展的若干个相对固定的字符(能够执行有用的功能—“砖块”)组合起来，提高了搜索的粒度所谓有用的砖块，就是几个结合起来可以构造问题的解—参见书中的八皇后问题举例第2章搜索技术人工智能chpt遗传算法的模式遗传算法上述特点可以用模式(schema)来解释—模式是某些位置上的数字尚未确定的一个状态子串能够匹配模式的字符串称为该模式的实例如果一个模式的实例的平均适应值超过均值，则种群内这个模式的实例数量会随时间而增长遗传算法在模式和解的有意义成分相对应时才会工作得最好遗传算法有很多应用，但是在什么情况下它会达到好效果，还有很多研究要做第2章搜索技术人工智能chpt2.5约束满足问题2.5.1约束满足问题的定义2.5.2CSP的回溯搜索2.5.3赋值次序2.5.4约束传播2.5.5智能回溯第2章搜索技术人工智能chpt2.5.1约束满足问题的定义约束满足问题(ConstraintSatisfyingProblem,CSP)由一个变量集合{X1~Xn}和一个约束集合{C1~Cm}定义每个变量都有一个非空可能值域Di每个约束指定了包含若干变量的一个子集内各变量的赋值范围CSP的一个状态—对一些或全部变量的赋值{Xi=vi,Xj=vj,…}第2章搜索技术人工智能chptCSP问题的解一个不违反任何约束的对变量的赋值称为相容赋值或合法赋值对每个变量都进行赋值称为完全赋值一个(一组)既是相容赋值又是完全赋值的对变量的赋值就是CSP问题的解CSP问题常常可以可视化，表示为约束图，更直观地显示问题，帮助思考问题的 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 第2章搜索技术人工智能chpt从搜索角度看待CSP问题CSP看作搜索问题的形式化初始状态—空赋值集合，所有变量都是未赋值的后继函数—给未赋值的变量一个赋值，要求该赋值与先前的变量赋值不冲突目标测试—测试当前的赋值(组)是否是完全赋值路径耗散—每步耗散均为常数(1)每个解必须为完全赋值/如果有n个变量，则解出现的深度为n(有限)/常使用深度优先搜索第2章搜索技术人工智能chpt例1：澳大利亚地图染色问题(1)澳大利亚地图：用红绿蓝3色标出各省，相邻者颜色不同第2章搜索技术西澳大利亚北领地南澳大利亚昆士兰新南威尔士维多利亚塔斯马尼亚人工智能chpt对应于澳大利亚地图的约束图,相互关联的节点用边连接第5章搜索技术例1：澳大利亚地图染色问题(2)WANTSANSWQVT西澳大利亚–WA北领地–NT南澳大利亚–SA昆士兰–Q新南威尔士–NSW维多利亚–V塔斯马尼亚–T一组满足约束的完全赋值{WA=R,NT=G,Q=R,SA=B,NSW=G,V=R,T=R}人工智能chpt例2：密码算术问题(1)字母算式谜（cryptarithmeticpuzzle）2008北京奥运会的主题是“同一个世界，同一个梦想”，对应的英文是“ONEWORLD,ONEDREAM”可以将这些英文字母组成一个字母算式如下：第2章搜索技术人工智能chpt第2章搜索技术例2：密码算术问题(2)WROANMDELX4X3X2X1通过约束图来更直观地观察和求解在约束图中，圆圈表示变量，X1~X4表示进位；方块表示约束关系这些约束关系中，上面的一个方块连接所有的变量，表示这9个字母必须是不同的数字；其余的方块表示同一位列数字和进位之间的关系人工智能chpt例2：密码算术问题(3)直观地求解这个问题，如千位数上的2个数有关系：R=O+进位1或者进位2，此时还必须产生一个进位等式关系最后答案：{O=9,R=0,E=8,N=1,D=6,M=2,W=5,A=7,L=3}第2章搜索技术人工智能chptCSP问题的分类变量—离散值域有限值域—如地图染色问题无限值域—如作业规划，要使用约束语言(线性约束/非线性约束)变量—连续值域如哈勃望远镜实验日程安排/线性规划问题约束的类型一元约束—只限制一个变量的取值二元约束与2个变量相关高阶约束—涉及3个或更多变量第2章搜索技术人工智能chptCSP问题求解的复杂度搜索相容的完全赋值，最朴素的想法是依次取变量的赋值组合并检查其是否满足约束条件指数级计算量若CSP问题的任何一个变量的最大值域为d，那么可能的完全赋值数量为O(dn)有限值域CSP问题包括布尔CSP问题—其中有一些NP完全问题，如3SAT问题(命题逻辑语句的可满足性)/最坏情况下不会指望低于指数级时间复杂性解决该问题第2章搜索技术人工智能chpt2.5.2CSP的回溯搜索CSP问题具有一个性质：可交换性—变量赋值的顺序对结果没有影响/所有CSP搜索算法生成后继节点时，在搜索树每个节点上只考虑单个变量的可能赋值CSP问题的求解使用深度优先的回溯搜索—最基本的算法算法思想：每次给一个变量赋值，当没有合法赋值(不满足约束时)就要推翻前一个变量的赋值，重新给其赋值，这就是回溯第2章搜索技术人工智能chpt简单回溯法生成的搜索树澳大利亚地图染色问题的搜索树第2章搜索技术WA=redWA=redNT=greenWA=RedNT=blueWA=redNT=greenQ=redWA=redNT=greenQ=blueWA=greenWA=blue人工智能chpt回溯搜索的改进(1)可以改善上述无信息搜索算法的性能，这些改进是一些通用性的考虑：变量赋值的次序对性能的影响—在若干变量已经赋值的条件下，如果下一步赋值有多个选择，该选择哪一个？—使用关于变量赋值次序的启发式当前变量的赋值会对其他未赋值变量产生什么约束？怎样利用这种约束以提高效率？—使用关于变量赋值之间的启发式第2章搜索技术人工智能chpt回溯搜索的改进(2)当遇到某个失败的变量赋值时，怎样避免同样的失败？就是说找到对这种失败起到关键作用的某个变量赋值—使用关于失败变量的启发式：进行回溯，直接找到影响失败的变量重新赋值考虑问题的结构，也可提高求解效率(参见5.4节)把问题分解为独立的子问题将约束图变换为树结构—任何一个树状结构的CSP问题可以在变量个数的线性时间内求解(树变换方法—删除或者合并节点)第2章搜索技术人工智能chpt2.5.3赋值次序随机的变量赋值排序难以产生高效率的搜索如：在WA=red/NT=green条件下选取SA赋值比Q要减少赋值次数(1:2)/并且一旦给定SA赋值以后，Q/NSW/V的赋值只有一个选择因此，选择合法取值最少的变量—或者称为最少剩余值(MRV)启发式，或者称为最受约束变量/失败优先启发式称为失败优先启发式是因为它可以很快找到失败的变量，从而引起搜索的剪枝，避免更多导致同样失败的搜索第2章搜索技术人工智能chptMRV启发式当有多个变量需要选择时—优先选择在当前约束下取值最少的变量当赋值的变量有多个值选择时—优先选择为剩余变量的赋值留下最多选择的赋值如，WA=red/NT=green时，如果给Q赋值，则Q=blue的选择不好，此时SA没有一个可选择的了如果要找出问题的所有解，则排序问题无所谓第2章搜索技术人工智能chpt度启发式对于初始节点，选择什么变量更合适？度启发式—选择涉及对其他未赋值变量的约束数量大(与其他变量关联最多)的变量地图染色例子中，度(SA)=5/其他均为2/3实际上，一旦选择了SA作为初始节点，应用度启发式求解本问题，则可以不经任何回溯就找到解SA=redNT=greenQ=blueNSW=greenWA=blueV=blue第2章搜索技术人工智能chpt2.5.4约束传播检查当前的变量赋值组合是否会对尚未赋值的变量产生新约束—要尽早地检查一些约束，使得一旦发现某些赋值不满足这样的约束，就及早地删除这些对变量的赋值，从而减少搜索空间假设CSP中所有的约束都是二元约束（多元约束均可以转化为二元约束），则CSP可以表示为一个只含有二元约束的图，这些二元约束就是图中两个节点之间的弧因此，不断删除那些不被满足的约束就是不断删除图中的不相容弧—称为弧相容（arcconsistency）技术第2章搜索技术人工智能chpt相容的概念（1）K-相容（K-consistency）：一个CSP问题，对于其中任意K-1个变量的每一组取值，如果它们满足这些变量之间的所有约束，则对任意第K个变量，存在一个值，使得K个变量之间的所有约束均被满足—此时该CSP称为K-相容的弧相容（arcconsistency，简写为AC）或2-相容：如果对于变量X的任意赋值v(x)，和该变量有约束关系的某个变量Y总有一个赋值v(y)与其相容，则称Y是与X弧相容的（或者2-相容）第2章搜索技术人工智能chpt相容的概念（2）弧相容是有方向的，Y与X弧相容，并不等于X与Y弧相容，即反过来不一定成立/也就是说，对于变量Y的任意赋值，变量X不一定总有一个赋值与其相容对于一个具有N个节点的CSP约束图来说，获得N-相容的算法的复杂性是指数级的一个CSP约束图是强K-相容的，如果对于所有都是J-相容的第2章搜索技术人工智能chpt约束传播与前向检验将相容的思想应用于CSP回溯搜索，就产生了约束传播（constraintpropagation）的方法其中最简单的方法是把弧相容的概念应用于搜索基本算法，构成前向检验（forwardchecking）方法第2章搜索技术人工智能chpt前向检验前向检验原理：每次给一个变量赋值（不妨称为当前变量和当前赋值）时，所有与该变量连接（或者称为相邻，即有约束关系）的其他变量都进行约束检查，那些与当前约束冲突的变量取值均被暂时删除/如果此时某个其他变量的值域为空，则当前赋值必须改变，要选择其他赋值。如果当前变量没有赋值可选，则 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 上一层的赋值是不满足约束的，必须回溯，那些被临时删除的变量赋值全部恢复以这样的方式，前向检验可以预测哪些赋值会导致失败，从而将其剪枝这种预测来得越早，则可以减少越多的搜索空间/前向检验通常和MRV启发式一起使用第2章搜索技术人工智能chpt约束传播如果前向检验不止向前看一个相邻变量，而且看相邻变量的相邻变量，直至遍历全部变量以检查它们之间的弧相容关系—部分向前看/完全向前看约束传播—将一个变量的约束内容传播到其他变量不断检验变量之间的约束并将其作用于更大范围，故称为约束传播第2章搜索技术人工智能chpt前向检验例子第2章搜索技术4皇后问题人工智能chpt2.5.5智能回溯在回溯算法中，当发现不满足约束即搜索失败时，则回到上一个变量并尝试下一个取值—称为历时回溯/在很多情况下这样做是效率很低的—因为问题并不决定于上一个(甚至几个)变量的取值所以，回溯应该倒退到导致失败的变量集合中的一个变量（冲突集）—称为后向跳转方法冲突集引导的后向跳转（回跳）—智能回溯第2章搜索技术人工智能chpt冲突集变量X的冲突集：当变量X的赋值集合为空时，那些通过约束与X相连的先前已赋值的变量就构成了X的冲突集基于冲突集的回跳方法：设变量是当前失败变量，是其父节点，是的冲突集从开始回跳，回跳至中离最近的节点（除去）；设置的冲突集为：在新冲突集中选择一个变量作为回跳点变量，进行重新赋值第2章搜索技术人工智能chpt冲突集指导的后向跳转—例子对于澳大利亚地图染色问题中的各变量，假设赋值次序是：{WA=red,NSW=red}→{NT}→{Q}→{SA}则因为WA和NSW不能为相同颜色，而导致SA失败/SA是失败变量，离SA最近的冲突集中的变量是Q，于是从Q回溯，得到各变量的冲突集如下：第2章搜索技术人工智能chpt冲突集指导的后向跳转—例子由此可跳至回跳点——变量NSW，重新赋值后可不产生冲突第2章搜索技术人工智能chpt2.6博弈搜索2.6.1极大极小决策2.6.2-剪枝第2章搜索技术人工智能chpt博弈搜索问题与方法从智能体角度看，博弈是多智能体之间的竞争和对抗/在竞争的环境中，每个智能体的目的是冲突的，由此引出对抗搜索问题—称为博弈本节探讨两个问题—如何搜索到取胜的路径/如何提高搜索效率相应的方法—最优策略(极大极小决策)/-剪枝第2章搜索技术人工智能chpt博弈游戏的描述两个游戏者的博弈可以定义为一类搜索问题，其中包括：初始状态—棋盘局面和哪个游戏者出招后继函数—返回(招数,状态)对的一个列表，其中每对表示一个合法招数和相应的结果状态终止测试—判断游戏是否结束效用函数—或称目标函数，对终止状态给出一个数值如输赢和平局(以-1/+1/0表示)双方的初始状态和合法招数定义了游戏的博弈树—此为博弈搜索第2章搜索技术人工智能chpt井字棋的博弈树第2章搜索技术………………XXXXXXXXXXOOXXOXOXXOXXOXXOXXOOXOOXXXXOOXXOXOOX…MAX(X)MIN(O)MAX(X)MIN(O)TERMINAL效用-10+1人工智能chpt2.6.1极大极小决策博弈搜索中，最优解是导致取胜的终止状态的一系列招数在井字棋搜索树中，因为MAX先行，所以MAX的任务是利用搜索树确定最佳招数/但是另一方MIN也有发言权因此MAX制定取胜策略时必须不断地考虑MIN应对条件下如何取胜—即MAX初始状态下应该采取什么招数，然后是MIN应对造成的状态下MAX采取的招数，接着继续考虑下一步应对后的招数...第2章搜索技术人工智能chpt极大极小值(1)假设一个两层的博弈树(因为即使是井字棋的博弈树也太复杂了)，其中有MAX节点和MIN节点博弈树中，每个单方的招数(或称走步)是一层/双方各走一招称为一步(博弈树的深度是一步的)给定一棵博弈树，最优策略可以通过检查每个节点的极大极小值来决定—记为MAX-MIN(n)，所以也称为极大极小决策第2章搜索技术人工智能chpt极大极小值(2)如果博弈双方都按照最优策略进行，那么一个节点的极大极小值就是对应状态的效用值(对应MAX)对于某个节点，极大极小函数如下定义MAX优先选择有极大值的状态/MIN则选择有极小值的状态第5章搜索技术人工智能chpt极大极小值(3)第2章搜索技术31282461452ABDC3223MAXMINMAX人工智能chpt极大极小值(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章搜索技术人工智能chpt极大极小值算法说明简单的递归算法—按照定义计算每个后继节点的极大极小值/搜索是从目标到初始节点的反向推导算法对博弈树实行了深度优先搜索如果博弈树的最大深度为m，每个节点的合法招数为b，则算法的时间复杂度是O(bm)每次生成全部后继节点的空间复杂度是O(bm)每次只生成一个后继节点的空间复杂度是O(m)第2章搜索技术人工智能chpt极大极小值算法FunctionMAX-MIN-DECISION(state)returnsanactioninputs:state(currentstateingame)v←MAX-VALUE(state)returntheactioninSUCCESSORS(state)withvaluevFunctionMAX-VALUE(state)returnsautilityvalueifTERMINAL-TEST(state)thenreturnUTILITY(state)v←-∞fora,sinSUCCESSORS(state)dov←MAX(v,MIN-VALUE(s))returnv(a=action招数)FunctionMIN-VALUE(state)returnsautilityvalueifTERMINAL-TEST(state)thenreturnUTILITY(state)v←+∞fora,sinSUCCESSORS(state)dov←MIN(v,MAX-VALUE(s))returnv第2章搜索技术人工智能chpt2.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章搜索技术人工智能chpt博弈树的剪枝(1)第2章搜索技术3[-∞,+∞]AB[-∞,3](a)[-∞,+∞]12AB3[-∞,3](b)人工智能chpt博弈树的剪枝(2)第2章搜索技术12AB[3,+∞]38[3,3](c)12ABC[3,+∞][-∞,2]382[3,3](d)人工智能chpt博弈树的剪枝(3)第2章搜索技术[-∞,14]12ABDC[3,14][-∞,2]38214[3,3](e)12ABDC[3,3][-∞,2][2,2]3821452[3,3](f)人工智能chpt-剪枝算法(1)在极大极小值算法基础上增加了剪枝功能，即在返回值基础上增加了判断FunctionALPHA-BETA-SEARCH(state)returnsanactioninputs:state(currentstateingame)v←MAX-VALUE(state,-∞,+∞)returntheactioninSUCCESSORS(state)withvaluev第2章搜索技术人工智能chpt-剪枝算法(2)FunctionMAX-VALUE(state,,)returnsautilityvalueinputs:state,thevalueofthebestalternativeforMAXalongthepathtostate,thevalueofthebestalternativeforMINalongthepathtostateifTERMINAL-TEST(state)thenreturnUTILITY(state)v←-∞fora,sinSUCCESSORS(state)dov←MAX(v,MIN-VALUE(s,,))ifv≥thenreturnv←MAX(,v)returnv第2章搜索技术人工智能chpt-剪枝算法(3)FunctionMIN-VALUE(state,,)returnsautilityvalueinputs:state,thevalueofthebestalternativeforMAXalongthepathtostatethevalueofthebestalternativeforMINalongthepathtostateifTERMINAL-TEST(state)thenreturnUTILITY(state)v←+∞fora,sinSUCCESSORS(state)dov←MIN(v,MAX-VALUE(s,,))ifv≤thenreturnv←MIN(,v)returnv第2章搜索技术人工智能chpt-剪枝算法的说明-剪枝可以应用树的任何深度，许多情况下可以剪掉整个子树/其原则是—如果在节点n的父节点或者更上层的节点有一个更好的选择m，则在实际游戏(搜索)中永远不会到达n=到目前为止在路径上任意点发现的MAX最佳选择=到目前为止在路径上任意点发现的MIN最佳选择-搜索不断更新/值，当某个节点的值分别比/值更差时剪掉该节点的剩余分支第2章搜索技术人工智能chpt-剪枝的效率-剪枝的效率很大程度上取决于检查后继节点的次序—应该先检查那些可能最好的后继如果能够先检查那些最好的后继，则-剪枝算法只需检查O(bd/2)个节点以决定最佳招数/极大极小值算法为O(bd)—有效分支因子b到b的平方根—效率大大提高第2章搜索技术人工智能chpt本章复习提示用各种搜索算法解决问题(编程练习)具体搜索问题的形式化表示(初始状态/后继函数/搜索代价等)了解各种搜索算法(包括局部搜索和博弈搜索)的思想、相关性质和性能约束满足问题的相关概念尝试使用搜索方式求解实际问题/考虑具体任务的相关知识第2章搜索技术人工智能chpt参考书目StuartRussell/PeterNorvig:AIMA第3章/第4章/第5章/第6章陆汝钤编著:人工智能(上册)第5章/第6章/第8章/第9章田盛丰、黄厚宽，人工智能与知识工程，中国铁道出版社，1999年8月第1版，第4章/第9章VipinKumar,AlgorithmsforConstraintSatisfactionProblems,AIMagazine,V13,N1(1992),pp32~44第2章搜索技术人工智能chpt附录A*算法可采纳性的证明第2章搜索技术人工智能chptA*算法可采纳性定理：A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A*算法必能结束在最佳路径上证明的过程：首先证明A*算法必定成功结束其次证明A*算法结束时中止于最佳路径第2章搜索技术人工智能chpt证明的步骤证明分为三步：(1)对于有限图，A*算法一定成功结束(2)对于无限图，A*算法一定成功结束(3)A*算法必定终止于最佳路径上对于无限图情况的证明，引入2个引理(1)如果A*算法不终止，则存在f值任意大的节点(2)A*算法结束前，仍有耗散值更小的节点待扩展第2章搜索技术人工智能chpt定理1的证明(1)定理1—对于有限图，如果从初始节点S0到目标节点Sg有路径存在，则A*算法一定成功结束证明：首先证明算法必定会结束由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因此，A*算法必然会结束第2章搜索技术人工智能chpt定理1的证明(2)然后证明算法一定会成功结束由于至少存在一条由初始节点到目标节点的路径，设此路径为S0=n0，n1，…，nk=Sg算法开始时，节点n0在Open表中，而且路径中任一节点ni离开Open表后，其后继节点ni+1必然进入Open表，这样，在Open表变为空之前，目标节点必然出现在Open表中/因此，算法必定会成功结束★第2章搜索技术人工智能chpt引理1的证明(1)引理1—对无限图，如果从初始节点S0到目标节点Sg有路径存在，且A*算法不终止的话，则从Open表中选出的节点必将具有任意大的f值证明：设d*(n)是A*算法生成的从初始节点S0到节点n的最短路径长度，由于搜索图中每条边的代价都是一个正数，令这些正数中最小的一个数是e,则有第2章搜索技术人工智能chpt引理1的证明(2)因为是最佳路径的代价，故有又因为h(n)≥0，故有如果A*算法不终止的话，从Open表中选出的节点必将具有任意大的d*(n)值，因此，也将具有任意大的f值★第2章搜索技术人工智能chpt引理2的证明(1)引理2—在A*算法终止前的任何时刻，Open表中总存在节点n’，它是从初始节点S0到目标节点的最佳路径上的一个节点，且满足证明：设从初始节点S0到目标节点t的最佳路径序列为S0=n0，n1，…，nk=Sg算法开始时，节点S0在Open表中，当节点S0离开Open进入Closed表时，节点n1进入Open表第2章搜索技术人工智能chpt引理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*(S0)★第2章搜索技术人工智能chpt定理2的证明定理2—对于无限图，如果从初始节点S0到目标节点Sg有路径存在，则A*算法必然会结束证明：(反证法)假设A*算法不结束，由引理1知Open表中的节点有任意大的f值，这与引理2的结论相矛盾，因此，A*算法只能成功结束★推论1—Open表中任一具有f(n)≤f(S0)的节点n，最终都被A*算法选作为扩展节点第2章搜索技术人工智能chpt定理3的证明(1)定理3—A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A*算法必能结束在最佳路径上证明：证明过程分以下两步进行先证明A*算法一定能够终止在某个目标节点上—由定理1和定理2可知，无论是对有限图还是无限图，A*算法都能够找到某个目标节点而结束第2章搜索技术人工智能chpt定理3的证明(2)再证明A*算法只能终止在最佳路径上(反证法)假设A*算法未能终止在最佳路径上，而是终止在某个目标节点Sg处，则有f(Sg)=g(Sg)>f*(S0)由引理2可知，在A*算法结束前，必有最佳路径上的一个节点n’在Open表中且有f(n’)≤f*(S0)