第二章 搜索(1)—基于状态空间的搜索

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,用以搜索状态空间的结构与策略,第二章 -,*,第 二章,用以搜索状态空间的结构与策略,怕窟幢漂垫泼编蛋揭氟尺耿案车纵揍亥邵壳擞当努穗廓搁褒筋膀绰沈忱诽第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,内容,2.0 简介,2.1 图论,2.2 问题状态空间的表示,2.3 状态空间搜索的方向,2.4 一般图搜索,2.5 常见的盲目式搜索技术,参亿隘新硷媒酋言沥经续裳垒海戍故涟氢溶扫翱铜汲宣翟灭纲串崖嘎与四第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,2,2.0 简介,什么是问题？,2,8,3,7,10,5,14,1,15,9,6,4,11,14,12,1,2,3,4,8,7,6,5,9,10,11,12,15,14,13,?,勿待币硒堰婿但蕉妖壮塔可辫膜雾领哀抉耸测皑颠蔼廷鼻鲍近祥玲旨辨叮第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,3,2.0 简介,问题,（现代认知心理学）：,在给定信息和目标状态之间有某些障碍需要加以克服的情境。,给定：有关问题条件的描述，即问题的起始状态；,目标：有关构成问题结论的描述，即问题的目标状态；,障碍：无法直接到达目标，必须通过一定的思维活动才,能找到答案，达到目标状态。,问题解决（信息加工观点）：,就是搜索问题空间，寻找一条从起始状态通向目标状态的通路，或使用算子使起始状态逐步过渡到目标状态。,按解决问题所需的领域特有知识的多寡，,问题求解系统,可,以划分为两大类：,知识贫乏系统：依靠,搜索技术,去解决问题。,知识丰富系统：依靠,推理,的识别技术解决问题。,浮鸳屯婆约纲义励蔽琢慰拢毁俐瞄屎垣痢愤赫肄乏尾糟孩河碗乎企席舱盈第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,4,2.0 简介,搜索,人工智能所研究的对象大多是属于,结构不良,或非结构化的问题。,对于这些问题，一般很难获得其全部信息，更没有现成的算法可供求解使用。,只能依靠经验，利用已有知识逐步摸索求解。,根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程,搜索,。,对那些结构性能较好，理论上有算法可依的问题，如果问题或算法的复杂性较高（如按指数形式增长），由于受计算机在时间和空间上的限制，也无法付诸实用。,组合爆炸,问题。,蝗坡拦捕盈舒南盔表咏飘驼撂困愤咖穷双幽躇谤尼匪憎捍阅施辑恕扎摇捕第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,5,2.0 简介,搜索的分类,根据搜索过程是否使用启发式信息,盲目搜索,：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，因此这种搜索具有盲目性。,启发式搜索,：搜索过程中加入与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。,根据问题的表示方式,状态空间搜索,：基于问题到,状态空间,表示求解问题所进,行的搜索。,与或树搜索,：,基于问题的,与或树,表示利用问题归约,法来求解问题时所进行的搜索。,第六章,呜垛泻边往卉搔峻盼宵危牢恼留颅场蛹召坏础斗慑相嫩慎烂辅洛粪陡询纲第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,6,内容,2.0 简介,2.1 图论,2.2 问题状态空间的表示,2.3 状态空间搜索的方向,2.4 一般图搜索,2.5 常见的盲目式搜索技术,铅仪辑枕炕聪费反呀荧缕柜菜夜阑返擅殴狡漱揉蛮纶志丁呢宰猿选抉哼揩第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,7,2.1 图论,例1：,从某王姓家族的四代中找王A的后代且其寿命为X的人,王A：寿命47，有儿子王B1、王B3、王B2,王B1：寿命77，有儿子王C1、王C2,王B3：寿命52，有儿子王D1,王B2：寿命65，有儿子王E1、王E2,王F1：寿命32,王G1：寿命96,王C2：寿命87，有儿子王F1,王D1：寿命77，没有儿子,王E1：寿命57，有儿子王G1,王E2：寿命92，有儿子王H1,王C1：寿命27，没有儿子,王H1：寿命51,萨绥蝗吐甘默灯邯蒜屯沫努矣辆蝇媒韦溜寞鲤货冀画委揉旅焉上空隅秩陋第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,8,2.1 图论,例1：,从某王姓家族的四代中找王A的后代且其寿命为X的人,审朴托申蕊作准酬葡秃痰脉筷缉挎谱儡宇炭蓉三他潘托辅肚疡飞擂碟吩框第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,9,2.1 图论,例2：哥尼斯堡七桥问题（瑞士数学家-欧拉）,沾惊秩纫霍汾蟹唁霞说尸驴岿六哼荫恋京芜烦缠躇工税捅粥透另亭蹋综黑第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,10,2.1 图论,图,节点和连接这些节点的弧的集合。,带标签的有向图,袄焚渔斋聪跺庇陈夯俯瞬挡斡炬织盖释增舀箕跪贫充铣章吴掳燥羹牙看耳第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,11,2.1 图论,有根图,具有一个唯一节点（根），从这个节点到图中所有节点都存在一条路径。,绘舱缺貌壮绎弱偿伟腺垦中譬舔葫娶腾章实情易谭缉附躁堑涝畦显耙萝榨第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,12,2.1 图论,树,两个节点之间最多有一条路径的图。,丘础皱吭牵晚袖诽忧滞厩劝膊偏弗欢赊仕殖颈郡赡墟乍居师侍吮国骤豆揭第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,13,内容,2.0 简介,2.1 图论,2.2 问题状态空间的表示,2.3 状态空间搜索的方向,2.4 一般图搜索,2.5 常见的盲目式搜索技术,踩脂戎封捆闯磨喉幢忠眠啤贬速窒棕仅爆族噎北尺段罐癸甩组呐饮橱幼枉第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,14,2.2 问题状态空间的表示,状态空间表示法,用来表示问题及其搜索过程的一种形式化方法。,状态,操作,状态空间, 什么是状态？,状态（State）是表示问题求解过程中每一步问题状况的数据结构：,S,k,S,k0,，S,k1,，,对每一个分量给予确定的值时，得到一个具体的状态。,任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。,托栋茬绵查部味揪剐梧婪撇治涪关杯太式崎摆秉磅棵馈容妮霓聪正缸盼撂第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,15,2.2 问题状态空间的表示, 什么是操作？,操作（Operator）,算符,当对一个问题状态使用某个可用操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。,操作可以是一个机械步骤、一个运算、一条规则或一个过程。,操作可理解为状态集合上的一个函数，它描述了状态之间的关系。,State1,State2,Operator,往绒钎屯寞缮罐腺炒蕾材丧庄咀粕痴庞端顽猎预盗扁杭汾镁诧棵甲嗜税鸳第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,16,2.2 问题状态空间的表示, 什么是状态空间？,状态空间（State space）用来描述一个问题的全部状态以及这些状态之间的相互关系。,状态空间常用一个三元组表示：,（S，F，G）,S：为问题的所有初始状态的集合；,F：为操作的集合；,G：为目标状态的集合。,Initial,State,Medium,State1,Medium,State2,Target,State,问题求解过程实际上是一个搜索过程,厂逾牧铱向蹋够敖鸳窥砧免店蛋场益胆蝴险巷伟懦得耽泼能嘻稻瞥棋糕龟第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,17,2.2 问题状态空间的表示,【例2.1】二阶Hanoi问题,设有三根钢针，它们的编号分别是1号、2号和3号;,在初始情况下，l号钢针上穿有A、B两个金片;,A比B小，A位于B的上面;,要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。,如何将A、B两个金片移到2号或三号钢针上面？,B,A,1,2,3,B,A,1,2,3,1,2,3,B,A,胞辕唉昧徽烽菇脐尸蠕枚直整抠唉搔早繁曼靶野降温澈砷波骋魂揍甫属径第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,18,2.2 问题状态空间的表示,解,：, 状态：Sk=Sk0， Sk1,Sk0表示金片A所在的钢针号；,Sk1表示金片B所在的钢针号。,全部可能的问题状态共有以下9种：,S0=( 1, l) S1=( 1, 2) S2=( 1, 3) S3=( 2, 1),S4=( 2, 2),S5=( 2, 3) S6=( 3, 1) S7=( 3, 2),S8=( 3, 3),目标：GS4,S8,B,A,1,2,3,S0=(1, 1),1,2,3,B,A,S8=(3, 3),B,A,S4=(2, 2),1,2,3,援盐磁监椽牙予镭蝇椎滓峙虑锋晰腰蝎慧呢斗缕筑所苑价对袁好诽般缸员第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,19,2.2 问题状态空间的表示, 操作,A(i,j)表示把金片A从第i号钢针移到j号钢针上；,B(i,j)表示把金片B从第i号钢针移到j号钢针上；,所有的操作共有12种：,B,A,1,2,3,S0=(1, 1),1,2,3,B,A,S8=(3, 3),B,A,S4=(2, 2),1,2,3,A(1, 3) A(3, 1) A(2, 1),A(1, 2) A(3, 2) A(2, 3),B(1, 3) B(3, 1) B(2, 1),B(1, 2) B(3, 2) B(2, 3),候砰码臣宙巫屈萄您拉霞册银隶撬彬秒晚垃窝鹏潜距未蜗腹蛾葵叙杂荆萄第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,20,2.2 问题状态空间的表示, 状态空间,9种状态、12种操作，得到二阶梵塔问题的状态空间图,A(1, 3),B(1, 2),A(3, 2),(1, 1),(2, 1),(2, 3),(3, 3),(1, 3),(1, 2),(2, 2),(3, 2),(3, 1),B(1,3),条踌刽茨孵囚挑讲抖花归蹄胯白阜兑锭绿汽烛款彻沸壶逆楷蛙葫放劳右而第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,21,2.2 问题状态空间的表示,B,A,1,2,3,S0=(1, 1),B,A,1,2,3,S0=(3, 1),B,A,1,2,3,S0=(3, 2),B,A,1,2,3,S0=(2, 2),A(1, 3),B(1, 2),A(3, 2),艇剔莉炔荷松怂聂抹餐窑嫌幸翰葡最僧默腺妮挡医诊烘已猪裸层槐氧壬设第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,22,2.2 问题状态空间的表示,【例2.2】猴子摘香蕉问题。,a c b,令嫌掌傣迫洁肺屈阂激虐砾稠奄乌扁篇椰蹭型昆攻酒澎求扫促够里卢菩耳第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,23,2.2 问题状态空间的表示,解：, 状态：用4元组(w,x,y,z)来表示。,w：表示猴子的水平位置，, a, b, c ;,x：表示箱子的水平位置，, a, b, c ;,y：表示猴子是否在箱子上，, 0, 1 ；,z：表示猴子是否拿到香蕉，, 0, 1 ；,初始和目标状态为：,S0：,( a，b，0，0 ),初始状态,S3:,( c，c， l，1 ),目标状态,枯胆韧栽甜上章青护绑做曲邑潭衡怎踊输核帆吱净宙晶宏岩没着脖福吾虎第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,24,2.2 问题状态空间的表示, 操作,Goto(u),猴子走到位置u，即,( w，x，0，0 ) ( u，x ，0，0 ),Pushbox(v),猴子推着箱子到水平位置v，即 ( x,x,0,0 )( v,v,0,0 ),Climbbox,猴子爬上箱子，即( x，x，0，0 ) ( x，x，1，0 ),Grasp,猴子拿到香蕉，即 ( c，c，1，0 ) ( c，c，1，1 ),斟容笋李仰怎墙篆馆滞夷磊脊施汞净狭礁点科尽俗鲸需抚犀添墩箭饺缚氢第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,25,2.2 问题状态空间的表示,(a, b, 0, 0),(u, b, 0, 0),(v, v, 0, 0),(b, b, 1, 0),(v, v, 1, 0),(u, v, 0, 0),(c, c, 1, 1),Goto(u),Climbbox,Pushbox(v),Goto(u),Pushbox(v),Goto(u),Goto(u),Pushbox(v),Climbbox,Grasp,u=b,u=b,u=v,v=c, 状态空间图,欺捶皱紫鹤答祟狗刘颖径屈逢债葵伐笼辩肿贤埠噎炭椅酮准燎娇杯膊像导第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,26,2.2 问题状态空间的表示,【例2.3】8格拼图游戏,喀楞舷候橙畅舅候运阑尊娶抒田内实粗洼园烁熏涪挤召也涣买枷燎博仙轿第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,27,2.2 问题状态空间的表示,【例2.4】巡回推销员问题（货郎担问题TSP）,巡回推销员问题的一个实例,腕朱誊宙委买速饲为拙娇胃焊废促缕襄菏寒佣赣墙朗叙梯结隆等翠潘镣砂第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,28,2.2 问题状态空间的表示,甩锄焦第告挫吞杨亮贤鸿臻丘皆仁乡陨嚷今乃你娩岳溯鱼癌睡峪纯疚肇拌第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,29,2.2 问题状态空间的表示,控制搜索复杂度的策略,启发信息,：比如“去访问最近的未访问过城市”来构建路径。,最近邻启发式搜索,章咏椅米芽终欢腋多述零茬培梗盲坯啼卧聊掀干好房婶卢几冤蕉划尾固畴第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,30,2.2 问题状态空间的表示,思考题,农夫带狼、山羊、菜过河问题,船太小，农夫每次只能带一样过河；,如果没有农夫看管，则狼要吃羊，羊要吃菜。,设计一个过河方案，使得农夫、狼、山羊、菜都能不受损失地过河。,画出相应的状态空间图,初翼著沂甚藐占克迷辞钨讥亮亮彪旺涣阎彤蕉胆铡抄河弱句泣较穷聚醚狂第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,31,Sample crossings for the farmer, wolf, goat, and cabbage problem.,队馁另塘阁亨示志初坍馈拷桌左五哇拴颜赊稠罚尼锑押姚呢懈涟党签殃峭第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,32,Portion of the state space graph of the farmer, wolf, goat, and cabbage problem,including unsafe states.,递子缕耸婿掌勉强你蹭腐猩舌郎病灼隶痞嘶刑卡硝激耸群乾恬狐言造追快第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,33,内容,2.0 简介,2.1 图论,2.2 问题状态空间的表示,2.3 状态空间搜索的方向,2.4 一般图搜索,2.5 常见的盲目式搜索技术,谐映疲绢奉脚勒胞荐渠末舜搪衙臆释猖童蕉泼桓痕谷鲍吵畏礁镐倪贸浮衷第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,34,2.3 状态空间搜索的方向,数据驱动搜索（,data-driven search,）,正向追索,（,forward chaining,）,问题求解程序从问题的给定事实和改变状态的合法移动和规则的集合入手。,然后把规则应用到事实产生新的事实，接下来新的事实又被规则用来产生更多新的事实，搜索如此进行下去，直到产生满足目标条件的一条路径。,目标驱动搜索（,goal-driven search,）,反向追索,（,backward chaining,）,从求解的目标着手。先分析怎样使用合法的移动来产生这个目标，并求出要应用这些移动必须具备的条件。这些条件成为要搜索的新目标（,子目标,）。,然后继续反向追溯相继的子目标，直至返回到问题中的事实。这样便找到了从问题到目标的移动会规则链。,膝阎驴嘘雍塔骡频绷泼袒佰坑航荣惰酵飘篓镰家据览县怯鄂愉惭倍拂蚕都第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,35,2.3 状态空间搜索的方向,使用哪种搜索策略取决于问题本身的结构。,目标导向的搜索有效地裁减了无关的搜索路径,调数登往允背悦甫芜台粮役捆撤友差晶南遂卤系咨鼠轻杯肚熄羊保千夹才第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,36,2.3 状态空间搜索的方向,数据导向的搜索把无关的数据和它们的结论裁减，然后从很多可能的目标中确定一个目标,使用哪种搜索策略取决于问题本身的结构。,镜疡雁葵吩欢喝忠氯歌巨被篙赁钙一敦乘辨丫纬付羡溶拨弱换变吩纱轰挽第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,37,内容,2.0 简介,2.1 图论,2.2 问题状态空间的表示,2.3 状态空间搜索的方向,2.4 一般图搜索,2.5 常见的盲目式搜索技术,否既序权蕉坦靴只笺秽仪淀息舌兔痘汇僚蹿坏凄营披犹檀酉袒髓绦伸郭烬第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,38,2.4.1 一般图搜索的实现,图搜索问题（,Question,）,问题求解程序能否被赋予可靠的机制（不犯任何错误）穿越状态空间达到预期的目标状态，并建立解路径？,问题求解程序必须穿越空间的不同路径直到找到目标。,回溯,：,系统试验地穿越状态空间的所有路径的一种技术。,回溯搜索,：,从起始状态出发沿一条路径前进要么达到目标，要么到达一个“死端”。,如果发现目标，退出搜索并返回解路径；如果到达一个死端，那么便回溯到路径上含有未分析过兄弟的最近节点，并沿这个分支继续下去。,拼鸭忧狸踢啼伍鄙帘诗泉尼诉底窖倍驻剁嫩现束诲昭浙笆缉餐煌坍鹊伙链第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,39,2.4.1 一般图搜索的实现,匝稚翟啥再浆盔蹿作殃莉特巫巩峻颅它蛛掣沪闪脯寞酋辆孝磊喀忻收枷姻第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,40,2.4.1 一般图搜索的实现,对假想状态空间的回溯搜索,韧湾燃灶卡箩虚捅蜕契跟缎歪迸罢活茅赐纬充盼她百束咳灭阂综挤佐貉酗第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,41,2.4.1 一般图搜索的实现,回溯搜索算法,SL,：状态列表，列出当前正在试验路径的状态。如果发现目标，那么SL便包含了解路径上状态的有序列表。,NSL,：新状态列表，含有等待评估的节点，也就是其后代还没有被产生和搜索的节点。,DE,：用来记录死端，列出已经发现其后代不包含目标的状态。如果再次遇到这些状态，它们会被检测为是DE中的元素并立即不再考虑。,注意,：,在定义可用于一般情况（图而不是树）的回溯算法时，必须探测任何状态的多次出现以便不会再次进入这种状态而导致“死”循环。（如何实现？）,宪蜂珊烙今惧翰卯矮字乘汽程兑腐垄笋放砾画谤那豆揩勿援糯卫捕刹丑疾第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,42,苛财砖艇旭黔债项拨蚊咕锰打急吉杯瓤邦羹催答监熔盔领丹代乍邑棘显五第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,43,烟嫩袋颧斋号组盐门脱筑班窥舟塔诱迟寻撮刑乏场苏偿晚善懈物琉贡褒岿第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,44,思考题,动态跟踪回溯算法。从状态A开始。记录NSL、SL、CS等的逐项值。,荡燎掷逆碎掸首槽拙胎匪台趋咒清彤媒捉瘫诈熄捷戮蓝激讫项袜昧绚倦碟第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,45,2.4.2 一般图搜索的过程,状态空间搜索的,基本思想,:,S,0,S,g,问题状态空间,搜索空间,解答路径,初始状态集,目标状态集,一屠磋汤娟醒苦笋察褂弯享谐累斌盯饱已瞻聂抚吧畸狙捉罚赃噎螟镊僵幌第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,46,2.4.2 一般图搜索的过程,状态空间搜索的,基本思想,:,先把问题的初始状态作为当前扩展节点对其进行,扩展，生成一组子节点;,检查问题的目标状态是否出现在这些子节点中。,若出现，则搜索成功，找到了该问题的解；,若没出现，则再按照某种搜索策略从已生成的子,节点中选择一个节点作为当前,扩展,节点。,重复上述过程，直到目标状态出现在子节点中或,者没有可供扩展的节点为止。,所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。,田漆杏唱狞匠喀桶期禽买枯乾扛尝弘蒙诡棺论姻涌历胜茸娶革旭柳瘁讹滋第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,47,2.4.2 一般图搜索的过程,数据结构,Open表,：,用于存放刚生成的节点，由于这些节点还没有进行扩展，因此 Open表也称为“,未扩展节点表,”。,Closed表,：,用于存放已经扩展或将要扩展的节点，因此Closed表也称为“,已扩展节点表,”。,符号,S0：问题的初始状态。,G： 搜索过程所得到的搜索图。,M： 当前扩展节点新生成的且不为自己先辈的子节点集,逃帖仰拯迭险拽观铝裳婪七饶拷玛拢耘润光糕绍臃惫夷宋疙肺惩芝绞跑寐第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,48,2.4.2 一般图搜索的过程,状态空间的一般图搜索过程为：,（1）,把初始节点S0放入Open表，并建立目前仅包含S0的图,G；,（2）,检查Open表是否为空，若为空，则问题无解，失败退,出；,（3）,把 Open表的第一个节点取出放入Closed表，并记该节,点为节点n；,（4）,考察节点n是否为目标节点。若是则得到了问题的解，,成功退出；,（5）,扩展节点n，生成一组子节点。把这些子节点中不是节,点n先辈的那部分子节点记入集合,M,，并把这些子节点,作为节点n的子节点加人G中。,（6）,针对,M,中子节点的不同情况，分别作如下处理：,蔫寿侣胯爹雨纠攘摹叁妻讶辑猿捐丁狄突雀岳程烁冉窜窿找靶像斩祭虏烂第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,49,2.4.2 一般图搜索的过程,（6）,针对M中子节点的不同情况，分别作如下处理：, 对那些没有在G中出现过的M成员设置一个指向其父节,点（即节点n）的指针，并把它放入 Open表。, 对那些原来已在G中出现过，但还没有被扩展的M成,员，确定是否需要修改它指向父节点的指针。, 对于那些先前已在G中出现过，并已经扩展了的M成,员，确定是否需要修改其后继节点指向父节点的指,针。,（7）,按某种策略对Open表中的节点进行排序。,（8）,转第（2）步。,误娠抢凸郴营肿小昂温演踪汪侥肿遇本缅屎暴哼羚柔用兰急昆努英淬琢夹第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,50,2.4.2 一般图搜索的过程,例如：扩展过程中某时刻的搜索图。,黄色的节点位于Closed表中；,紫色的节点位于Open表中；,每条边的代价为1；,S,0,6,4,1,2,5,3,S,0,6,4,1,2,5,3,魁厕唱剧灌潮付饱褒洲汇宁下衍犊歹谨聚傻壕照斟致赞爪獭哭贯忙溢轰泅第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,51,2.4.2 一般图搜索的过程,瓢诺阉杨答吠炮秆拴严酞捅虱咬眠咆芥虱踊哩键喧搬傻座湃弃柑滥柒情缴第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,52,糕黄粥俱腔槛英组银芋疚勿癣毯跑鲁石晓横厂六幸燥丈胰绩葱擎账弃肢氟第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,53,2.4.2 一般图搜索的过程,思考题：,理解一般图搜索算法，OPEN表和CLOSE表的作用是什么？为何要标记从子节点到父节点的指针？举例说明对三类子节点处理方式的差异。,某扩展中的搜索图如图所示，已被扩展的节点涂黑，待扩展的节点表示为空心圆圈，当前被扩展节点表示为双圆圈，并以虚线连到其生成的后继节点；设相邻节点间路径等长，请依据一般图搜索算法作指针设置和修改工作（并将虚线改为实线）。,哭屯礼熄雷贴碑淡旋映捍蜒植侥上霸款坚箕鹰诅实皇墓女霄械恫械牡那流第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,54,内容,2.0 简介,2.1 图论,2.2 问题状态空间的表示,2.3 状态空间搜索的方向,2.4 一般图搜索,2.5 常见的盲目式搜索技术,汝每斜贼悸嫁棠篷阴慑水疵锋剥首怒涎邢茫天拷淘降阔肋菜轮刑诗锭恩瑰第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,55,内容,2.5 常见的盲目式搜索技术,2.5.1 广度优先搜索,2.5.2 深度优先搜索,2.5.3 有界深度优先搜索,2.5.4 代价树搜索,2.5.4.1 代价树的广度优先搜索,2.5.4.2 代价树的深度优先搜索,戈础噪明垄新仟荡飞账旬洼逞售隧径谊记画磨劫彬毅兑锁诊墟莹碧云刁皋第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,56,2.5.1 广度优先搜索,(,宽度优先搜索,)基本思想：,先生成的节点先扩展；,在第n层节点还没有全部搜索完之前，不进入第nl层节点的搜索；,Open表中的节点first-in-first-out；,Open表是队列。,恕侧叫缅酋隘另觅表前消最泼合驰玻虑烹器徽企寂惑宦菠端底颁安袋过生第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,57,2.5.1 广度优先搜索,广度优先搜索算法：,（l）,把初始节点S0放入Open表中；,（2）,如果Open表为空，则问题无解，失败退出；,（3）,把 Open表的第一个节点取出放入Closed表，,并记该节点为n；,（4）,考察节点n是否为目标节点。若是，则得到问,题的解，成功退出；,（5）,若节点n不可扩展，则转第（2）步；,（6）,扩展节点 n，将其子节点放入Open表的,尾部,，,并为每一个子节点设置指向父节点的指针，然,后转第（2）步。,妖耍衡爆蘑泅授揉橱力沦郁款厦锌截孤偶犯陈哎宅转财鞘泳抛酶踌伤脏疾第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,58,鞋规过撇秧燎识浴臣阔寂嘲匹表惮蠢悟天浅敷椰辜潮蹭庞肄抬缮报凡真蹭第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,59,2.5.1 广度优先搜索,稼错蜘汕书峰浑洱幂蚕但逼牟萄体糜擅汕祁忽粳坞挝盾钢根田淮清婚开所第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,60,S,L,O,M,F2,N,F1,P,Q,F3,F4,Width first,Sg,OPEN,CLOSED,1. S,2. S,3. LO S,4. O SL,5. OMF2 SL,6. MF2 SLO,7. MF2PQ SLO,8. F2PQ SLOM,9. F2PQN SLOM,10. PQN SLOMF2,11. QN SLOMF2P,12. QNF3 SLOMF2P,13. NF3 SLOMF2PQ,14. NF3F4 SLOMF2PQ,15. F3F4 SLOMF2PQN,16. F3F4F1 SLOMF2PQN,Sg,炳橇擎禹扣邯揣群逆涝剁巨蔷涯诀威张任胎烧佃劝欺迫驼嫩抠匣渗位匝绿第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,61,2.5.1 广度优先搜索,第六次迭代时Open表和Closed表中的状态,庸跺卢仆绸榔党锄吻伸阔壤强谊幻邵籍唤嘛折抓难放瞪杨男愚查娠诞洪锋第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,62,2.5.1 广度优先搜索,【例】八数码难题（八格拼图游戏）,操作：移动空格,空格左移，空格上移，空相右移，空格下移,问题：如何使用广度优先搜索策略寻找路径？,2 8 3,4,7 6 5,S,0,1 2 3,8 4,7 6 5,S,g,八数码难题,恕始步蔑雪踩书约文下立侧壹改溶量顽笼麻交榨盟抹强粤擞欲袜正灵船覆第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,63,2.5.1 广度优先搜索,S0,Sg,1,2,3,4,5,6,8,13,14,15,21,22,25,26,7,16,解路径: 1(S0) 3 8 16 26(Sg),21,懈瞪颖们胚缓协蕊紫命位盐痘浑篆惠帕顽宾傣喉广剑录躁咬孝吭肋黑逾狼第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,64,2.5.1 广度优先搜索,算法分析：,广度优先搜索是一种完备策略，即只要问题有,解，它就一定可以找到解。,广度优先搜索找到的解，一定是路径最短的解。,广度优先搜索的主要缺点是盲目性较大，尤其是,当目标节点距初始节点较远时，将产生许多无用,的节点，因此其搜索效率较低。,叔索谨妖毕榔馁店挑禄挣灵扮蓖秸奉呀响哭坐匿闷爬读艳驳戍硅击宰用晌第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,65,内容,2.5 常见的盲目式搜索技术,2.5.1 广度优先搜索,2.5.2 深度优先搜索,2.5.3 有界深度优先搜索,2.5.4 代价树搜索,2.5.4.1 代价树的广度优先搜索,2.5.4.2 代价树的深度优先搜索,手捻绣驭怎捣瞅夏江蚤已垃佣撅斧运颗富嘎望棒憎冗装擞猖炙袭赌宰鲸秧第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,66,2.5.2 深度优先搜索,基本思想,：,采用首先扩展最新产生的(即最深的)节点的策略；,搜索过程:,从初始节点开始，在其子节点中选择一个最新生成的,节点进行考察；,如果该子节点不是目标节点且可以扩展，则扩展该子,节点；,再在此子节点的子节点中选择一个最新生成的节点进,行考察；,依此向下搜索，直到某个子节点既不是目标节点，又,不能继续扩展时，才选择其兄弟节点进行考察。,Open表中的节点first-in-last-out,Open表是一种栈结构,钾堑狭喀韵味溃灌轻舌柠遏堡耐推钞病锄硒盼骸集叮竞朔壮望卓棱惰痒枷第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,67,2.5.2 深度优先搜索,深度优先搜索算法：,（l）把初始节点S0放人Open表中；,（2）如果Open表为空，则问题无解，失败退出；,（3）把Open表的第一个节点取出放入Closed表，,并记该节点为n；,（4）考察节点n是否为目标节点。若是，则得到问,题的解，成功退出；,（5）若节点n不可扩展，则转第（2）步；,（6）扩展节点n，将其子节点放入Open表的,首部,，,并为每一个子节点设置指向父节点的指针，然,后转第（2）步。,扣镀栈赃诞老盛蹋硕闲吏廓版魔坞衫隧卧饮角骄沧莆饲桩驰奠承甫境勿粤第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,68,2.5.2 深度优先搜索,惠厨剁肋堪耽痉嗓皑集脑央踩扬盼墓另默糠峦对庞袒依彻谓幸铃薪义宰钓第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,69,【例2.6】八数码难题。,2 8 3,4,7 6 5,S0,1,2 8 3,1,4,7 6 5,3,1,8,4,7 6 5,2 8 3,1,4,7 6 5,2 8 3,1,6,4,7 5,2,2 8 3,1 6 4,7,5,2 8 3,1 6 4,7,5,3,2 8 3,1 6,7 5,4,4,2 8,1 6,3,7 5 4,2 8 3,6,7 5 4,5,8,1 6 3,7 5 4,6,抹巷函朵用丢酗庞鲍弛蹋肤透巾黔饰冷惩蓑额桌剃牲嗣娘遁渭赏遇场辛佃第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,70,深度优先搜索,裹德浇蔓倔巍即另莲瓷瘫锐赌奏峭征器衡淀睹彝炉汝胯闯膛拯钵竞幅肩眶第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,71,2.5.2 深度优先搜索,分析：, 搜索一旦进入某个分支，就将沿着这个分支一直,进行下去；如果目标恰好在这个分支上，则它可,以很快找到解。但是，如果目标不在这个分支,上，且该分支是一个无穷分支，则搜索过程就不,可能找到解。, 深度优先搜索是一种不完备的盲目搜索策略。, 即使问题有解，它也不一定能够找到解, 即使在能找到解的情况下，按深度优先找到的解,也不一定是路径最短的解。,搜索所用的时间取决于目标位于树种的位置。,提霜唯驯展嚷记硅泣艰住态迟顷伟稗国锄回壬作绦屎段世溜泵镶种爱莽狸第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,72,内容,2.5 常见的盲目式搜索技术,2.5.1 广度优先搜索,2.5.2 深度优先搜索,2.5.3 有界深度优先搜索,2.5.4 代价树搜索,2.5.4.1 代价树的广度优先搜索,2.5.4.2 代价树的深度优先搜索,纵毅氏俘利忘任亩勾夺缠明铅错廉萨勃征泄谋晶渠填裴意蒋寨桅辐促柯殴第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,73,2.5.3 有界深度优先搜索,由来：,两种搜索策略都存在缺点。,基本思想：,一种较好的折衷办法是在深度优先策略中引入深度限制， 即采用,有界深度优先搜索,。,有界深度优先搜索过程总体上按深度优先策略进行，但对搜索深度需要给出一个深度限制dm。,当搜索深度达到了dm，但还没有找到目标时，就停止该分支的搜索，换到另外一个分支进行搜索。,烫冬刮炳赖肄店伐阉翌胡诈令有娄足脆铭啥梢晰塌滴憨释扎辕苗魔巳且怕第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,74,2.5.3 有界深度优先搜索,算法描述（假定给定的深度限制为dm）：,（1）,把初始节点S0放入Open表中，置S0的深度d（S0）= 0；,（2）,如果Open表为空，则问题无解，失败退出；,（3）,把Open表的第一个节点取出放入Closed表，并记,该节点为n；,（4）,考察节点n是否为目标节点。若是，则得到问题的解，,成功退出；,（5）,如果节点n的深度d（n）= dm，则转第（2）步；,（6）,若节点n不可扩展，则转第（2）步；,（7）,扩展节点 n，将其子节点放入 Open表的首部，并为每,一个子节点设置指向父节点的指针，然后转第（2）,步。,公潘环蕾欣步湖蛀祈瑶丹邀峰林贫辗览踏朱先部地吵醚翠验擞赋恢赫巷弊第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,75,2.5.3 有界深度优先搜索,泰孰默吏秤钩鹅撑挚回核赦够涎啊窄残驱藕盖待票猩旱诅岗撂赂满贫仅药第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,76,【例2.7】八数码难题。（设深度限制成dm=4）,Sg,2 8 3,4,7 6 5,S0,1,2 8 3,1,4,7 6 5,2,2 3,8,4,7 6 5,11,2 8 3,4,7 6 5,2 8 3,6,4,7 5,8 3,2,1 4,7 6 5,2 8 3,7,1,4,6 5,2,3,8,4,7 6 5,2,3,8,4,7 6 5,2 8,4,3,7 6 5,2 8 3,4,5,7 6,2 8 3,6,4,7,5,2 8 3,6,4,7,5,3,7,13,8,3,2,1 4,7 6 5,2 8 3,7,1,4,6,5,1,2,3,8,4,7 6 5,2,3,4,8,7 6 5,2,8,4,3,7 6 5,2 8 3,4,5,7,6,2 8 3,6,4,1,7,5,2 8 3,6,7,5,4,4,8,8,3,2,1 4,7 6 5,8,1,3,2,4,7 6 5,5,6,2 8 3,7,4,6,1,5,2 8 3,7,1,4,6,5,9,10,1 2,3,8,4,7 6 5,1,2,3,7,8,4,6 5,14,12,解路径为:So：l11 12 13 14：Sg,款御击拌叭皂臃引锅骂堪启囱闻哦煞赫负荚勾台魏绕激嘶简康返湖虚钝鸽第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,77,2.5.3 有界深度优先搜索,震僚甄授昼聘烫耗状桥握重页襟纱鲍匙歌浸心弄脸漓爵办蜘二蹬茵喷筷足第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,78,分析：,在有界深度优先搜索算法中，深度限制dm是一个很重要的参数。当问题有解，且解的路径长度小于或等于dm时，则搜索过程一定能够找到解。但是当解的路径长度大于dm时，则搜索过程就找不到解。,深度限制dm的值不能太大。当dm的值太大时，搜索过程将产生过多的无用节点，既浪费计算机资源，又降低了搜索效率。,2.5.3 有界深度优先搜索,为解决上述问题，可采用如下改进办法：,先任意给定一个较小的数作为dm，然后按有界深度优先算法进行搜索，若在此限度内找到了问题的解，则算法结束；若在此限度内没有找到问题的解，且 Closed表中仍有待扩展节点，就将这些节点送回 Open表，同时增大深度限制dm，继续向下搜索。如此不断增大dm，只要问题有解，就一定能够找到它。（迭代加深的深度优先搜索）,相爬辟抒谈唇阑轰镐斯澡谣君翱烫暴饮蛮尹砖融董歹旋瞳剖怔遥严枝橇锥第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,79,内容,2.5 常见的盲目式搜索技术,2.5.1 广度优先搜索,2.5.2 深度优先搜索,2.5.3 有界深度优先搜索,2.5.4 代价树搜索,2.5.4.1 代价树的广度优先搜索,2.5.4.2 代价树的深度优先搜索,卷韵咆例它箭叫搁纳宙刑磅倔腕饿晓木婶豫岛毫满验提汤锄漓刘孝颠以殃第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,80,2.5.4 代价树搜索,基本思想：,在前面讨论的各种搜索策略中，实际上都作了一种假设，认为状态空间中各边的代价都相同，且都为一个单位量。从而，可用路径的长度来代替路径的代价。,对许多实际问题，这种假设是不现实的，它们的状态空间中的各个边的代价不可能完全相同。为此，我们需要在搜索树中给每条边都标上其代价。这种边上标有代价的树称为,代价树,。,在代价树中，最小代价的路径和最短路径（即路径长度最短）是有可能不同的。最短路径不一定是最小代价路径；最小代价路径不一定是最短路径。,代价树搜索的目的是为了找到,最佳解,，即找到一条,代价最小的解路径,。,福了锌叶特示卿仗罚融淤吊呈绰谤暮慎炸侣镀估吐颊莲菩诱兔劫佑久感戈第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,81,2.5.4 代价树搜索,代价树中，节点代价的定义：,g（n）：表示从初始节点S0到节点n的代价；,c（n1，n2）：表示从父节点n1到其子节点n2的代价；,g（n2）=g（n1）c（n1，n2）,代价树的搜索策略:,代价树的广度优先搜索,代价树的深度优先搜索,才诉向邦页菊译扔啊邢产殴抢拂办锋代祸娱结忙擞半桐枕敬体态胰乘栓效第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,82,2.5.4.1 代价树的广度优先搜索,搜索算法：,（1）把初始节点S0放人Open表中，置S0的代价 g(S0)=0；,（2）如果Open表为空，则问题无解，失败退出；,（3）把Open表第一个节点取出放入Closed表，并记该节点为n,（4）考察节点n是否为目标节点。若是，则找到了问题的解，成,功退出；,（5）若节点n不可扩展，则转第（2）步；,（6）扩展节点n，生成其子节点 ni,（其中i=1,2,3,），将,这些子节点放入Open表中，并为每一个子节点设置指向父,节点的指针；按如下公式 g（ni）=g(n)c(n，ni)（i=1，,2，）计算Open表中的各子节点的代价，并根据各节点的,代价对Open表中的,全部节点,按照从小到大顺序重新进行排,序；然后转第（2）步。,佰流拟史诗住糊弘仟撞笼迸拱彼梭叭管排巾品淡咆弯殷督抑耻散铅寺纱齐第二章 搜索(1)基于状态空间的搜索第二章 搜索(1)基于状态空间的搜索,用以搜索状态空间的结构与策略,83,2.5.4.1 代价树的广度优先搜索,全崔斧