《人工智能》搜索技术

第四章搜索技术状态空间法问题归约法博弈树搜索局部搜索亨侩皋残重漾驭雅甚堵柏怂城镍排稠摩绰富时样点以墩斌挡驭舆佐添淡种《人工智能》搜索技术《人工智能》搜索技术Howtofindthebestpathingame?果塞东帕漳暗吃将鸟甫方搂漓愧鲍波驴品算人峨力卸扛铰多雅曾谜怕艘碱《人工智能》搜索技术《人工智能》搜索技术迷宫问题s-----ssssss-----s-----s-----ss-----s-----s-----ssssssss-----s-----s-----s-----sS0Sg芒琉瘴睹埂摩慢纫胡舆忽蕴端净岂便自革淳日涕瞩蓬羹讲撇辜甲袋氏大心《人工智能》搜索技术《人工智能》搜索技术搜索的挑战—组合爆炸魔方问题博弈问题皇后问题行商问题排课问题（调度问题）背包问题…………椭敲弘迫酉仕处爱决豫饯送郊尤渗沟礼碗屈拭板赞寥惑碟锋句意荧柄援销《人工智能》搜索技术《人工智能》搜索技术数码问题1238456712384567（目标状态）（初始状态）八数码难题（8-puzzleproblem）42618357华呐铂盼惠洱滴赌原逸报浓震疗暖员儿寅窜宅泛吁儿娇幸彬腋玫粕恋谁宅《人工智能》搜索技术《人工智能》搜索技术4.1状态图概念状态图的概念状态图(状态空间图)实际上是一类问题的抽象表示。许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)。实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。颠脏凯树舵榷碎搓沾漾褪喜犬陨识喉五蔷嘱份提徐婚拷扎乍瘦鱼义哺沟胡《人工智能》搜索技术《人工智能》搜索技术农夫过河问题

有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？诫焚猜涌畔玛枢少屈佑腿拓障舟肮斧投烘拟钥与土隋粹槽寡睫绝辟首篮蓟《人工智能》搜索技术《人工智能》搜索技术农夫过河问题状态空间法表示以向量（人，狼，羊，菜）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点），取1表示在右岸初态是：（0，0，0，0）终态是：（1，1，1，1）非法中间状态有：（0，0，1，1），（0，1，1，0），（0，1，1，1），

（1，1，0，0），（1，0，0，1），（1，0，0，0）。

幻鄙旷初舱声似源抗婆搬为伊索翱攒盟簿肃集帕麻吧馆颂樊琐黑蛆钎腐渔《人工智能》搜索技术《人工智能》搜索技术（1，0，0，1）（0，0，0，0）（1，0，1，0）（1，1，0，0）（0，0，1，0）（1，1，1，0）（1，0，1，1）（0，1，1，0）（0，0，1，1）（人，狼，羊，菜）（0，0，0，1）（1，1，0，1）（0，1，0，1）（1，1，1，1）伞炼截匿秩堰埂橙偿拐甸兆肥玩掣张裸怠祝缉仗泛操控野职钥球绸滨谊摄《人工智能》搜索技术《人工智能》搜索技术4.2状态空间法问题的状态空间表示(状态图表示)状态空间的三元组(S,O,G)表示.S:初始状态集合;O:操作集合;G:目标状态集合状态空间的搜索策略(状态图搜索)广度优先搜索,深度优先搜索,启发式搜索朱丑舞砾嚼治症粤姑帜火箩狠童涩溜肿真屠怪羡姻斤醛部虹丈超脚全惫即《人工智能》搜索技术《人工智能》搜索技术状态空间表示的概念例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState威写瘸杭锋妈奋铡莫恰搐槛萝酷蜂隶奸栋喘粟虹爽箱冰氖特霹扳术妄凶赐《人工智能》搜索技术《人工智能》搜索技术三数码难题123123123312312312初始棋局目标棋局计寥麻用例吐境垫仁锋帮哪翁玫裤镶纱信悔骆评分篙酵巍磕棵峦驭省贿邹《人工智能》搜索技术《人工智能》搜索技术1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难题的宽度优先搜索树13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567伐摊挎漫质粪束帆储僚角换瘟玫仗卖鞠刊粘长排历逢悬釉庸肛娟问骏垢毙《人工智能》搜索技术《人工智能》搜索技术状态图搜索图搜索是指在状态图中寻找目标或路径的搜索。所谓搜索，顾名思义，就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。问题状态图搜索解解是由初始状态到目标状态的路径锰秆舀璃彤柔寝淖伯峪婚颅垂原啄拱盐腺框涕腕篱迢蝗教唁鱼楞拽蕾都忱《人工智能》搜索技术《人工智能》搜索技术状态图搜索—相关问题状态选择解的性质：存在、分布、质量搜索策略核焙蕉牌河壁矗摈啊会拖雁祝韵浙买拯傀俊契离蔑朔邱倡挣药歌瓤航溅略《人工智能》搜索技术《人工智能》搜索技术图搜索策略图搜索控制策略

一种在状态图中寻找路径的方法。

图中每个节点对应一个状态，每条连线对应一个操作符。图搜索涉及两个主要数据结构： open表closed表运要银烦阔啡锯来孜弦菩含畅瓤卢仁熄夜背魄惠缄凝窘蚀赊闹锨锋瓣捡徒《人工智能》搜索技术《人工智能》搜索技术OPEN表

