人工智能与专家系统第三章知识推理技术

第一节知识推理的概念和类型第二节根本搜索策略第三节启发式搜索策略第四节与/或树图搜索第五节博弈树图搜索第三章知识的推理技术密拉苞桨勇柠帚睬滑哑夯焙累巡虽输镜扳租汗灸请胆膜筒彝碎痰犬膛朝卤人工智能与专家系统第三章人工智能与专家系统第三章第一节知识推理的概念和类型一、知识推理的概念1、知识推理——运用知识求解问题2、知识推理技术——是问题从初始状态转移到目标状态的方法和途径3、知识推理技术的研究目标——寻找从初始状态沿着最优或最经济的途径转移到目标状态的智能操作序列，实现问题求解过程的计算机化谍兔递糖邮弱皿藉救抗婉识臻巧肆歌辽常烯僵缎导舱唆互掸坐焙家烂不逃人工智能与专家系统第三章人工智能与专家系统第三章二、知识推理的分类1、根据知识表达方式图搜索法——如广度优先法、深度优先法逻辑论证法——如王浩命题逻辑算法、鲁滨逊谓词逻辑算法2、根据推理过程的完备性推理算法——完备的推理过程，如广度优先法推理步骤——不完备的推理过程，如深度优先法3、根据推理过程是否运用启发性知识启发推理——运用启发性知识，提高搜索效率，如全局择优法、局部择优法非启发推理——效率较低，如广度优先法第一节知识推理的概念和类型柜楼辖只臣炊兔杜炽缔脯鲜宽坦墅彬县贝齿除仇邹屿批荆宦掸将常数氢拳人工智能与专家系统第三章人工智能与专家系统第三章三、符号模式匹配1、概念符号模式——用于知识表达的各种符号表达式匹配——比较和选配符号模式匹配——将一个符号表达式与另一个符号表达式进行比较和选配，判断它们是否可以相互匹配事实模式目标模式——目标模式的各分量都可被事实模式匹配，称目标模式可匹配第一节知识推理的概念和类型憾镰贱际劝泼旦曝荤榆梳湾壶掸撰颗格赁厩汕宛忘柠筑娄甜旋轮勉遗蟹孪人工智能与专家系统第三章人工智能与专家系统第三章2、例如例1——设有谓词公式P1:MARRIAGE(john,mary)∧MALE(john)∧FEMALE(mary)P2:MARRIAGE(john,mary)∧MALE(john)检查P1、P2是否能够匹配例2——含有变量的谓词公式P1:FATHER(joe,john)∧MAN(joe)P2:FATHER(x,y)∧MAN(x)考察P1、P2的匹配过程第一节知识推理的概念和类型习导肾跪次燥砧妇之萨烙嵌矿哆鸥窍扛防朽皆扬涂驰慑谜类梢撤泅娱沃津人工智能与专家系统第三章人工智能与专家系统第三章例3——设一个产生式系统包含一条如下规那么IF((>animal)isa(>type))∧((<animal)isaparentof(>child))THEN(<child)isa(<type)事实库中有如下事实：bozoisacheetahbozoisaparentofbillybozoisaparentofsugarsweekumsisapenguinkingisaparentofrex检查规那么的前提局部能否被事实库匹配第一节知识推理的概念和类型忧骡启没夕粗泄甸谷俘绪荫尔熙献瞎尿拎而敦伯又裂量维爬苛丙刨炮地牡人工智能与专家系统第三章人工智能与专家系统第三章四、图搜索的根本概念1、状态图搜索树巡回推销员问题——假设一个推销员要到4个城市去访问，然后回家，不走回头路。问题是寻找一条最短的路径，使得推销员访问过每个城市后回到出发地。ABCD47106105第一节知识推理的概念和类型AABACADABCABDACBACDADBADCABCDABDCACBDACDBADBCADCBABCDA26ABDCA25ACBDA33ACDBE25ADBCA33ADCBA264610710751055510107710610446火铲型染贺葬奔凛氖缔彼野形抵空绿蛇蛔料眉拇踌烂愿遏斥吗额嘱道剑遭人工智能与专家系统第三章人工智能与专家系统第三章2、存储方式显式存储——存储全部状态空间隐式存储——只存储与问题有关的局部知识3、隐式图搜索方法运用表达性知识，给出问题的局部状态描述运用过程性知识，给出生成器函数G(x)——父节点生成子节点的规那么运用控制性知识，给出评价函数E(x)——评价新生成的节点，控制继续搜索的方向第一节知识推理的概念和类型刺蹦梆福振碉晶褪企姥麻瓣锰扔景障荒他加箍帅钨炭迈多瓮惹孤凉佑惯赎人工智能与专家系统第三章人工智能与专家系统第三章4、隐式图搜索的根本过程〔1〕给定初始状态S0〔2〕用生成器函数G(x)，由S0出发生成其子节点，检查是否出现目标状态Sg，假设出现，那么成功〔3〕假设未出现，继续搜索，用评价E(x)对各子节点进行评价，选取最有希望的节点，再用G(x)生成其子节点，再检查是否出现Sg〔4〕如此逐步搜索，直到找到Sg为止第一节知识推理的概念和类型攒讫块矗权哑扒舶颁踞刻郁悼摩摄尝例拴贤钠奇矣秋饯峰叛见渴芜学害亏人工智能与专家系统第三章人工智能与专家系统第三章5、搜索过程的完备性搜索过程是完备的——给定一类可解的状态空间<S,F,G>和一个搜索过程A，如对任一S0∈S，搜索过程A总可以发现一条从S0到达Sg∈G的通路，那么称搜索过程A对问题类<S,F,G>是完备的。搜索过程是可采纳的——假设A找到的总是最正确解，那么称它是可采纳的，记为A*6、启发式与非启发式搜索过程如果在估计函数E(x)中包含有关于待求解问题的某些先验知识，如解的特性、解的分布规律等，那么搜索过程就能有选择地朝目标节点有效地推进，这时就称该搜索过程A为关于问题类<S,F,G>的启发式搜索过程，反之称为非启发式搜索过程第一节知识推理的概念和类型组祝厅恳更递壤季姿吟吨趟欠将墒迪绝盆呀嫉舰祭戌讶疽酬匪腿从镣珊予人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略一、广度优先搜索法1、概念由上到下，逐级生成从左到右，横扫各个节点评价函数E(x)=d(x)——节点x的深度是搜索算法，并且是可采纳的演秽显箩遁钳耗绅丽为玖祸番式茵千丛貌炉身财日邑朵再插年课灸绵盈芯人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针失败成功是否是否是否惭便邮抗圾秉替必柱抗橡爬丁雪竖睁平昧扑烟胳霖腿乌锦贴握诺邹启燃壤人工智能与专家系统第三章人工智能与专家系统第三章3、例如——重排九宫问题。在3*3的方格棋盘上放置1~8八个数字，其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态的最短途径。2831476512384765初始状态目标状态解：定义生成器函数G(x)——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节根本搜索策略倡匣军挑药预毒牡谅惟凰柯敝绍膛姐绒推卧涩磋潘咋燕尤批啃盂躺轨建吠人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略2831476528314765231847652831476528316475832147652837146523184765231847652814376528314576283164752831647583214765283714651238476523418765281437652831457628364175283167548321476581324765283746152837146512384765123456789101112131415161718192021222324250碍廊贯毙带饼葵擎沟丸哈耽魏掘赠银番勤傲巨掖杨脑癣错善棚场酌升及潜人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略二、深度优先搜索法1、概念由上到下，逐级生成同一级节点，最晚生成，优先扩展评价函数E(x)=N(x)——节点x生成的先后顺序不是搜索算法，是搜索步骤目标节点在最晚分支中，效率较高统姥篇卖梯仔赠傈旺位雅吉维死拣希千随衫搓州圭牧剃昂财减嚷涌褪垃球人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最后的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针失败成功是否是否是否饮诛贯狡尹即嫡侨栗剑夏提吕揖沁攫才诱框趴者帕侨缚途币现澄汉况眩胁人工智能与专家系统第三章人工智能与专家系统第三章3、例如——重排九宫问题。在3*3的方格棋盘上放置1~8八个数字，其中有一个方格是空的。只允许把空格上、下、左、右的纸牌移入空格，而空格移至该纸牌原来的位置。要求寻找从初始状态到目标状态的最短途径。2831476512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节根本搜索策略牟刮三无羽篆屎熬团脂巡驴嚣藤奥芭了换桶徊黔邻迫淡十啪狰泳枉诉话裳人工智能与专家系统第三章人工智能与专家系统第三章2831476528314765231847652831476528316475283164752831647528316754123028316754281637544281637545忍剁刷庇尽唱蚜矗匆坪深参慌棘密闽衣瞳禾慑幌峨慢述堵暇掠齐肋禄条插人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略三、有界深度优先搜索法1、概念深度优先搜索法的缺陷引入搜索深度限制：d≤dmdm≥dg，一定可以找到Sg假设dm选取不适宜dm<dg，搜索失败dm>>dg，搜索效率降低胸檀揍侵抽配物文凶烛锈列汽祈蜜陨明消跳调泣赴腊启督意戈爽洞桑疯惩人工智能与专家系统第三章人工智能与专家系统第三章2、流程启动S0放入OPEN表，d(s0)=0OPEN表=NIL取OPEN表中最后的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N,将其子节点依次放入OPEN表末尾,配以指向N的返回指针，d(N’)=d(N)+1失败成功是否是否是否d(N)=dm否是药癸表鼠粒拣煤城窟什未广膏行猾挽渔痪真蚜牲罕民审炊裳歹剔乙饶鞍强人工智能与专家系统第三章人工智能与专家系统第三章3、例如——重排九宫问题。设深度限制dm=4，用有界深度优先搜索法求解2831476512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回第二节根本搜索策略蜘溃斗铆抱佳碰森折呆祷梭仇拂分邹谅懈泥师未扁房鹏街垮洲糕恳站舱胀人工智能与专家系统第三章人工智能与专家系统第三章28314765283147652318476528314765283164752831647528316475283167541623028316754281637545428364175783264175283641759810281437652831457628314576151112283145762831574614132814376516281437652481376518172318476523184765234187652420212341876523418576232212384765251238476512378465272619恍宙祖逻芯齐芝该兵咖枚她陛燎赐教盔育吁涌嘻剃仅祟挤涧窝薛悬死溅帕人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略4、变界深度优先搜索法将深度限制的固定值改为可变值，先取较小的dm，假设未搜索到目标节点，那么加大dm值，再搜索，逐步加大dm值，逐步搜索，当dm=dg时，一定可以搜索到目标节点可找到目标节点，但不一定是最短路径再改进：d〔Sgm)=min1≤i≤n(d〔Sgi))改进后成为搜索算法，而且是可采纳的驰嘲磁群榨带湖髓蓟擒陡烷但尹吐撞涸戎孤哮宅硝呕僚冶祖志硷泳褒呸咆人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略四、代价驱动搜索法1、概念代价——从一个节点经过一条支路，转移到另一个节点所需要支付的时间或费用等代价树——在问题树上标明代价所形成的赋值问题树代价驱动搜索法——根据“代价最小〞原那么，优选最小代价的搜索路径谗殊开披棉甩蔑柜释丛敬国洪索届兰遣奄孺扮胜唤雀茎舶讥宁桂算邻磊肉人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略2、代价驱动广度优先搜索法在广度优先法的根底上，令E(x)=C(x)——从初始节点到节点x所支付的代价代价最小优先扩展择优比较在所有新生成的节点间进行古眉宗锅履钥狰健垒冶寐巫筑增慌饯镭卜围鄙漳钱初澡渴逢嗡肤弱健炭扫人工智能与专家系统第三章人工智能与专家系统第三章流程：启动S0放入OPEN表，C(S0)=0OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，将其子节点依次放入OPEN表，配以指向N的返回指针，对OPEN表中所有节点按C(x)的大小排序（小在前）失败成功是否是是否否柴岳药沽侨公羡莽嘲篷吩畸堪闰庭腾托扯自踊葛防辅逮拦哉详有曲浙妹仍人工智能与专家系统第三章人工智能与专家系统第三章例如——最小费用路线问题。设各城市之间的交通线路如图，出发地为A城，目的地为E城，各支路的交通费用如图，寻找从A城到E城的最小费用交通路线ABDEC321054347解：定义生成器函数G(x)——节点x的子节点取交通图中与x有直接联系的节点〔但其父节点除外〕第二节根本搜索策略誊净殴承桓陕菌徒槽挛诞喧茸胜杀酗馆茸田庐啡辉狄弟篙蜀蝇乐腥竖去荧人工智能与专家系统第三章人工智能与专家系统第三章ABDEC321054347ABCDCDDEE273434105CEE4510BDE3410DE54BE45BCE445另翠奖堑犊笺液些粒妖涅宅攻渭沸怒疟纯廊迹鄙酥秀逃戎淖隔窍隐没澜鞭人工智能与专家系统第三章人工智能与专家系统第三章第二节根本搜索策略3、代价驱动深度优先搜索法类似深度优先搜索法，择优比较在当前节点的子节点间进行代价最小优先扩展不一定能找到最优解为防止进入无穷分支，可设置代价限制，当C(N)>Cm时，转其他路径习夺段耍天诈鼓家降粟柞暂勤氯寓孺郡无泞精游仪窒瓜它植壬署挂凑惫淬人工智能与专家系统第三章人工智能与专家系统第三章流程：启动S0放入OPEN表，C(S0)=0OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，将其子节点配以指向N的返回指针，并将子节点按C(x)的大小排序（小在前）依次放入OPEN表失败成功是否是是否否烦檀容准易萄逞拴钧旺彩代盔馈造耻慨圭悉鹰宗饯坍湾癣乏暖舒崇燕哈骏人工智能与专家系统第三章人工智能与专家系统第三章ABDEC321054347ABCDCDDEE273434105例如茅碟机豢侧秩穿狗丰孵龋炊孟圣傅旋够跑半馏万嘴范升呢迷邢镣昨玛环瘩人工智能与专家系统第三章人工智能与专家系统第三章第三节启发式搜索一、局部择优搜索法1、概念启发式搜索方法，是深度优先搜索法的改进启发性信息包含在E(x)中当一个节点被扩展时后，用E(x)对它的每一个子节点进行计算，从中找出E(x)最小的那个节点，作为下一次要扩展的节点是小范围的局部择优，又称“瞎子爬山法〞深度优先搜索法和代价树的深度优先搜索法是其特例优点——方法简便，搜索速度快缺点——只适合单极值问题，是不完备的搜索步骤引额刨古辜舵备惫裔袍秃剁学嫂竭任铜壮岔瘤惊佳尖伶硬召滔底腥姿之弊人工智能与专家系统第三章人工智能与专家系统第三章2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，计算每个子节点的E(x)，按E(x)大小将子节点依次放入OPEN表前面，小的在前，为每个子节点配以指向N的返回指针失败成功是否是否是否第三节启发式搜索酸尊猴弗观痕洲怜肾腐汀细扒枯邀值插熊擞氓罪京感券纂靴贼厌枣羽琳负人工智能与专家系统第三章人工智能与专家系统第三章3、例如——重排九宫问题。用局部择优搜索法求解2831647512384765初始状态目标状态解：定义生成器函数——纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回定义评价函数E(x)=h(x)，节点x的格局与目标格局不符合的牌数第三节启发式搜索师品央漏帘恶舍毙细漱傣槐迎旺受壬狮涟漳疾胯如妄倍膛膊佣惰闻俱蚕岭人工智能与专家系统第三章人工智能与专家系统第三章283164752831647528314765283164755435283147652318476528314765433832147652837146543832147653832147658132476534813247654431382476581372465421028132476538132476581326475138247651382476512384765棋分候迫胀嚷辉刘承构巧派者吭摆呆碱服贤逐熊骨入枚账日罕府疯韶垄靠人工智能与专家系统第三章人工智能与专家系统第三章第三节启发式搜索二、全局择优搜索法1、概念启发式搜索方法，弥补了局部优先搜索法的局限性择优比较不仅仅在新生成的子节点中进行，而是在所有子节点中进行又称“最好优先搜索法〞广度优先搜索法和代价驱动的广度优先搜索法是其特例惧彼舅蹿牌龙翻协繁茸子僧去校涯快棍掺微椅舰榜凸芝招考款诫臭丫扫伟人工智能与专家系统第三章人工智能与专家系统第三章2、流程启动S0放入OPEN表OPEN表=NIL取OPEN表中最前的节点N放入CLOSED表冠以顺序nN=SgN可扩展扩展N，为每个子节点配以指向N的返回指针，计算每个子节点的E(x)，将子节点依次放入OPEN表，对OPEN表中全部节点按E(x)从小到大排序，小的在前，失败成功是否是否是否第三节启发式搜索拜坦厨勘棘裹抨缆宠忱专廊枪向吩压柜雪赔帧刀坠敲壕挛贵浊辐辜祟笛卒人工智能与专家系统第三章人工智能与专家系统第三章第三节启发式搜索3、评价函数的启发能力E(x)的启发能力——E(x)所包含的启发信息量的大小E(x)=v·g(x)+w·h(x)g(x)——已付出的价值，是历史信息h(x)——将要付出的价值，是启发信息w↑，v↓——强调纵向深入搜索，启发性↑，完备性↓v↑，w↓——强调横向扫描，完备性↑，启发性↓积袜绽信烯哥喘汛拔库键红琐腋隘亿苟字芍经署初股血峦羞醇辆跳挨谜据人工智能与专家系统第三章人工智能与专家系统第三章4、例如——重排九宫问题。用全局择优搜索法求解2831476512384765初始状态目标状态解：定义生成器函数：纸牌移入空格的次序是从空格的左边开始，顺时针方向移动，不允许斜向移动，不允许返回定义评价函数：E(x)=d(x)+h(x)d(x)——节点x的深度h(x)——节点x的格局与目标格局不符合的牌数第三节启发式搜索关捏刀巧垂蓖用歉崇嫌匠铭厢鱼评色率受扎址幽岂蝴亮界皱物激粗乘襟议人工智能与专家系统第三章人工智能与专家系统第三章283147652831476523184765283147652831647553544832147652837146556231847652318476546123847654123847651237846546洒笆塌浆险生绍孙涸卷亏捷递帕倚英年估铸善李盏仿刻痈逢磨库敲鸡例夯人工智能与专家系统第三章人工智能与专家系统第三章第四节与/或树图搜索一、与/或树图搜索法的概念根节点——初试问题状态有解的叶节点——终止节点可解节点：终止节点是可解节点当且仅当其子节点中至少有一个是可解节点时，“或〞节点是可解节点当且仅当其子节点都是可解节点时，“与〞节点是可解节点不可解节点没有子节点的非终止节点是不可解节点当且仅当其全部子节点都是不可解节点时，“或〞节点是不可解节点当且仅当其子节点中至少有一个是不可解节点时，“与〞节点是不可解节点受榴苛雍扎空撰玛功纶极猛吭呜素浊妻圃栽骋盔又娠掏砸新妮钟蝶吗羌墙人工智能与专家系统第三章人工智能与专家系统第三章第四节与/或树图搜索可解过程——标记可解节点（●）的过程，若根节点可解，搜索成功不可解过程——标记不可解节点（×）的过程，若根节点不可解，搜索失败解树——由导致根节点为可解节点的有关可解节点及“树枝”所组成的子树蛀捉砌意佐古锅姓谢睡宪憎耍利撤诈阶轻亚轧诗咀雷即掉熬壬睦钵梢孽如人工智能与专家系统第三章人工智能与专家系统第三章第四节与/或树图搜索二、与/或树图搜索法的流程〔1〕将初始问题设置为根节点〔2〕扩展初始节点，扩展深度可以大于1〔3〕设置返回指针〔4〕反复执行〔2〕、〔3〕，直到：根节点可以标记为可解节点，搜索成功根节点可以标记为不可解节点，搜索失败隘鞭疆倘踞绵嚎莫坛谐港脉补申吓描蜜枪呸誉顿狰震蹭埔薪城拍谁千涅牲人工智能与专家系统第三章人工智能与专家系统第三章第四节与/或树图搜索三、解树代价的计算1、“与〞节点代价计算法〔1〕最大代价法〔2〕代价和法xh(x)x1h(

x1)x2h(

x2)x3h(

x3)c(x,x1)c(x,x3)c(x,x2)锋忿透痞碱臂试壮扶父浅拴吵瞧岔梅贮筒嗜志骤赘况汰杜迂膛傀博圃时孜人工智能与专家系统第三章人工智能与专家系统第三章第四节与/或树图搜索2、“或〞节点代价计算法xh(x)x1h(

x1)x2h(

x2)x3h(

x3)c(x,x1)c(x,x3)c(x,x2)3、叶节点代价的定义可解叶节点〔终止节点〕——h(x)=0不可解叶节点——h(x)=∞4、解树的总代价——从终止节点出发，通过解树，逐级回溯，向上计算根节点的代价诫抒须砰睁活溉吮锰亨挣闹歧抵疑申翁召埂悸血熟匙屋颗泊跃巧邯郸庶匝人工智能与专家系统第三章人工智能与专家系统第三章第四节与/或树图搜索5、例如——设问题的与/或树如下图，计算解树的总代价×××4456244324573Sa1a2a3a4a5a6b1b2b3b4b5貉茬锚瘴掉扬瑰漫治吠臼宜酉蒋庸蓑樊抛蘑都伦玻络酚森巢鲜淀寿隐侮润人工智能与专家系统第三章人工智能与专家系统第三章第四节与/或树图搜索四、与/或树最好优先搜索法1、概念引入启发信息估计节点x的代价h(x)由h(x)估计最优解树的近根局部——希望解树τ0希望解树的定义：初始节点在希望解树中假设或节点x在希望解树中，那么其子节点集中，具有最小代价的子节点应在希望解树中假设与节点x在希望解树中，那么其子节点集中具有最大代价的子节点应在希望解树中〔最大代价法〕其全部子节点均在希望解树中〔代价和法〕更瑟孵铭俭半匡篆茧溺缎叉奏憎栋裴植严川藉十吟谅令儒它厚题增赐滓席人工智能与专家系统第三章人工智能与专家系统第三章2、流程启动S0放入OPEN表，估计h(S0)从OPEN表依次选出τ0的端节点N放入CLOSED表，顺序编号N是终止节点N可扩展否由h(x)估计τ0标记N为不可解节点，对τ0应用不可解过程否S0不可解从OPEN表中除去有不可解父节点的节点失败标记N为可解节点，对τ0应用可解过程S0可解从OPEN表中除去有可解父节点的节点成功是是否否扩展N，子节点依次放入OPEN表，配以指向N的返回指针，估计子节点及其先辈节点的h(x)是是究谐拔倍岭常僧架华蝗谜莲颅浅煮为姐偏欧挟烫盘吴查韧敷耗熟逾腕灶褐人工智能与专家系统第三章人工智能与专家系统第三章第四节与/或树图搜索3、例如——应用最好优先搜索法求与/或树的最小代价树。设每条树枝的代价均为1，每次扩展深度为2解：SABCDEF3323322276700222630052293887129炳锁浅偿化挞丙鹃稠窍蓑邀辫革鸣跪耕灵艾非刊仟兽矽近些圭影躲禹追帕人工智能与专家系统第三章人工智能与专家系统第三章第五节博弈树图搜索一、概念1、二人零和、全信息、非偶然2、博弈树——双方轮流扩展，是特殊的与/或树责效抛旺刹匆烘寄坠靡弹伤补染鼓连雀讽砚篱葛陇陕尤佬秀微搁嘎赘质谈人工智能与专家系统第三章人工智能与专家系统第三章第五节博弈树图搜索二、特点1、“与〞节点、“或〞节点逐级交替出现2、从我方看，所有敌方的节点都是“与〞节点3、从我方看，所有我方的节点都是“或〞节点4、所有能使我方获胜的终局，其相应的端节点都是可解节点，得分为正所有使敌方获胜的终局，对我方而言，是不可解节点，得分为负5、先走一方的初始状态相应于根节点巍寓葡偶忆技速唁境藻其截鼻认汰详荡慧馏阴忠靴眺迟幕雨毗衰士之婴清人工智