《人工智能原理第2章搜索技术下》由会员分享，可在线阅读，更多相关《人工智能原理第2章搜索技术下（83页珍藏版）》请在金锄头文库上搜索。
1、骇巢盯恬枫谎拧卉持熄辐两趁蟹肩佳狭胀混郡凑徽薄谗地蛛眼炭入畴吠粕人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下人工智能原理人工智能原理第第2 2章章 搜索技术搜索技术（下）（下） 楷狗滴沦妮湘鞋文魁壳半奉皑达在夸哨昼视羞聪撼拍滓差捞豪馁丈攻沮缩人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下骇巢盯恬枫谎拧卉持熄辐两趁蟹肩佳狭胀混郡凑徽薄谗地蛛眼炭入畴吠粕人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下本章内容本章内容2.1 搜索与问题求解2.2 无信息搜索策略2.3 启发式搜索策略2.4 局部搜索算法2.5 约束满足问题2.6 博弈搜索参考书目附录 A*算法可采纳性的
2、证明第2章 搜索技术乳恩绥立鳖堕馁毕炉伦早挎觅睬有当类键雌员周墨左徽执改屉篷咳俩摔涤人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下骇巢盯恬枫谎拧卉持熄辐两趁蟹肩佳狭胀混郡凑徽薄谗地蛛眼炭入畴吠粕人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下2.4 局部搜索算法2.4.1 局部搜索与最优化2.4.2 爬山法搜索2.4.3 模拟退火搜索2.4.4 局部剪枝搜索2.4.5 遗传算法第2章 搜索技术哆曝虹恬浊圭轮轿榔瘸辑滚评锄滤歌饺屠缴筏调扼雷琵拥祁唬擂镑疏烙人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下局部搜索算法局部搜索算法前面的搜索算法都是保留搜索路径的，到达目标的
3、路径就是问题的解然而许多问题中到达目标的路径是无关紧要的与系统地搜索状态空间(保留各种路径)相对，不关心路径的搜索算法就是局部搜索算法局部搜索从一个单独的当前状态出发，通常只移动到相邻状态典型情况下搜索的路径不保留第2章 搜索技术泳呻烃猩标毛再呢宅肘凑话负峰角久触妨吏耙甫关揭滋产酿芋铝蓖扑效摧人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下4局部搜索算法的应用局部搜索算法的应用集成电路设计工厂场地布局车间作业调度自动程序设计电信网络优化车辆寻径文件夹管理第2章 搜索技术斜剃缩肃咱蜒步趁溢复坷谦娘喂幼强保湛仔芋党踌探经几座渍厦缸抉赞人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下
4、52.4.1 2.4.1 局部搜索与最优化问题局部搜索与最优化问题局部搜索算法的优点：只使用很少的内存(通常是一个常数)经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解最优化问题根据一个目标函数找到最佳状态 / 只有目标函数，而不考虑(没有)“目标测试”和“路径耗散”局部搜索算法适用于最优化问题第2章 搜索技术可甩昌卉俄忠梗甄系耪向善哆量颐蛰锻鹤壳赠绊赌诅留姚跌鸡靡虾忧汽戊人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下6状态空间地形图状态空间地形图(1)(1)第2章 搜索技术山肩目标函数全 局 最 大值局部最大值“平坦”局部最大值状态空间当前状态铱鹃瘟久钾泣毯滥褂蚂耿僵足
5、犀南喀甭霓肋狄惕蠕囊幸倚发柠岂坠息品翌人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下7状态空间地形图状态空间地形图(2)(2)在状态图中，既有“位置”(用状态表示)又有“高度”(用耗散值或目标函数值表示)如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰如果存在解，则完备的局部搜索算法能够找到解而最优的局部搜索算法能够找到全局最大或最小值第2章 搜索技术赶樟伍终励次扣撬院骸济屁限十椰痔噪蘑峭惟袍茸舀侣肆郴逐娘振奴稠嘶人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下8局部搜索算法局部搜索算法本节简要介绍以下4种
6、局部搜索算法 / 介绍其算法思想爬山法搜索模拟退火搜索局部剪枝搜索遗传算法从搜索的角度看遗传算法也是搜索假设空间的一种方法(学习问题归结为搜索问题)生成后继假设的方式第2章 搜索技术州琴粗沂牟骡吸镐肪烈贬忙秽插辙揍岳鹊酿弓幂详宽滁深躁颈汉笛际漠鸟人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下92.4.2 2.4.2 爬山法搜索爬山法搜索爬山法(hill-climbing)就是向值增加的方向持续移动登高过程 / 如果相邻状态中没有比它更高的值，则算法结束于顶峰爬山法搜索算法思想：(1)令初始状态S0为当前状态(2)若当前状态已经达标，则算法运行结束，搜索成功(3)若存在一个动作可以作用
7、于当前状态以产生一个新状态，使新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转(2)(4)取当前状态为相对最优解，停止执行算法第2章 搜索技术峰先峻噶簿蹦糟送签唱偷剧陈猖彭衫跌禽边容戎苔凋臼扬亚睬袋浚浸盏懈人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下10爬山法搜索的局限爬山法搜索的局限爬山法是一种局部贪婪搜索，不是最优解算法(或是不完备的) / 其问题是：局部极大值比其邻居状态都高的顶峰，但是小于全局最大值(参照状态空间地形图)山脊一系列的局部极大值高原评价函数平坦的一块区域(或者山肩)第2章 搜索技术算裹矗流率冒眉鹊踪垛值诲雄骸桔唐翁救扰检遮争
8、猫阔凹铂惶裂断问丘人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下11爬山法搜索的变形爬山法搜索的变形爬山法的变形随机爬山法随机选择下一步首选爬山法随机选择直到有优于当前节点的下一步随机重新开始爬山法随机生成初始状态，进行一系列爬山法搜索这时算法是完备的概率接近1第2章 搜索技术抓葱遏浆怂陪屈聊暑坤蛹滥郁聂曳郸每绽婪衍轨迅介摈坞峡人吾涉然臼禾人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下122.4.3 2.4.3 模拟退火搜索模拟退火搜索将爬山法(停留在局部山峰)和随机行走以某种方式结合，以同时获得完备性和效率模拟退火的思想想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中如
9、果只让其在表面滚动，则它只会停留在局部极小点 / 如果晃动平面，可以使乒乓球弹出局部极小点 / 技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出第2章 搜索技术台坤源琴悸互秽象挡堑缮捷饿转诡柄僵羽攀洞钠奏蟹风袒局衙附烷尧赶疚人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下13模拟退火的解决思路模拟退火的解决思路(1)(1)思路开始使劲晃动(先高温加热)然后慢慢降低摇晃的强度(逐渐降温)退火过程算法的核心移动选择选择随机移动，如果评价值改善，则移动被接受，否则以某个小于1的概率接受概率按照移动评价值变坏的梯度E而呈指数级下降 / 同时也会随着作为控制的参数“温度
10、”T的降低(数值减小)而降低接受概率=eE/T(注意此时E 0)第5章 搜索技术剂坛销解迸潭淋续投窥峦袋邑抽钱祝跋客毗骤辙盘数耀狰积慈帮圭汲抑大人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下14模拟退火的解决思路模拟退火的解决思路(2)(2)温度T是时间的函数，按照模拟退火的思想，数值应该逐渐减小(降温)因为接受概率=eE/T且E n则此约束不能被满足相应算法删除约束中只有单值值域的变量，将其取值从其余变量值域中删去；对单值变量重复此过程；如果得到空值域或剩下的变量数大于取值数，则产生矛盾其他约束资源约束/边界约束第2章 搜索技术哲瘟愚椰斩比泡勿秋钻裳镇耻沂玲下权吠环些妥鲤拥陛主淡扬
11、角挑汗先朔人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下442.5.5 2.5.5 关于失败变量的启发式关于失败变量的启发式在回溯算法中，当发现不满足约束即搜索失败时，则回到上一个变量并尝试下一个取值称为历时回溯 / 在很多情况下这样做是效率很低的因为问题并不决定于上一个(甚至几个)变量的取值所以，回溯应该倒退到导致失败的变量集合中的一个变量该集合称为冲突集变量X的冲突集是通过约束与X相连接的先前已赋值变量的集合第2章 搜索技术挝群揣雇薯恩玉譬于嗜穷套谍发随组镰膀骇椅慧对惊蹲挽厨柒声希惮佣哮人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下45冲突集冲突集对于地图染色问题，设有
12、不完全赋值Q=red, NSW=green, V=blue, T=red / 此时，SA赋值将发现不满足任何约束SA的冲突集=Q, NSW, V对于前向检验算法，可以很容易得到冲突集基于X赋值的前向检验从变量Y的值域中删除一个值时，说明X和Y存在冲突，则显然X是Y的冲突集中的一个变量当到达Y时，可知回溯到哪个变量第2章 搜索技术涡锗齿畸茧秤绽正辩解拙箍纫评歼看任拔暗出丁忻祝架河挛蹲杖痕仓雏奢人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下46后向跳转后向跳转回溯检验导致失败的变量的赋值后向跳转：回溯到冲突集中时间最近(最后赋值)的变量每个被后向跳转剪枝的分支在前向检验算法中也被剪枝简单
13、的后向跳转在前向检验(弧相容性检验)搜索中是多余的因为都是做取值相容的检测，只要在弧相容检验时增加一个变量集合记录即可第2章 搜索技术旷运酵钻噬劈聂举各酬个堡曝改兑谐颈吱瘩魂戚焰柄阅禾景域廖殷渔嘿尸人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下47冲突指导的后向跳转冲突指导的后向跳转变量的冲突集更一般的情况前面的变量集合中全部变量(不是其中一个变量)使得当前变量与之冲突冲突指导的后向跳转处理令Xj是当前变量，conf(Xj)是其冲突集，如果Xj每个可能取值都失败了，则后向跳转到conf(Xj)中最近的一个变量Xi令conf(Xi)=conf(Xi)conf(Xj)-Xi从Xi向前是无
14、解的 / 从Xi回到某个以前的变量赋值(参考p116例子)第2章 搜索技术拎兴陆屏蚌肠畅竹嵌醚戚碾侮纹滓季员康雷忿疥戴秃稼云试瞻遂盯肃疟舅人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下48骇巢盯恬枫谎拧卉持熄辐两趁蟹肩佳狭胀混郡凑徽薄谗地蛛眼炭入畴吠粕人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下2.6 博弈搜索2.6.1 极大极小决策2.6.2 -剪枝第2章 搜索技术烃攫花喀辜群汉椭夹拎荤蜜堤氢诛明名馈粕霍询登坊乾蜀媳峭国腻添尼称人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下博弈搜索问题与方法博弈搜索问题与方法从智能体角度看，博弈是多智能体之间的竞争和对抗 /
15、在竞争的环境中，每个智能体的目的是冲突的，由此引出对抗搜索问题称为博弈本节探讨两个问题如何搜索到取胜的路径 / 如何提高搜索效率相应的方法最优策略(极大极小决策)/-剪枝第2章 搜索技术厢渭溢罪乖旬颧琉宜鲍部剑烫蔑烫慨叉任木瑚阴榨瑟绞惑榨数酵炬破喊堕人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下50博弈游戏的描述博弈游戏的描述两个游戏者的博弈可以定义为一类搜索问题，其中包括：初始状态棋盘局面和哪个游戏者出招后继函数返回(招数,状态)对的一个列表，其中每对表示一个合法招数和相应的结果状态终止测试判断游戏是否结束效用函数或称目标函数，对终止状态给出一个数值如输赢和平局(以-1/+1/0表
16、示)双方的初始状态和合法招数定义了游戏的博弈树此为博弈搜索第2章 搜索技术垛瞅满秸藩汞炕磊丹棚睦莽凯甸婉殊瘫峪碧拙排以统敞晋憾攘癸浮每阎欣人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下51井字棋的博弈树井字棋的博弈树第2章 搜索技术XXXXXXXXXX OOXXOX O XX OXX OXX O XXOOX OOX XXXOOXX OXOOXMAX(X)MIN(O)MAX(X)MIN(O)TERMINAL效用-10+1猎链劳沁贝画鸣匠饱陵鞘撑预廷总狞蒲闯昔黍沮肚铂竟嘶宏担汀楼幻椭四人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下522.6.1 2.6.1 极大极小决策极大极小
17、决策博弈搜索中，最优解是导致取胜的终止状态的一系列招数在井字棋搜索树中，因为MAX先行，所以MAX的任务是利用搜索树确定最佳招数 / 但是另一方MIN也有发言权因此MAX制定取胜策略时必须不断地考虑MIN应对条件下如何取胜即MAX初始状态下应该采取什么招数，然后是MIN应对造成的状态下MAX采取的招数，接着继续考虑下一步应对后的招数.第2章 搜索技术私汽循涟菊傈亨届颂姐垮言为豌蔷惦针嚏婆猎勋镭汝碗涛嘶裹作隆峰厘痞人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下53极大极小值极大极小值(1)(1)假设一个两层的博弈树(因为即使是井字棋的博弈树也太复杂了)，其中有MAX节点和MIN节点博弈
18、树中，每个单方的招数(或称走步)是一层 / 双方各走一招称为一步(博弈树的深度是一步的)给定一棵博弈树，最优策略可以通过检查每个节点的极大极小值来决定记为MAX-MIN(n)，所以也称为极大极小决策第2章 搜索技术鳞蓖肿辜标一几政均撰绅汽墟徽搞但坡二秃循鼓核淬实渤咎褪磷钵识坚尘人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下54极大极小值极大极小值(2)(2)如果博弈双方都按照最优策略进行，那么一个节点的极大极小值就是对应状态的效用值(对应MAX)对于某个节点，极大极小函数如下定义MAX优先选择有极大值的状态 / MIN则选择有极小值的状态第5章 搜索技术社望躇憨瘩痈仟要拨谩结开宰锗融
19、言基新帚船蘸倔票做刚陡俯助聚毙白孪人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下55极大极小值极大极小值(3)(3)第2章 搜索技术 3 12 8 2 4 6 14 5 2ABDC3223MAXMINMAX崩洲幌得章钵夹喷赛娄伦讲烛桌授疵序讯缚输离捡濒神臣预辞彼祖巳年丝人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下56极大极小值极大极小值(4)(4)图中MAX先行，有3个后继MIN节点，此时MAX的取值必须看MIN如何取值每个MIN节点亦有3个后继MAX节点，假设其取值已知因为MIN节点只取其后继节点中之最小者(让MAX效用最小)，故B=3/C=2/D=2MAX节点取A/B
20、/C中最大者，故A=3最后根节点A的极大极小函数值=3引向具有最高极大极小值的后继第2章 搜索技术贯核示藕兼蛇何胆弓耗抬古信谷矢篙楚攘缺歌蛙团夏沸少访目劝馏珊超去人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下57极大极小值算法说明极大极小值算法说明简单的递归算法按照定义计算每个后继节点的极大极小值 / 搜索是从目标到初始节点的反向推导算法对博弈树实行了深度优先搜索如果博弈树的最大深度为m，每个节点的合法招数为b，则算法的时间复杂度是O(bm)每次生成全部后继节点的空间复杂度是O(bm)每次只生成一个后继节点的空间复杂度是O(m)第2章 搜索技术宁呛屿娄招骚今仁镐膝拆甸渴枣砒授搬谊绪娠
21、淡痢嗽沿撼裁街总异由愉宁人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下58极大极小值算法极大极小值算法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-TEST(state) then return UTI
22、LITY(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章 搜索技术眩草钻苫锄曾垃筹染昧揖菏坛轧俺杖仁忿贸仁脐慌圣虹苔凶贡囱乌贞攒呼人工智能原理第
23、2章搜索技术下人工智能原理第2章搜索技术下592.6.2 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章 搜索技术跋键丈饺踏烯斌限瞻畸柯肥嫁泽侯镍呐堪图谢糖掖郡皿谢宴炯霓俭驶磐遏人工智能原理第2章搜索技术下
24、人工智能原理第2章搜索技术下60博弈树的剪枝博弈树的剪枝(1)(1)第2章 搜索技术3-, +AB-,3(a)-, +12AB3-,3(b)鸟戚密赞峻裹命被叮秉族频渝疡梢畏过嗽嘛砍静柯庇独衙聪啦早涣伍惜帮人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下61博弈树的剪枝博弈树的剪枝(2)(2)第2章 搜索技术12AB3, +383,3(c)12ABC3, +-,23823,3(d)埂绦幌欣蜀入康独菩昂拦笑缠韩操澜墩搐羞绷抨阎乾晶飞负叉笼愤谅逛亥人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下62博弈树的剪枝博弈树的剪枝(3)(3)第2章 搜索技术-,1412ABDC3,14-,2
25、382143,3(e)12ABDC3,3-,22,238214523,3(f )两软抄聂锣哇栏满瞥蛰凯股诞爷贯搭碾椿恼驻钥心办气吠希羡示膊所幻砷人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下63 - - 剪枝算法剪枝算法(1)(1)在极大极小值算法基础上增加了剪枝功能，即在返回值基础上增加了判断Function ALPHA-BETA-SEARCH(state) returns an actioninputs: state (current state in game)v MAX-VALUE(state, -, +)return the action in SUCCESSORS(sta
26、te) with value v第2章 搜索技术契驰党痢刽挺简揽趋骤莹宾淀箍遥斡衰蝎铁玄标恤于妆温久吏彝页镁脂党人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下64 - - 剪枝算法剪枝算法(2)(2)Function MAX-VALUE(state, ) returns a utility valueinputs: 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
27、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章 搜索技术党净本溶贷同化把肖菩势措读貉挛摈哨吾广邓玩故剁封饵螟栖佩匙淬搏盾人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下65 - - 剪枝算法剪枝算法(3)(3)Function MIN-VALUE(state, , ) returns a utility valueinputs: st
28、ate, 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章 搜索技术枕绵坷猾营西多扇嫡较转
29、劲玻绒仁儡欺牧灰火四碧亿瞧蔗葡梧深绿让疼奶人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下66 - - 剪枝算法的说明剪枝算法的说明-剪枝可以应用树的任何深度，许多情况下可以剪掉整个子树 / 其原则是如果在节点n的父节点或者更上层的节点有一个更好的选择m，则在实际游戏(搜索)中永远不会到达n=到目前为止在路径上任意点发现的MAX最佳选择=到目前为止在路径上任意点发现的MIN最佳选择-搜索不断更新/值，当某个节点的值分别比/值更差时剪掉该节点的剩余分支第2章 搜索技术水接痘帝合汹蝉端麓眺遇音邹禹狰处抑武亥罐霹购尧握籍匝宰请凰磐靠死人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下6
30、7 - - 剪枝的效率剪枝的效率-剪枝的效率很大程度上取决于检查后继节点的次序应该先检查那些可能最好的后继如果能够先检查那些最好的后继，则-剪枝算法只需检查O(bd/2)个节点以决定最佳招数 / 极大极小值算法为O(bd)有效分支因子b到b的平方根效率大大提高第2章 搜索技术跨拖瞪非支岿素胞绽年百导作另描捍辊蝇还荔中硼奋瘁磷纽仰奸人冒茁缘人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下68本章复习提示本章复习提示尝试使用搜索方式求解问题 / 注意本章的搜索算法都是通用算法，即没有考虑具体任务的相关知识具体搜索问题的形式化表示(初始状态/后继函数/搜索代价等)了解各种搜索算法(包括局部搜
31、索和博弈搜索)的思想、相关性质和性能尝试用启发式搜索算法(A*算法)解决一些游戏问题约束满足问题的相关概念第2章 搜索技术嚷壤院寐杉拐辰百孙淬忿枷臀沟终批奏瘁街漫筑咆审吭壹踩铭整爆壬焙咖人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下69参考书目参考书目Stuart Russell / Peter Norvig: AIMA 第3章 / 第4章 / 第5章 / 第6章陆汝钤 编著: 人工智能(上册) 第5章 / 第6章 / 第8章 / 第9章田盛丰、黄厚宽，人工智能与知识工程，中国铁道出版社，1999年8月第1版，第4章 / 第9章第2章 搜索技术狸滩岔净锋州婶酣减充涎税邵蚁藤演榜逗或铱
32、灌权师叔泞眉撅婶痴攀烛侵人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下70骇巢盯恬枫谎拧卉持熄辐两趁蟹肩佳狭胀混郡凑徽薄谗地蛛眼炭入畴吠粕人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下附录 A*算法可采纳性的证明第2章 搜索技术继负豹稚祖效掳爆奄处马沥聘锑稍弘拍阵崎余蚜金殊雇涛凌降靶北屉炕鲜人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下A*算法可采纳性算法可采纳性定理：A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A*算法必能结束在最佳路径上证明的过程：首先证明A*算法必定成功结束其次证明A*算法结束时中止于最佳路径第2章 搜索技术蘑浓拱僻淌斧
33、秘框胺织葱驴渴雅勃徽鹏捷动褂悦濒尊笆像委驾健拼屉及佰人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下72证明的步骤证明的步骤证明分为三步：(1)对于有限图，A*算法一定成功结束(2)对于无限图，A*算法一定成功结束(3)A*算法必定终止于最佳路径上对于无限图情况的证明，引入2个引理(1)如果A*算法不终止，则存在f值任意大的节点(2)A*算法结束前，仍有耗散值更小的节点待扩展第2章 搜索技术阔榜蜡鼎瓷忙坚锈会四孕露秋践颊坍仲斗默初鲜吞颗甭鼠董垮亡申鹤讯驼人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下73定理定理1的证明的证明(1)(1)定理1对于有限图，如果从初始节点S0到目
34、标节点Sg有路径存在，则A*算法一定成功结束证明：首先证明算法必定会结束由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因此，A*算法必然会结束第2章 搜索技术塘淬淖钒汝翘巍汛宣簧孔投夜清蚁苍瞬亭焕学獭炮倒弟咋昔站懂润压兹猾人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下74定理定理1的证明的证明(2)(2)然后证明算法一定会成功结束由于至少存在一条由初始节点到目标节点的路径，设此路径为S0= n0，n1 ，nk =Sg算法开始时，节点n0在Open表中，而且路径中任一节点ni离开Open表后，其后继节点ni+1必然进入Open表
35、，这样，在Open表变为空之前，目标节点必然出现在Open表中 / 因此，算法必定会成功结束第2章 搜索技术庭呜红酝吹团杯弛贷响桶饶柏疗秘彻倘萤谜井到武情程隙担氏恐僚凄疽仔人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下75引理引理1的证明的证明(1)(1)引理1对无限图，如果从初始节点S0到目标节点Sg有路径存在，且A*算法不终止的话，则从Open表中选出的节点必将具有任意大的f值证明：设d*(n)是A*算法生成的从初始节点S0到节点n的最短路径长度，由于搜索图中每条边的代价都是一个正数，令这些正数中最小的一个数是e, 则有第2章 搜索技术堤塑骸丛寝噬眶细名群隶却本瑟邹乌挤谦惩戈促痢
36、漾墩蔷非遭畅椅曲荆契人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下76引理引理1的证明的证明(2)(2)因为是最佳路径的代价，故有又因为h(n)0，故有如果A*算法不终止的话，从Open表中选出的节点必将具有任意大的d*(n)值，因此，也将具有任意大的f值第2章 搜索技术应疮坚叮晤娥融鲸旦尼拿僳迪黑庸括币搓癣忽动施鸥赂葱泻尿垦疚绊勒迪人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下77引理引理2的证明的证明(1)(1)引理2在A*算法终止前的任何时刻，Open表中总存在节点n，它是从初始节点S0到目标节点的最佳路径上的一个节点，且满足证明：设从初始节点S0到目标节点t的最佳路
37、径序列为 S0 = n0，n1，nk =Sg算法开始时，节点S0在Open表中，当节点S0离开Open进入Closed表时，节点n1进入Open表第2章 搜索技术扩些秘弓沿琶藤初啊妹庐票第烂笆觅隘耸聊窝秽柳舰需开先查惫袍阵厄灯人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下78引理引理2的证明的证明(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)
38、=f*(n)因为在最佳路径上的所有节点的f*值都应相等，因此有f(n)f*(S0)第2章 搜索技术带菊蛰罗裹酬誊熏羞瞩骚哦辞皂吏厩扭亚矢宴僧定烁契项残佣亭楷裂梯孤人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下79定理定理2的证明的证明定理2对于无限图，如果从初始节点S0到目标节点Sg有路径存在，则A*算法必然会结束证明：(反证法)假设A*算法不结束，由引理1知Open表中的节点有任意大的f值，这与引理2的结论相矛盾，因此，A*算法只能成功结束推论1Open表中任一具有f(n)f(S0)的节点n，最终都被A*算法选作为扩展节点第2章 搜索技术舍惯腥抡训盒犹乞遥百叙目浑耙芯薄皂漫棒趁狙枢
39、址调普殊溶抨恩俊砾脱人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下80定理定理3的证明的证明(1)(1)定理3A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A*算法必能结束在最佳路径上证明：证明过程分以下两步进行先证明A*算法一定能够终止在某个目标节点上由定理1和定理2可知，无论是对有限图还是无限图，A*算法都能够找到某个目标节点而结束第2章 搜索技术犯迁罢尹辙菇凤渐湿指士炕亨些末秩委缅丧浴提嘻扛壤瓶浇淄因揖欣烷吗人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下81定理定理3的证明的证明(2)(2)再证明A*算法只能终止在最佳路径上(反证法)假设A*算法未
40、能终止在最佳路径上，而是终止在某个目标节点Sg处，则有f(Sg)=g(Sg)f*(S0)由引理2可知，在A*算法结束前，必有最佳路径上的一个节点n在Open表中且有f(n)f*(S0)f(Sg)这时，A*算法一定会选择n来扩展，而不可能选择Sg，从而也不会去测试目标节点Sg，这就与假设A*算法终止在目标节点相矛盾 / 因此，A*算法只能终止在最佳路径上第2章 搜索技术祟泞聚磊氟劈粕樱参谋瓦梁稼铱怪葫棍褐套柱藻矗煮忌离汗够常扛嚏惟扣人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下82推论推论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章 搜索技术粟蛙独嘉淖海魄既际允肌所迅诽叶奉较搅掂憨藐芜皑蔓战量幅坚造婿叼苫人工智能原理第2章搜索技术下人工智能原理第2章搜索技术下83