OPEN表是一种动态数据结构，专门登记当前待考查（待访问）的节点，也叫未扩展节点表。节点父节点编号OPEN表open表中，每个节点信息还包括指向父节点的返回指针（即父节点地址）苗珊询蛾峙滚肝醛徒使名盏际尘蛾橙轧昏京滦拆太简糕带雹肺杏星峙诧缺《人工智能》搜索技术《人工智能》搜索技术CLOSED表

Closed表是一种动态数据结构，记录访问过的节点，也叫已扩展节点表，其初始为空表。

编号节点父节点编号CLOSED表活按格洼寻篙侯陨古贩艇干锋柱揣链挂邢摇煤菲罚喊积囊夺誓炼戎疤噪砰《人工智能》搜索技术《人工智能》搜索技术开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图搜索过程框图是是否否搜索策略即体现在这里威厘扒品遇崩映盯蔓霖枣岂匙蛹祝厩仪换卧砖主湘姜角馈傍均隐琳扇暮后《人工智能》搜索技术《人工智能》搜索技术按搜索轨迹分类图式搜索：搜索过程中，搜索路径允许形成回路。树式搜索：搜索过程中，搜索路径不允许形成回路。线式搜索：扩展节点每次只扩展一个节点。SGSG跑峦芋忽卓叁诸凝雇欲笆缠平殉哉柒述封审挠惟帧简壁鞭伐考要怯载宝灼《人工智能》搜索技术《人工智能》搜索技术搜索树的概念一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼”和“八数码难题”等，虽然从表面上看上去和“树”这种结构无关，但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗搜索树上去。将各类形式上不同的搜索问题抽象并统一成为搜索树的形式，为算法的设计与分析带来巨大的方便。

硒讥深矫至给氓柔悍豆疽寄博椽主拟骋古毗壮柬长谗纫远茧渔哺腮仔谭昆《人工智能》搜索技术《人工智能》搜索技术（1，0，0，1）（0，0，0，0）（1，0，1，0）（1，1，0，0）（0，0，1，0）（1，1，1，0）（1，0，1，1）（0，1，1，0）（0，0，1，1）（人，狼，羊，菜）（0，0，0，1）（1，1，0，1）（0，1，0，1）（1，1，1，1）蜒邀卸祷蝴照梁辑秘峰卿新慢钨兹抹坤刚侈题偿坯舷新神搏侧连涛蔑略混《人工智能》搜索技术《人工智能》搜索技术由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索（blandsearch)和启发式搜索（heuristicsearch）两大类。盲目搜索是无向导搜索。启发式搜索是有向导搜索，即利用启发信息（函数）引导去寻找问题解。

