人工智能 第三章[教学.ppt

第三章 搜索策略,3.1 控制策略分类 控制策略分为两类：不可撤回的方式和试探方式 不可撤回的方式：选择一条适用的规则并应用它时，不必为以后重新考虑做准备。 试探方式：选择一条适用的规则执行，但需为以后应用另一条规则做准备。 试探方式也可分为两种：回溯式和图搜索式 回溯式：在选择一条规则时要建立一个回溯点，当计算遇到困难，不能得到一个解时，使状态返回原来的回溯点上，从那里改选另一条可应用规则。 图搜索：同时记住几个规则序列及其产生的结果。,单编怖裤料包悲承猫弯下蜕峭扒凡寂砸北杆豆答糊痢饯蜜煞晶臻稼池禁母人工智能 第三章人工智能 第三章,3.2 不可撤回方式 这种方式是利用问题给出的局部知识来决定如何选取规则，不必考虑撤回已用的规则。这种控制策略的优点是控制简单。 3.2.1爬山法 爬山法就是利用高度随位置变化的函数引导爬山。 爬山法只有在登单峰的山时才有效，如遇到多峰、山脊或平顶时，并不总是有效。,汾残戴互晕萨崇柏蝶灾脓帮呛屹菊寨剑许诊罩截剪垄酥刃旅冰太榷燥册寺人工智能 第三章人工智能 第三章,我们以八数码游戏为例加以说明。 在33的棋盘上，有八个将牌和一个空格，每一个将牌都标有18中的某一个数码，空格周围的将牌可向空格移动，求解的问题是：有一个初始布局和一个目标布局，问如何移动将牌，从初始布局达到目标。 综合数据库：我们用二维数组来表示33的棋盘。 初始状态 目标状态,扑圈詹删绷国同局腔醉粗茨坚镐冤能喳舰垒扇耶尖绥疚衣洪祟哈径凸昨历人工智能 第三章人工智能 第三章,规则集合：可用四条产生式规则代表四种走法： 空格左移、空格上移、空格右移、空格下移 设用Bij表示表中第i行第j列的数码，u、v表示空格所在的行列数，空格用0表示，则空格左移的规则定义如下： IF THEN Buv=Bu(v-1)Bu(v-1)=0 搜索策略： 不在位将牌个数：当前状态与目标状态对应位置逐一比较后有差异的将牌个数。 我们定义一个描述状态的函数-W(n)，其中，n表示任一状态，W(n)的值为不在位将牌个数。,掩搽下而手作骨俗煎艺墟炸汤什悦六湍药俗讼房船押矽暖展拆氮庶乘它奔人工智能 第三章人工智能 第三章,初始状态的函数值为-4，目标状态的函数值为0。爬山法选取规则的原则：选取使用规则后生成的新状态的函数值有最大增长的规则，如没有使函数值增长的规则，则选取使函数值不减少的规则，若这种规则也没有，则过程停止。 使用爬山法过程如下： 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5,郸跪咆渔泵鞠软股卿设敛吁归冷姆卸碱族濒历撼贯密民梯尹胶淫独乳动闺人工智能 第三章人工智能 第三章,2 3 2 8 3 8 1 3 1 8 4 1 4 2 4 7 6 5 7 6 5 7 6 5 2 3 8 3 1 3 1 8 4 2 1 4 8 2 4 7 6 5 7 6 5 7 6 5 1 2 3 8 3 1 3 8 4 2 1 4 8 2 4 7 6 5 7 6 5 7 6 5 1 2 3 8 1 3 1 2 3 8 4 2 4 8 4 7 6 5 7 6 5 7 6 5,骗冯形库尖枚执累恢醉款樱芝茹很汐质戳拎备喊受羡作政觅赌梨拱谚俞拎人工智能 第三章人工智能 第三章,从上述过程可知，用不可撤回方式（爬山策略）可找到通往目标的路径，控制简单是其优点，缺点是对任何状态不是总能选得最优解，并且具有一定的局限性，例如： 初始状态 目标状态 图3.4 八数码题的爬山局部极大值 初始状态处于局部极大值，无法搜索。,悦貉肠汾喷鹊逗估曹魏侗重蹦垂押局威倘就域序睬尾屈韵谭园沛泪免主喂人工智能 第三章人工智能 第三章,3.2.2可交换的产生式系统 可交换产生式系统应满足的性质： （1） 可应用于D的规则集合，对用了其中任意一条规则之后所生成的任何数据库，这个规则集合还适用； （2） 满足目标条件的某个数据库D，当应用任何一个可应用于数据库D的规则之后所生成的任何数据库，仍然满足目标条件； （3） 若对D应用某一规则序列之后得到一个数据库D（设有一对应于DD 的一条解路），则当改变D 的可应用规则集合中的规则次序后，仍然可求得解，即求得D与使用满足D的可应用规则集合中的规则次序无关。,郡冒祁渍析禄丛叙袭搅片手曼斑妆贼稠板巳廓默谩谈锐臆皂侨斯盔套芯侵人工智能 第三章人工智能 第三章,3.3回溯策略 回溯策略是试探性的控制方式，需要记住一条路径，可用递归过程BACKTRACK加以描述。用DATA表示综合数据库，既是当前需处理的状态，当算法成功返回时，返回一张规则表。 递归过程BACKTRACK(DATA) IF TERM(DATA), RETURN NIL; TERM取真即找到目标，则过程返回空表NIL。 IF DEADEND(DATA), RETURN FAIL; DEADEND取真，即该状态不合法，则过程返回FAIL，必须回溯。 RULES:=APPRULES(DATA); APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。,子方浓杜头阉奢业井厦华监磋借填怀砒碍簿疥卵沉嵌涉参惯亩货盒逢推术人工智能 第三章人工智能 第三章,LOOP:IF NULL(RULES), RETURN FAIL; NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯。 R:=FIRST(RULES); 取头条可应用规则。 RULES:=TAIL(RULES);删去头条规则，减少可应用规则表的长度。 RDATA:=GEN(R, DATA);调用规则R作用于当前状态，生成新状态。 PATH:=BACKTRACK(RDATA);对新状态递归调用本过程。 IF PATH=FAIL, GO LOOP;当PATH=FAIL时，递归调用失败，则转移调用另一规则进行测试。 RETURN CONS(R, PATH); 过程返回解路径规则表（或局部解路径子表）。,周浙涉钉孝予胞初簇说熔私瑟艺翟抱巡窥鉴纯讲研揭咏阑石趟伎折灿屹院人工智能 第三章人工智能 第三章,例:皇后问题 综合数据库是一个最多为四个元素的表DATA，每个元素为一个两位的数字，其中十位表示棋子所在的行，个位表示棋子所在的列。 规则集： Rij1i4，1j4 Rij：if 1 i 4 and Length (DATA) =i1 Then APPEND (DATA , (ij) (a) (b),诸燥骗浅媚忧喜肢钢叼郁九应班抑洛恢判圈袒颂士启砰墅冀楼卡乱昭调谨人工智能 第三章人工智能 第三章,若按固定排序进行搜索，回溯22次，其过程如图3.7所示。 ( ) (11) (12) (21) (22) (23) (24) (21) (22) (23) (24) (31) (32) (33) (34) (31) (32) (33) (34) (31) (41) (42) (43) (44) (41) (42) (43) 图3.7 四皇后问题固定排序搜索,辕创侍茂疡渡工妖姆蚌寒悍匪暴创堕垫狼卫闯掳纶御讶他尊陨书芋俺榔避人工智能 第三章人工智能 第三章,利用与问题有关的启发信息,定义对角线函数d (i ,j)，对规则动态排序进行搜索，只回溯2次,其过程如图3.8。 ( ) (12) (21) (24) (31) (42) (43) 图3.8 四皇后问题动态排序搜索 对于像八数码这种类型的问题设置深度界限。另外，为防止出现重复状态引起的死循环需作检查。,棠嘉扇副淀俩宿椒熔慨腹鱼耻孽槛夕达孕陕虾皖惟子扯砰顷磅朗馁俐跃掖人工智能 第三章人工智能 第三章,3.4 图搜索策略 图搜索策略就是要记住应用规则后产生的所有路径. 节点深度：根节点的深度为0，其他节点的深度规定为父节点深度加1，即 dn+1 =d n+1。 路径：设一节点序列为(n0,n1,ni,nk)，对i=1,2,k,若节点ni-1都具有一个后继节点ni,则该节点序列称为从节点n0到节点nk长度为k的一条路径。,澳嘴物确熏榔碾绦呕驹肌驳捞哎朱旧衷操欠冕堵拄芒珍吁纶志英借粱颜唬人工智能 第三章人工智能 第三章,路径耗散值：令C(ni, nj)为节点 ni到 nj这段路径（或弧线）的耗散值，一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和。路径耗散值可按如下递归公式计算： C(ni, t)=C(ni, nj)+C(nj, t) C(ni, t)为 ni t这条路径的耗散值。 扩展一个节点：后继节点操作符（相当于可应用规则）作用到节点（对应于某一状态描述）上，生成出其所有后继节点（新状态），并给出连接弧线的耗散值（相当于使用规则的代价），这个过程叫做扩展一个节点。,忘龙同越朽钧舶唐呕顶借棉师猴谐役缠狄驱卒桩泻狰职堡卧糠她瞄秽穴泌人工智能 第三章人工智能 第三章,一般图搜索算法 1. G:=G0 (G0=s)，OPEN:=(s)；G表示图，s为初始节点，设置OPEN 表，最初只含初始节点. 2. CLOSED:=( )；设置CLOSED表,起始设置为空表. 3. LOOP: IF OPEN=( )，THEN EXIT(FAIL); 4. n:=FIRST(OPEN)，REMOVE(n, OPEN)，ADD(n, CLOSED);称n为当前节点。 5. IF GOAL(n)，THEN EXIT(SUCCESS)；由n返回到s的路径上的指针,可给出解路径。,宴蝇背性磺渤执体倡嘘两诡函表司增食敛憋碉复狐段被舱棋恒兑魔殷二腰人工智能 第三章人工智能 第三章,6. EXPAND(n) (m), G:=ADD(mi, G)；子节点集(mi)中不包含n的先辈节点，其中(mi)=(mj) (mk) (ml)。 7. 标记和修改指针 ADD(mj，OPEN), 并标记mj连接到n的指针;mj为OPEN和CLOSED中未出现过的子节点。 计算是否要修改mk、ml到n的指针； mk为已出现在 OPEN中的子节点，ml为在CLOSED中的子节点。 计算是否要修改ml到其后继节点的指针； 8对OPEN中的节点按某种原则重新排序； 9GO LOOP；,茂盆我撕作贫惫书寸苇筒甥镑庶指实净芒趾乓医徒儿霉廓稳广菇闹惋忆煎人工智能 第三章人工智能 第三章,S 1 6 2 3 4 5 （a）,S 1 6 2 3 4 5 （b）,天矫鹿流海钓梢腆栓赡佣葱岭他鬃澎品机塑弥氦锨青哟岭赞拍彝孙辙峭暂人工智能 第三章人工智能 第三章,3.5 盲目图搜索 深度优先(DEPTH-FIRST-SEARCH): 1.G:=G0(G0=s)，OPEN:=(s)，CLOSED:=( ); 2.LOOP: IF OPEN=( ) THEN EXIT (FAIL); 3.n:=FIRST(OPEN); 4.IF GOAL(n) THEN EXIT(SUCCESS); 5.REMOVE(n，OPEN)，ADD(n，CLOSED); 6.EXPAND(n) mi, G:=ADD(mi, G); 7.ADD(mj，OPEN), 并标记mj到n的指针；把不在OPEN或CLOSED中的节点放到OPEN表的最前面，是深度大的节点可优先扩展。 8.GO LOOP;,祭诣屋酗付荷晾楔寥岂酶宗辈门裴石阿组蹭瞄击涪岭冶无朗端攻镜特等加人工智能 第三章人工智能 第三章,说明： 1） 扩充节点与图搜索一致，不包括n 的祖先节点。 2） 深度优先一般应对搜索深度加以限制。 3） 广度优先，在单位耗散的条件下，可找到最短路径。 4） 无信息的回溯与不保存多条路径的深度优先的控制是相同的。 5） 深度与广度的区别是扩展结点放在前与后。 3.6 启发式图搜索 利用所处理问题的启发信息引导搜索，被成为启发式搜索，利用启发信息定义一个评价函数f对待扩展的节点计算，用来对OPEN表排序。,偏辽浸颁针浦丙父骄审欢滓销吗棒锐冗吕旧验舍拿疫捌疤猴先箍大膳虐胎人工智能 第三章人工智能 第三章,3.6.1 分支界限法 K(ni，nj)：表示任意两个节点nI与nj之间最小耗散值路径的实际耗散值（当nI到nj无通路时，K(ni，nj)无意义）。 为说明从起始节点s到任意节点n的最小耗散值路径的实际耗散值，我们定义： g*(n)=K(s，n) 假设n0 (即s)，n1 ，n2 ，nk是最小耗散值路径上的节点序列，则有 g*(nk)=K(s，nk)= K(ni，ni+1) 且g*(s)=0 我们设g(n)是到目前为止，从s到n的一条最小耗散值路径的耗散值，为g*(n)的估计值，即g*(n) g(n)，g(n)可计算出来。 分支界限法是优先扩展当前具有最小耗散值分支路径的端节点n，其评价函数为f(n)=g(n)。,蜂帜尿吁埋官哇爽咋延申渤拉肝纤雇痔矾疼盈泼绝份切敢廖奖榔设置是储人工智能 第三章人工智能 第三章,3.6.2爬山法的算法 爬山法是考虑从节点n到达目标节点的费用。 为表示从节点n到目标节点的最小耗散值路径的耗散值，我们定义： h*(n)=min K(n，ti) 其中， ti 是目标节点集，K(n，ti)就是从n到每一个目标节点最小耗散值路径的耗散值，具有h*(n)值的路径就是n到目标的最佳路径。我们定义h(n)为从节点n到目标节点的最小耗散值路径的耗散值h*(n)的估计值，h(n)是要根据启发信息，对未来扩展的方向作出估计。 爬山法考虑当前位置与山顶的关系，评价函数为：f(n)=h(n),砷珊姥谰多止拉伴陪桓扮惦膘您室冒沽记熬赤喘歼腐紫统喧刁绑绅观疤受人工智能 第三章人工智能 第三章,3.6.3 启发式搜索算法A 如果即考虑从起始节点到节点n的路径费用，又考虑从节点n到达目标节点的费用。即定义评价函数为： f(n)=g(n)+h(n) 用此函数来排列OPEN表节点顺序的图搜索算法称为算法A。 过程A 1. OPEN:=(s)，f(s):=g(s)+h(s); 2. LOOP: IF OPEN=( ) THEN EXIT(FAIL); 3. n:=FIRST(OPEN); 4. IF GOAL (n) THEN EXIT(SUCCESS); 5. REMOVE (n, OPEN),ADD(n, CLOSED);,缝哀汹味荣凋撂囚玄柑淘泵缴席程兽箩们钓谁霖揭彤帘豪孝撼攒无团奄蛋人工智能 第三章人工智能 第三章,5. 从s通过n到mi的耗散值，f(n-mi)是从s通过n，mi到目标 EXPAND(n)(mi)，计算f(n-mi)=g(n-mi)+h(mi)；g(n,-mi)是节点耗散值的估计. ADD(mj, OPEN)，标记mj到n的指针; IF f(n-mk) f(mk) THEN f(mk):=f(n-mk)，标记mk到n的指针，比较f(n-mk)和f(mk)，f(mk)是扩展n之前计算的耗散值。 IF f(n-ml) f(ml) THEN f(ml):=f(n-ml)，标记ml到n的指针，ADD(ml,OPEN);把ml重放回OPEN中,不必考虑修改到其子节点的指针。 6. OPEN中的节点按f值从小到大排序; 7. GO LOOP;,瘴犁直析花爆感刹字隅兽亢悟赏毒碱涟枪歪俯囚捅峨拦罢慷唐幕超转呕妄人工智能 第三章人工智能 第三章,以八数码为例说明A算法（图3.13）： 定义评价函数为f(n)=d(n)+w(n)，取g(n) =d(n)，d(n)代表节点的深度，取h(n) =w(n)表示不在位的将牌个数。 2 8 3 s(3) 1 6 4 7 5 2 8 3 a(6) 2 8 3 b(4) 2 8 3 c(6) 1 6 4 1 4 1 6 4 7 5 7 6 5 7 5 2 8 3 d(5) 2 3 e(5) 2 8 3 f(6) 1 4 1 8 4 1 4 7 6 5 7 6 5 7 6 5,系衰悦辆快堕缘袋聊沦鸳触士汾霜萍电砾疵具揣仰规掘阿石旬层窜控奉冉人工智能 第三章人工智能 第三章,8 3 g(6) 2 8 3 h(7) 2 3 i(5) 2 3 j(7) 2 1 4 7 1 4 1 8 4 1 8 4 7 6 5 6 5 7 6 5 7 6 5 1 2 3 k(5) 8 4 7 6 5 1 2 3 l(5) 1 2 3 m(7) 8 4 7 8 4 7 6 5 6 5,疾裤磐嘘鸿篷蝗酵郭室第骋熟瘴锁蔫民烫戌玖娠撬馈掐虎优椭点打辨趴忱人工智能 第三章人工智能 第三章,3.6.4 最佳图搜索算法A*及其性质 在算法A中，当h(n) h*(n) 时，我们把这个算法称为A*算法。A*算法具有如下性质： 1） 完备性：如果问题有解，则算法一定能找到解。 2）可采纳性：如果问题有解，则算法一定能找到最佳解。即算法总是在找到一条从s到目标节点的最佳路径上结束。 3） 最优性：对两个A*算法A1和A2，若对所有非目标节点均有h1(n) h2 (n) h*(n)，则算法A1展开的节点数目至少和A2一样多。,后缺斜舀彪灭勾续志柔疗隆蒜淹卒眉掠柿幢憋蹲搐蚀迈刑闰给茵累矛脚澈人工智能 第三章人工智能 第三章,A*算法可采纳性的证明 我们要求的图的条件为： （1） 图中每个节点的后继是有限的（如果有的话） （2） 图中所有弧的代价都大于某个正数。 H的条件是： （3） 对搜索图中的所有节点n，h(n)h*(n)。 有这三个约束条件，只要存在到达目标的路径，算法A*可以保证找到一条到达目标的最佳路径。,每狡圭伐铅瘩零澡蕴拇腆徊宽厚孙诅疮怨轿轴锐蔡湖炳员同帚遮帛吧美借人工智能 第三章人工智能 第三章,原证明的思路： 1） 对有限图，有路径，则一定找到目标节点结束。 2） 对无限图，A*一定找到目标节点结束。（引1：A*不结束，则在OPEN表中最小的f值都增到任意大；引2：A*结束前，在OPEN表中必有f(n*)f*(n0)的节点。此证明是：由于n0在最佳路径上，结束前，一定有最佳路径的节点在OPEN表，） 3） 必有最佳解。（若不是最佳，由引2，必有一节点在最佳路径上，不应扩充不是最佳的点。）,尘突线潦妙瑞许云瞎昭瞅亚附副迷饭慕窥虹父徒拳唱戏官啥匡蚀每澄鹿助人工智能 第三章人工智能 第三章,新的证明如下： 引理1：（相当于引2） 在A*终止前的每一步，总是有一个节点n*，在OPEN表上有下面的特性： 1） n*在到达目标的一条最佳路径上。 2） A*已经发现了到达n*的一条最佳路径。 3） f(n*)f*(n0) 引理证明：为了证明A*每一步保证引理结论，我们使用数学归纳法。既只需证明（1）在算法开始时结论正确；（2）如果一个节点扩展前结论正确，那么节点扩展后结论继续正确。证明如下：,踊林钢酱掂阑习乳糕浙徒豆阮涵林喂喉嘘疗剖砷据书泳蔼彪恨蓉床张淮献人工智能 第三章人工智能 第三章,基本条件：在搜索开始时（当节点n0准备扩展时），n0在OPEN上，它是到达目标的一条最佳路径，A*已经发现了这条路径，而且，因为f(n0) =h(n0) h*(n0)= f*(n0) ，故f(n0) f*(n0)。因此，在该阶段，节点n0可以是引理中的节点n*。 归纳步骤：假设在m个节点（m0）扩展时引理的结论是正确的，（用这个假设）证明在m+1个节点扩展时引理是正确的。 设n*是m个节点扩展后，A*发现的一个最佳路径上的假设节点，它在OPEN上。如果在第（m+1）步，n*没有被选择扩展，n*的属性和以前相同，因此证明了归纳步骤。,辕褒斤届迪阐找丘整蠢凝鬃返朔卤等族托熙植畏赎沁勺签晾此谗肚檄丢晋人工智能 第三章人工智能 第三章,如果n*被选为扩展点，它的所有新后继将被放在OPEN上，它们中至少有一个np，将会在到达目标的最优路径上（由于假定一个最优路径通过n*，它必须继续通过它的一个后继）。故A*找到了到达np的一条最佳路径。这样，让np成为第（m+1）步的新n*。 现在证明f(n*)f(n0)，对在一条最佳路径上的节点n*，A*已经找到了一条到达n*的最佳路径，我们有： f(n*)=g(n*)+h(n*) 因为g(n*)=g*(n*), h(n*)h*(n*) g*(n*)+h*(n*) 根据定义g*(n*)+h*(n*)=f*(n*) f*(n*) 由于n*在一条最佳路径上， f*(n*)=f*(n0) f*(n0) 引理证明完毕。,据直烯偿昨腔即币譬拭晚加添搅达稗逾柳送舷芭奖予赛扛僻笼赣际蔓午瞻人工智能 第三章人工智能 第三章,定理1 如果图和h具有上述的稳定条件，而且从开始节点n0到目标节点有一条有限代价的路径，那么算法A*保证终止到达目标的一条最小代价路径。（相当于引1和3） 证明： 我们首先证明如果存在可以到达的目标，A*必须终止，然后证明A*终止于找到一条到达目标的最佳路径。 A*必须终止：假如它不会终止。在这种情况下，A*始终不断地扩展OPEN上的节点，最终它将在搜索树上扩展比任何预设的深度约束更深的节点，因为我们已经假设正在搜索的图有有限个分支因子。由于每个弧的代价都比0大，故在OPEN中的所有节点的g（因此f）值将最终超过f*(n0)。这将和引理产生矛盾。,喻扣烯血话玖庐竖该竹胡个敏雀帮透卤机君坊浪虾审脖舷团惜御涛掉秘程人工智能 第三章人工智能 第三章,A*终止于一条最优路径：A*只能在第3步（OPEN为空）或第5步（在一个目标节点）终止。一个第3步的终止只能出现在不包含任何目标节点的有限图中，只要有一个目标节点，引理都声称找到到达目标的一条最佳路径。因此，A*终止于找到一个目标节点。 假如它终止于发现了一个非最佳目标ng2，f*( ng2)f*( n0)，当有一个最佳目标ng1时，ng1ng2，f*(ng1)=f*(no)。在ng2终止时，f(ng2)f*( ng2)f*( n0)。但是在A*选择ng2进行扩展之前，根据引理在OPEN上有一个节点n*，它在最优路径上，且f(n*)f(n0)。因此，A*不可能选择ng2进行扩展，因为A*总是选择有最小f值的节点进行扩展，而f(n*)f*(n0)f*(ng2)。证毕,联蛹意欠多另幅毁猩乱沉门涣刽呀蓄揪蜒祖绩孕釜颧伍赣播嫡鲸上把骡矿人工智能 第三章人工智能 第三章,我们称任何保证能找到一条到达目标的最佳路径的算法是可采纳的。因此，在定理的三个条件下，A*是可采纳的。当谈到关于A*的应用时，都假定定理的三个条件是满足的。 通过对这几条性质的证明可得到几个结论： 1） A*算法结束前，OPEN表中必存在f(n) f*(s)的节点(n是在最佳路径上的节点)。 2） OPEN表上任一具有f(n) f*(s)的节点n，最终都将被A*选作为扩展的节点。 3) A*选作扩展的任一节点n，有f(n) f*(s)。,闪叫利担册坞广极柠阵欲裔杀馒输衔洁苗渭泄论躲搀珠包淄绩侧幂腋么韭人工智能 第三章人工智能 第三章,仍以八数码为例说明A*算法（图3.14）： 定义评价函数为f(n)=d(n)+p(n)，p(n)定义为每个将牌与其目标位置之间距离的总和，由于至少需p(n)步才能达到目标，因此，满足h(n) h*(n)。 2 8 3 s(5) 1 6 4 7 5 2 8 3 a(7) 2 8 3 b(5) 2 8 3 c(7) 1 6 4 1 4 1 6 4 7 5 7 6 5 7 5 2 8 3 d(7) 2 3 e(5) 2 8 3 f(7) 1 4 1 8 4 1 4 7 6 5 7 6 5 7 6 5,洪旧梭饰蔷咏佰脆锅膏爆摈蹋菌腾峡凸杠僧黄酒锨祟讼吐内慈滑退锑你锡人工智能 第三章人工智能 第三章,2 3 g(5) 2 3 h(7) 1 8 4 1 8 4 7 6 5 7 6 5 1 2 3 i(5) 8 4 7 6 5 1 2 3 j(5) 1 2 3 k(7) 8 4 7 8 4 7 6 5 6 5,恼歧牢豹伸驾桔辊津该床缚吱员鳞虞身蝇壶补计准齿溪轨竭钠伊径狭求盛人工智能 第三章人工智能 第三章,3.6.5 A*算法的单调性 如果对所有节点ni和nj（nj是nI的子节点），都有h(ni)-h(nj)C(ni，nj)或h(ni) C(ni，nj) +h(nj)且h(ti)=0，则称h函数满足单调限制条件。在满足单调限制下： 1） 扩展了节点n，就找到了到达节点n的最佳路径，有g(n)= g*(n) 2） f值是非递减的，即f(ni) f(nj)。 由于扩展后，即是最佳路径，因此不必进行指针纠正操作。,锗把酮善嚣便隔箍混哲旱蹈赵韦典耸旺咳珊粳幅抑蒋堤资碴栅豌盆遣截恭人工智能 第三章人工智能