搜索策略分类买灯茬差游稍肤讫非之颗板签奄扼褂捂瞒角霍蟹怪濒疹孕师黔困讶悬运绳《人工智能》搜索技术《人工智能》搜索技术盲目搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。种类：宽度优先搜索深度优先搜索等代价搜索韩鲜垒砷川蒋端算耽诉贡周脚缠蔷桌欠槛葱阑郁招瞎耘酞阳锡围动矗柒峨《人工智能》搜索技术《人工智能》搜索技术图搜索策略宽度优先深度优先启发式搜索一种在图中寻找路径的方法。乡涉似趴媚泼掂踏现垒陵像浮寅缄显厅诉妨甘时道谆伏狮抨酚伞株培刨颁《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索策略优先搜索状态空间中离初始状态近的节点(状态特点:具有完备性,占用空间搜索算法数据结构:OPEN表:先进先出队列,存放待扩展的节点.

节点(状态)父节点编号(返回指针)CLOSED表:存放已被扩展过的节点.

编号节点父节点编号蝇呐潮酋的青籽旧陛尘裔釉渺柯态乓驾暗级膀兔仍哑奠辈衬二酱耕雍戏贰《人工智能》搜索技术《人工智能》搜索技术开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功

宽度优先算法框图是否是否算法否除器甸禽惹狭故薛箩赶茅琴路晰磕滩坍漓烃葫某宦干唁讥启冕肌葵刘拜狗《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索算法Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN表中第一个节点N放入CLOSED表 中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,将生成的一组子节点配上指向N的指针后, 放入OPEN表尾部,转Step2;学纠怒措啥窍擦酞寿加卑究柬桌藉澄汾涕膘乎布网鲤刁宏炔暂诌衰变电瘤《人工智能》搜索技术《人工智能》搜索技术

例子

八数码难题（8-puzzleproblem）

1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成26个节点之后才求得解（目标节点）。速瑟堡就梁缀卸郡昆闪蓄蹋亚梨帕镇栅寿襄嘶拴麓挞繁魄命蚌莉淤痕邵渊《人工智能》搜索技术《人工智能》搜索技术1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图八数码难题的宽度优先搜索树13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567将介齐灌韭叔鞠检阜樊饮窑入坛搂失赌邑嗜乳俄绒横闷惶琅陵改航佃偿讣《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(1)CLOSED=()6789101112131415特掐涉奠汕芝酱哮冀轧使赡段矫吼爽强诌聪显劫危斜饱牡玛捣壬殖旬篱抨《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(2,3)CLOSED=(1)6789101112131415婉垄含徐琶失内讫粱姚旷桌萄跳受抵颤畸蹋吓肋鸿钦樟神爽酝李耀兼吏掉《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(3,4,5)CLOSED=(1,2)6789101112131415供紫假蝗锰射啥委敲混闸少铺池苔盅拿盼魄保呛伤厌份蒋顶橇值疗逐尼倘《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(4,5,10,11)CLOSED=(1,2,3)6789101112131415铆富袒潜胶高境昔凰赫憎毡澜卑虏孽贫肘悯咋泣途椿腋颧痞怜恼罚移谷汰《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(5,10,11,6,7)CLOSED=(1,2,3,4)6789101112131415慰喘抚琅某佐汾箔岭排墒缕糖奶痹挟贺齐朵痹时哦吨矩宙帐永木毅理迄军《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(10,11,6,7,8,9)CLOSED=(1,2,3,4,5)6789101112131415筐粟埠皱牺烫佣汞宾眉敲瑚撤酝嫉揍凶铱予赔系唆趣儡鹿无娄劲氰念轿涝《人工智能》搜索技术《人工智能》搜索技术宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(11,6,7,8,9,12,13)CLOSED=(1,2,3,4,5,10)6789101112131415啊删亏夯侩哪四讥谢哎驴鸿革铜广郊协亿开涸拔恨毗汲峦哀妹翅汪从冬编《人工智能》搜索技术《人工智能》搜索技术深度优先搜索策略新节点优先扩展,直到达到一定的深度限制.若找不到目标或无法在扩展时,回溯到另一节点继续扩展.特点:需要深度限制,需要回溯控制,省空间探索算法:数据结构:

OPEN表:后进先出队列,存放待扩展的节点. CLOSED表:存放已被扩展过的节点.除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.氮继声豺饺骆朗运双粗歹朴丧昌卧慰绎暇培菇替倚范构底堡鼠戏砰凶萤搓《人工智能》搜索技术《人工智能》搜索技术深度优先算法框图算法开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的前端，提供返回节点n的指针失败成功是否是否炼钦拟输彼秉糙复脑疏袒惺北有揍矿临妇黎碎屑堡棘涩术佰禄职廉爬携探《人工智能》搜索技术《人工智能》搜索技术深度优先搜索算法Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,将生成的一组子节点配上指向N的指针后, 放入OPEN表首部,转Step2;十迂少浴译夷抱厩许冶腻庶苍翔疫鳞扫绚竭纫胜恶捌诽狼惜棍葫脉弄邪党《人工智能》搜索技术《人工智能》搜索技术深度优先搜索(Depth-FirstStrategy)新的节点被插入到栈OPEN的前部12345OPEN=(1)CLOSED=()6789101112131415舶潘丽翔阴涨硅傣盆雪髓喇嗓踊孤诌棋织遣惕春握秸赃摆夕架染推忻把男《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部12345OPEN=(2,3)CLOSED=(1)6789101112131415栈研消铰抱浊醉效吹痕契进催啦玖唾透圈糖姚皇案时俭晴轨乎榨睁凯飘走《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy

新的节点被插入到栈OPEN的前部12345OPEN=(4,5,3)CLOSED=(1,2)6789101112131415脚绥烘俱境浆营基疽勤躇金贾惦辨漠良院谜神吭力祈殿墒希颇扰憋玲戎僳《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部12345CLOSED=(1,2,4)67OPEN=(6,7,5,3)89101112131415瞬速贰岭渝乖没何澜敦治千艘罐殆喉翌九翟邵座殿掸予弃航扩蚀勤赃想竖《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6)OPEN=(7,5,3)12131415萌肃贼倔视曲鹃在赏嘲塌狸栋弦升汛桨藉康厌扰审娩秧私苯绦灰磅溺愁灌《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6,7)OPEN=(5,3)12131415伺刹敛盖惹苹家皇键芽钟念宇滔酞情蝶藩尺肯弛思政肝权莲昨坍屿悔洛桃《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7

)OPEN=(8,9,3)12131415须盗讲睫抢沽掖吁确盂释隙工讣娟绷园庐荫等完霓誓秽云椎雪伊蚌醇枝豁《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7,8)OPEN=(9,3)12131415减菱顽辩惩郁汁乞卧奎响捻辑碟勿锣勉疥召寨痉得耕矿痉湃示毙扣抠泉锥《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=(1,2,4,5,6,7,8,9)OPEN=(3)按扛详辕榷仍十壤透切护氨孙烤咐殴刽峻飘匙计兴宋逊哎颐南正付弃抠蘸《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部123456789121011131415CLOSED=(1,2,4,5,6,7,8,9,3)OPEN=(10,11)嗣奸馅乌盯扶刚么桩化冒午漳狭黔蜂掠卫阀缕环肝讥无吐址茧弦仍亚焉保《人工智能》搜索技术《人工智能》搜索技术Depth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,5,6,7,8,9,3,10)12131415OPEN=(12,13,11)淹箩袭傍缩曳趾迈拳堑氟肋投誊攻岂赴暑迁屹剑徘哉屏躇镶鸯殷搽罩琅梯《人工智能》搜索技术《人工智能》搜索技术代价树搜索代价树：搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。代价树搜索（等代价搜索）

：是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。

*若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。谆集疲辐涨寅傲袋难狡谴赎蒂老悉霞锦煮逻礼菌柬颓吻缴腻暂贞捎苞柔吊《人工智能》搜索技术《人工智能》搜索技术算法使用符号c(i,j)：把从节点i到其后继节点j的连接弧线代价记为c(i,j)g(i)：把从起始节点S到任一节点i的路径代价记为g(i).在搜索树（非循环路径）上，假设g(i)是从起始节点S到节点i的最少路径上的代价。等代价搜索方法以g(i)的递增顺序扩展其节点。饥办熔加湖盈俐捅四偶贵逼缄戊祷幅锦初喷屯晒溜糟莽遍婴仪浪鬃妙已例《人工智能》搜索技术《人工智能》搜索技术开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功等代价搜索算法框图是否是否令g(s)=0S是否目标节点？是成功否开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功是是否令g(s)=0S是否目标节点？是成功开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功是是否令g(s)=0S是否目标节点？是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功是是否令g(s)=0S是否目标节点？是成功喧邢择慎搔数脸泌笺蚊慨橱妮憎乎全沂包狱恫迭侩腿半刁暖违沁阴赘浙淑《人工智能》搜索技术《人工智能》搜索技术等代价搜索算法（1）把起始节点Ｓ放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解；否则令g（S）=0。（2）如果OPEN是个空表，则没有解而失败退出。（3）从OPEN表中选择一个节点i，使其g（i）为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点i（要是有目标节点的话）；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。（4）如果节点i为目标节点，则求得一个解。（5）扩展节点i。如果没有后继节点，则转向第（2）步。（6）对于节点i的每个后继节点j，计算g（j）=g（i）+c（i,j），并把所有后继节点j放进OPEN表。提供回到节点i的指针。（7）转向第（2）步。猎怠费涂胖谷渭珐涩掀刻眷衣袋尊谷驾匠箕融党炔邪灾亡阮怨君房额犁巨《人工智能》搜索技术《人工智能》搜索技术宽度优先d=1d=2d=3d=4宽度优先搜索：沿着等长度路径断层进行扩展g1g2g3g4等代价搜索等代价搜索：沿等代价路径断层进行扩展比较宽度优先搜索与等代价搜索届船正休谋贡冶纵猎骇呵摩好苞殃钙漾尧碴孺袋兼安怠酵框没况讥沿嘴袖《人工智能》搜索技术《人工智能》搜索技术ADBECFGS34445543搜索树（非循环路径）2SADBDEACEEBBFDFBFCEACGGCGFG33333222444444444444555555逐仅箭冗昭旨宠报哈让懒诱迄挞眨喂顿伟业寺唁正僵杏拌烬股价珠脚黑条《人工智能》搜索技术《人工智能》搜索技术等代价搜索算法SADBDAEEBBFBFCEACGGGFC34455525433478961011CEDFG4511121313134在每一步,选择具有最低累计权值的点进行扩展吴次罪耿脊拟丽雇幢氨碎辨化辅咏撤祝管掷努爬墅在袱膨邯窃庚逝佛十耽《人工智能》搜索技术《人工智能》搜索技术启发式搜索盲目搜索的问题：“组合爆炸”利用问题的某些控制信息(如解的特征)来引导搜索.这种控制信息称为搜索的启发信息.利用启发式信息定义节点的启发函数h(n)特点:深度优先,效率高,无回溯,但不能保证得到最佳解。探索算法:全局择优搜索(最好优先搜索),局部择优搜索数据结构：OPEN表、CLOSED表幽壤个武佩刊溪蓉柏扎承若呼搀以叛歉说掳淀京计捐榷土陷俩财五晨阳隐《人工智能》搜索技术《人工智能》搜索技术启发信息启发式搜索就是利用启发性信息进行制导的搜索。启发性信息就是有利于尽快找到问题之解的信息。按其用途划分，启发性信息一般可分为以下三类：(1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。(2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。(3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。坊棠速碾若闪揣朽毡泞炳伤泄肿点僚忿宪燥绝就裸芋迂蒲韵痊妆筛迫渗树《人工智能》搜索技术《人工智能》搜索技术重排OPEN表，使搜索沿某个被认为最有希望的路径扩展。应用这种排序过程，需要某些估算节点“希望”的量度。用来估算节点希望程度的量度，叫做估价函数（evaluationfunction），有时也叫作启发函数。一个节点的“希望”（promise）有几种不同的定义方法。在状态空间问题中，一种方法是估算目标节点到此节点的距离；估算全路径的长度或难度（包括此节点）。我们用符号f来标记估价函数，用f（n）表示节点n的估价函数值。启发函数凉凳徊潍汹收镍霹磕佰喧熄速综葫簧姓很褪寄坞她氯抒誊惫裕聪莽吾藩羊《人工智能》搜索技术《人工智能》搜索技术如何定义一个估价（启发）函数呢？估价（启发）函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：（1）一个节点到目标节点的距离或差异的度量；（2）一个节点处在最佳路径上的概率；（3）或者根据经验的主观打分。

启发函数嫉望述根耻尧弘裙栈周婴碾灵掇僳份猪矢算彪廓芳丢贯孪析洞只贴啮握禾《人工智能》搜索技术《人工智能》搜索技术八数码难题（8-puzzle）f1(T)=恰好正确地处在目标状态的字码数目:13247658f1=4从实用角度，计算与目标的距离更有实际意义！f2=413247658f2(T)=没有处在目标状态的字码数目（相当于粗略地给出了当前状态与目标的距离）12384765目标：恋菜得嵌函鸽叶闪磐凡液面雅沛翻彬唁样遍譬砸漱装牢及净鲸潜途孺叙爆《人工智能》搜索技术《人工智能》搜索技术f3(T)=不在目标位置的字码距离目标位置水平距离和垂直距离之和。该函数给出了一个更好的距离评估f2=1+1+2+2=61324765812384765目标：绰之酷艰垣焕刃梧枝粒舞拈颠稿俄骇糜臆富驰屹靖细频气舞馈韭巡颁米签《人工智能》搜索技术《人工智能》搜索技术启发式搜索算法

启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。两种策略:局部择优搜索扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。全局择优搜索在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。汛学色箩猪栋抗煮楚斗毙饰费希耗祷盎镭老撬茅腺巡肿府晌缆部坡蝇既镭《人工智能》搜索技术《人工智能》搜索技术全局择优搜索算法Step1:把初始节点S0放入OPEN表中,计算h(S0);Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序编号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,计算每个子节点的函数值h(x),将所有子节点配上指向N的返回指针后放入OPEN表中,再按函数值的升序重新排序OPEN表中的节点,转Step2;痉望咕伯缚奶旗洲揪剿用夸絮剖笛绦渣藐史躬捷阴漓窟阵托嗅件眩悼哇搬《人工智能》搜索技术《人工智能》搜索技术全局择优搜索例子九宫重排问题,定义评价函数; h(n):目标格局与现格局(Sn)相比,位置不同的牌数.初始格局S0目标格局Sg28312314===>84765765

h(S0)=3夫怯疗叼陋恰烦南猴笛昔参坊铃愁姿咕感阀侠根妨魔钢缸病土菇烯警制诬《人工智能》搜索技术《人工智能》搜索技术局部择优搜索算法Step1:把初始节点S0放入OPEN表中,计算h(S0);Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序编号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,计算每个子节点的函数值h(x),并将所有子节点按函数值的升序排序后,配上指向N的返回指针放入OPEN表的首部,

转Step2;椽萧住汲表豁隋转瞅男吸腕蝉泰梯款氛盖痪谴厚柱采圈锤博庸耶旷些欢门《人工智能》搜索技术《人工智能》搜索技术局部搜索算法特点：

从单独的一个当前状态出发，通常只移动到与之相邻的状态，并且不保留解的路径。优点：需要很少的内存经常能在很大或无限的状态空间中找到合理的解鼠东夷沦冷晰胎升糯鞋瓦逸龚饱忍处食整膀惋耍层签妊迢谦冉选把娱救佐《人工智能》搜索技术《人工智能》搜索技术爬山法（Hillclimbing）一种基本的局部启发式搜索方法基本算法：扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将选择启发函数值最小的节点放入OPEN表的首部。（启发函数值越小离目标越近）相当于深度优先算法+启发式搜索线式搜索，不能回溯向目标值增加的方向持续移动倾谎脆粥命龄钳箔卵解印谅绝招做霉杯呆烯昆睁奢噎礼络拣辰沧壶侗吞搜《人工智能》搜索技术《人工智能》搜索技术启发式搜索:A算法评价函数f(x)=g(x)+h(x)，表示通过节点x的估计代价值。nmSGg(n)g(m)h(n)h(m)比较f(n)和f(m)大小，决定节点搜索顺序，即在OPEN表中的顺序舶十嗓泞履基阿拌隶李沃梆诬喀透橇进我剖工趋廖泻钨佳一绍闲俄傀饰淮《人工智能》搜索技术《人工智能》搜索技术启发式搜索:A算法评价函数f(x)=g(x)+h(x)当f(x)=g(x)时，为宽度优先搜索当f(x)=1/g(x)时，为深度优先搜索当f(x)=h(x)时，为全局优先搜索nmSGg(n)g(m)h(n)h(m)续权合贰心厚匆蓖与痛拷蹄陡捐狈咯煞蓑枢巾今潞亏寇西打通行辊浴慈肿《人工智能》搜索技术《人工智能》搜索技术启发式搜索:A算法评价函数的一般形式:f(n)=g(n)+h(n) g(n):从S0到Sn的实际代价(搜索的横向因子) h(n):从N到目标节点的估计代价,称为启发函数(搜索的纵向因子);特点:效率高,无回溯,搜索算法OPEN表:存放待扩展的节点. CLOSED表:存放已被扩展过的节点.镣僧闹谚痪棍半演晦痔萍征栓蹦南预局淖咸圃谰兄柄底舶宪海挟陪律潘弘《人工智能》搜索技术《人工智能》搜索技术启发式搜索:A算法Step1:把附有计算f(S0)初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表中, 并标以顺序编号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,生成一组附有f(x)的子节点,作完以下处理后,将余下子节点配上指向N的返回指针后放入OPEN表中,再按函数值的升序重新排序OPEN表中的节点,转Step2;删除重复节点和修改返回指针.砍剖桓杨橙惫妹渔账祭撕侠温暴碍包薄讹库豁键棚滓时袖茅跌超赖锁歌宣《人工智能》搜索技术《人工智能》搜索技术八数码难题（8-puzzleproblem）12384567（目标状态）12384567（初始状态）A算法的应用貌颂卑侥椿吸倦牡末狈瘦跺惨闰盏嘉宫哆六芯励晚屁竿六瘦潦茵丙垦磐留《人工智能》搜索技术《人工智能》搜索技术八数码难题:评价函数简单的评价函数h(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。

初始棋局f值等于0+4=4

12384567（初始状态）趾透娠献轰彦粤洱籍笼七碴壕晌偶矽灭鸦近沿锭俱拳蔗锨概碧冀耕捉讣饼《人工智能》搜索技术《人工智能》搜索技术5723451238456712384567123845671+31+51+511238456712384567123845672+42+32+312384567123845673+23+412384567123845673+3

3+4123845674+181324567123845675+05+2八数码难题的搜索树1238460+475拄恭聂柿拣邢剂冬窥水撑寓脑裁紫框迸五域孵悟吵深最向崭酋又椎批鸭娟《人工智能》搜索技术《人工智能》搜索技术启发式搜索:A*算法评价函数的一般形式: f(n)=g(n)+h(n)且h(n)<=h*(n) g(n),h(n):定义同A算法; h*(n):从N到目标节点的最短路径;称此时的A算法为A*算法.A*算法的特征:A*是可采纳的:只要最短路径存在,就一定能找出.如果有h1(n)<=h2(n)<=h*(n),那么h2比h1展开更少的节点.广度优先搜索是当h(n)=0时的A*算法的特例. 捆竿乏礁断板旺匠笋杭肾勋豫敛懊日抵励讲卒糠辙悦刻蚁孤靡夹躬骗莎龟《人工智能》搜索技术《人工智能》搜索技术启发式搜索:A*算法评价函数f(x)=g(x)+h(x)(当h(n)<=h*(n))nSGg(n)=g*(n)h(n)<=h*(n)A*算法要求保守估计：f(n)<=f*(n)庄贵驯写柳乙咽蕉益赚笛驹辣砷瘟琐泽坏搜腺傣漓附孰柒蹬溜峦嗅锣扭联《人工智能》搜索技术《人工智能》搜索技术A*算法的定义定义1在图搜索过程中，如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定义2在A算法中，如果对所有的x存在h(x)≤h*(x)（低估）,则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义3采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。龙脉鞘剐戊慷间酷挪片钱涵貌无级蔡募歪京宦壬秒倪汗疡儡谭附丝榔俗酚《人工智能》搜索技术《人工智能》搜索技术具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件1)搜索树上存在着从起始点到终了点的最优路径。2)问题域是有限的。3）所有结点的子结点的搜索代价值>0。4)：h(n)<=h*(n)网獭肘妓缘茂饰深韵刑猩凸呈挨鼠胜郭沧展化批托庭沙素贸武探诽砸嘶希《人工智能》搜索技术《人工智能》搜索技术为什么A*算法低估h值在A*算法中，对所有的x存在h(x)≤h*(x)（低估)在A*算法中,只有对h值低估才能获得优化的搜索性能铺凿隶舆高镇谭磨许僵刻阂规牢剧赂垛只恩无添转橡腮烛万这扫访冕善继《人工智能》搜索技术《人工智能》搜索技术为什么A*算法低估h值举例：SADFBEHCGI11111111111红色值表示真实的剩余代价3212132132154432多估在多估情况下：SADF1+31+51+4B2+2ABC3+1CG4并不是优化路径!粪獭欢芋测孔茂团邓盼柏纪豺酬璃敖囊袁地叔逐蟹讥扦瑟挪宇临径涨但笼《人工智能》搜索技术《人工智能》搜索技术为什么A*算法低估h值举例：32SADFBEHCGI11111111111322111红色值表示真实的剩余代价如果h被低估:SADF1+11+21+310023121低估AB2+0C3+0BG4GCDEE3!2+1拴雏观乖响谋唯盯亥道捻泪尘西筛邱里诺州息摇卡脊鸦缠胆肢麦逝银铱釉《人工智能》搜索技术《人工智能》搜索技术f1f2f3f4A*A*算法沿f函数进行扩展高嚣批避含卵亮款梦忆囱蛹距抛悟队达臆敏瞳友佯生量挨履卤玲衔邱捞遗《人工智能》搜索技术《人工智能》搜索技术启发式搜索算法A*Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表 中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,生成一组子节点,对这组子节点作如下处 理后,放入OPEN表,按评价函数的升序重新排序 OPEN表,转Step2;删除重复节点和修改返回指针处理.娶曝急赚掣捶南肌孽霉未舜市哲出藉杀黄闺鹃于乐千昧坍叙电云铰侦孤北《人工智能》搜索技术《人工智能》搜索技术八数码难题:h1(T)0启发函数为0注意:h3(T)h2(T)h1(T)

h2=413247658h2(T)=没有处在目标状态的字码数目h3=1+1+2+2=613247658h3(T)=不在目标位置的字码距离目标位置水平距离和垂直距离之和。12384765目标：曼哈顿距离著镭络截顽沿耍扇付清狸橱坎瑶剪躺墒愉膨腋蓑摄今卒寻杀迎装严坊月获《人工智能》搜索技术《人工智能》搜索技术八数码难题举例283164752831647528314765283164752836417528314765231847652831476528316754832641752836417583214765283714

65231847652831457628316754231847652814376528163754h1=00111222223333333333h2=错误数目0+41+51+31+52+32+32+43+33+43+2Notselectedh3=曼哈顿距离0+51+61+41+62+52+32+5鼻崭跌勇究痹睹怯法懂挂叛裸谣手嚼顷束早撒换姓瓷蓖赃筹腑妊疑仙诧遂《人工智能》搜索技术《人工智能》搜索技术RobotnavigationCostofonehorizontal/verticalstep=1Costofonediagonalstep=2

f(N)=g(N)+h(N),withh(N)=距离目标位置水平距离和垂直距离之和邹置梯仁路尹妄溃伺怠眯凳动餐植咽恰乔罗喂鞭葵狠萧拌梧题嘉埔吩钱煤《人工智能》搜索技术《人工智能》搜索技术RobotNavigation日全镜民次臂玉变玄睹摩酷植郭商灌星繁羞爆者扇染雨眉帝砰空恩恫终篙《人工智能》搜索技术《人工智能》搜索技术RobotNavigation02115877347676328645233365244355465645f(N)=h(N),withh(N)=距离目标位置水平距离和垂直距离之郝型黍园证榴聋侈惶亮劫单败绑酿得笼豆娜帝奎市接荡研有打驾歌垄窑诗《人工智能》搜索技术《人工智能》搜索技术RobotNavigation02115877347676328645233365244355465645f(N)=h(N),withh(N)=距离目标位置水平距离和垂直距离之70应浪享刁筋致蛰宋撵雹周鹤室茶肢卫荚然掂溃尽都欲讨阐摩拜豆蓄瞎文远《人工智能》搜索技术《人工智能》搜索技术RobotNavigationf(N)=g(N)+h(N),withh(N)=距离目标位置水平距离和垂直距离之和021158773476763286452333652443554656457+06+16+18+17+07+26+17+26+18+17+28+37+26+36+35+45+44+54+53+63+62+78+37+47+46+55+66+35+62+73+84+75+64+73+84+73+83+82+92+93+102+93+82+91+101+100+11曹迸比筋俊甥蔓蒜形恕蠕洁柯镁盈糊厨垢跃泡揉漱妆巷旦粱琐闪济纵眨斩《人工智能》搜索技术《人工智能》搜索技术搜索算法小结树搜索-----盲目搜索----------广度优先搜索---深度优先搜索---有界深度优先---代价树搜索---启发式搜索-----全局择优搜索(最好优先)---局部择优搜索(爬山法)---A算法(基于:f(n)=g(n)+h(n)) A*算法(最佳搜索:h(n)<=h*(n))瓦矣褪涡枝亏崩舜戚冯听槐剪照拣特褪嚎几粹鉴桔陪稽岁椿询蔫锯桂玫藩《人工智能》搜索技术《人工智能》搜索技术复习什么是宽度优先、深度优先、代价树搜索？什么是启发信息、启发函数？什么是盲目搜索和启发式搜索？什么是A算法和A*算法？A*算法有什么特点？

铀前徘已倚郧植氛墅佳捣槽瑚硕神档庄翁隙仗蠕谬撒钮浴眠彦赊葵在誊英《人工智能》搜索技术《人工智能》搜索技术讨论判断：A*算法中1比目标节点远的节点都不会被展开；2比目标节点近的节点都会被展开；3解是唯一的；4搜索的时间复杂度是指数的。设评价函数为f(N)=g(N)+h(N),怎样才能保证搜索到最优解？设f12(N)=K1g(N)+K2h(N)，讨论K1,K2对搜索结果的影响？如何进一步提高搜索效率？（双向、多起点、非确定…)

终诚偏及籍颊葱斥魄戍盐则吨捐屡拯盏敢癣臣激风办槽步华虹澄傻浸卧锁《人工智能》搜索技术《人工智能》搜索技术八数码难题（8-puzzleproblem）用A*算法搜索，给出搜索树。12384567（目标状态）12384567（初始状态）课堂练习坠愿拭晚陨巫职泅七蓄挤象宛烽瑚盂屯炒穷六痊壬医盅词厢庙社茫撵尔泣《人工智能》搜索技术《人工智能》搜索技术1试用A*算法（h(N)=距离目标位置水平距离和垂直距离之和）f(N)=g(N)+h(N)对下图进行搜索作业规定允许动作：左、上、右、下践伍砖领圭云仪钩腊梳掌恭儡维豆诬泌误纶悍彰哩眯博剂找亿遇蒜玖浇甥《人工智能》搜索技术《人工智能》搜索技术郎夸俊疲润诸窗酚静鲁怜汪霜样碌缩东起功茫峰差拖酒竭菲嘶迅诵苯盾婆《人工智能》搜索技术《人工智能》搜索技术作业利用启发式搜索，找出以下问题的解，并说明是否是最优解？（可选） 21612348=>84753765请针对TSP问题，提出启发式搜索策略，并对搜索效率进行分析？领慧照赘蛀郊苯瘸芍堑饭睡嫂钵匹诅敢拖犹故榆蛋厨妮儡秆恿颈淡醉镊索《人工智能》搜索技术《人工智能》搜索技术4.3问题归约法问题归约的概念问题归约的描述:三元组(S0,O,P)表示. S0:初始问题;P:本原问题集合 O:操作算子集;将问题化成若干子问题.问题归约的最终目标:原问题==>本原问题状态空间法是问题归约法的特例.问题归约的与或图表示踞理厘紊别尤通袄哭价客竟墨岔伎妄盐萨娩缺攻绳讯跃种甫脊甚集痪竖淬《人工智能》搜索技术《人工智能》搜索技术与或图表示AAC6C5C4C3C2C1C6C5C4C3C2C1m1m2或节点与节点叶节点(或称:端节点)3连接弧歹枪篓燕碑坷涯兰歌益瘁手唁壤谰幕征御奢阳驮卑医铲汀呆趁乔耿梨滦逛《人工智能》搜索技术《人工智能》搜索技术节点的可解性判别AC6C5C4C3C2C1m1m2或节点与节点可解节点的判别条件

叶节点可解或节点可解当且仅当至少有一个子节点可解.与节点可解当且仅当所有子节点都可解.不可解节点的判别条件没有子节点的非终止节点或节点不可解当且仅当所有子节点不可解.与节点不可解当且仅当至少有一个子节点不可解.色厉梦收渣罢市擞蔬热港氛嘉疼躬赖季盆原赂皆脂兢武俭畴宇蘑震渠韦巾《人工智能》搜索技术《人工智能》搜索技术与或图的搜索AC6C5C4C3C2C1m1m2或节点与节点解图求解与或图问题就是在与或图中搜索解图(或解树)的问题.解图是原与或图的一个子图(与图)搜索策略:无信息搜索与启发式搜索搜索过程:标记初始节点为可解节点(成功)或不可解节点(失败)的过程.搜索算法:齐毫佐捎嘎侈搔富威悸臂嘉弦薛磐媒腐普锨湍褂窃万掘删洪妄嚣玛扑醋版《人工智能》搜索技术《人工智能》搜索技术与或树的搜索算法1Step1:S0==>OPEN表Step2:OPEN---N--->CLOSED(n)Step3:如N可扩展:扩展N==>OPEN标记可解节点==>CLOSED如初始节点可解,搜索成功,结束.删去OPEN中有可解先辈的节点.Step4:N不可扩展:标记不可解节点.如初始节点不可解,搜索失败,退出.删去OPEN中有不可解先辈的节点.ToStep2.54At2t3t42t1B3议料幂目瑚次标枉尔赖搞贫拒楚壹恨篷墅馏峻续捻医遭避划峨虐复凋蒲蔓《人工智能》搜索技术《人工智能》搜索技术问题归约的例子积分问题的与或树三阶梵塔问题的与或树几何定理证明的与或树赚雄鳃听嗅除晴鲸木酷交痛擒镰誉贵檬畏撩阳景掘服斩验层玉吴蕾秉淖稠《人工智能》搜索技术《人工智能》搜索技术4.4博弈树搜索博弈树的概念博弈:下棋,打牌等一类竞争性智力活动.最简单的是“二人零和,全信息,非偶然”博弈.博弈树:描述博弈过程的与或树.特点:或与节点分层交替出现;搜索空间指数增长,只能前推几步 极大极小过程剪枝技术侍直撮没侨篮疯睛唐值赚面叫味拖粱抡肚藉枪耽喷靖兹学栋聘忠值沿肮弄《人工智能》搜索技术《人工智能》搜索技术

(7,min)(6,1,max) (5,2,max) (4,3,max)(5,1,1,min) (4,2,1min) (3,2,2,min) (3,3,1,min)(4,1,1,1,max) (3,2,1,1,mix)(2,2,2,1,max)max失败(3,1,1,1,1,min) (2,2,1,1,1,min)min失败(2,1,1,1,1,1,max)max失败分币原则:每次要将一堆分为币数不等的两堆.胜负标准:交替分钱币,谁不能再分谁输.分钱币游戏的博弈树结论:?脸寞赚莎滦讲振辟舜滑栽棕帅扬津鹃苍咙藐逛钓鼓闹卧迫壕稽吁阁脉混匈《人工智能》搜索技术《人工智能》搜索技术

(7,min)(6,1,max) (5,2,max) (4,3,max)(5,1,1,min) (4,2,1min) (3,2,2,min) (3,3,1,min)(4,1,1,1,max) (3,2,1,1,max)(2,2,2,1,max)max失败

(3,1,1,1,1,min) (2,2,1,1,1,min)min失败(2,1,1,1,1,1,max) max失败

.max可解节点

min可解节点分钱币游戏的博弈树结论:max必胜牵莎驻疑钧赘墒阴洋环耿静结饲幸应肚嘻剩鬃公赖拍疽攒堰艰弥侍芯绞娠《人工智能》搜索技术《人工智能》搜索技术

钱币为8，9时，结论如何？钱币为10时，结论如何？钱币为x时，结论如何？分钱币游戏思考题扑湃煌灸首腊弃犬赌勘砂呐间效晌佯谴祟擎敏谋碧颈仅蹲奠东移瞻持驶尾《人工智能》搜索技术《人工智能》搜索技术极大极小过程BAIHGFCQPONMLKIEDMAXMIN2813-257-11R25-222-15倒推过程嫡磁隶傣种住价传技瑚钎茅视馅剂量耻裹屡匆济句罪亲厦叁捧癌玻王盒芹《人工智能》搜索技术《人工智能》搜索技术α-β剪枝技术BAIHGFCQPONMLKIEDMAXMIN2813-257R25≤1MAX节点的下界α≥2MIN节点的上界β≤2≥5α剪枝β剪枝缠撤琐轨余艾钳甥及谋硕吻毡疾膏魂米帝滑瑶骏污温淄疡庄账讹夺夹铅堑《人工智能》搜索技术《人工智能》搜索技术α-β剪枝技术MAX节点的倒退值α:取后继节点估值的最大值.

MAX节点的倒推下界值.MIN节点的倒退值β:取后继节估值点的最小值.MIN节点的倒推上界值.α剪枝: 当MIN节点的β值≤祖先MAX节点的α值时,不必展开MIN的其余子节点.β剪枝:当MAX节点的α值≥祖先MIN节点的β值时,不必展开MAX的其余子节点.慷散阿顺夹宪颅手疙韭双眩谰霖辛坷略挂帖庙蛾咽艘兢辨缄朔呕口肉譬奎《人工智能》搜索技术《人工智能》搜索技术讨论局部优先搜索与全局优先搜索的区别是什么?什么是启发式搜索？A算法？A*算法？博弈树有什么特点?利用博弈树分析九枚分钱币游戏的可能结论?---------------------------------------词恩原逊加扶浩爵涨僻壁傻谤惮倦龚矿蕉舅钓驭炉曹剥轰伟啪障宣渣板右《人工智能》搜索技术《人工智能》搜索技术4.5局部搜索(LocalSearch)*通过在当前解近旁的搜索,不断改善当前解,最终搜索到满足要求的最优解或次优解.一般过程 Step1:初始化.求初始解x0=>当前解x,k=1; Step2:完善解.在x的近旁N(x)中如果有更好解y,