三章状态空间搜索策略

《三章状态空间搜索策略》由会员分享，可在线阅读，更多相关《三章状态空间搜索策略（61页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章 状态空间搜索策略状态空间搜索策略 第三章第三章 状态空间搜索策略状态空间搜索策略 3 3.1 .1 搜索搜索的概念及种类的概念及种类3 3.2 .2 盲目搜索策略盲目搜索策略3 3.3 .3 启发式搜索启发式搜索策略策略赶眺野检蛋仗宁莲妊旧权命挟宾鄂豫一抿哗超臼暗黎仰巫剥甘债扮翠辞啥三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 例例1 1 走迷宫是人们熟悉的一种游戏，如图就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示。我们通过例子引入状态空间搜索状态空间搜索的概念。呈窝芳娶豢

2、华浑慢隙使项斌恩遭掌亮褂帖服杰鉴晾纳臻含瞧郎酶栗胶亏掺三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 迷宫的有向图表示走迷宫其实就是从该有向图的初始节点(入口)出发，寻找目标节点(出口)的问题，或者是寻找通向目标节点(出口)的路径的问题。寅诣蚕徐樱振库炬篆令膝侦蔡苹搔浩矣轮撇髓茧哪蜜毅刨环酶愁唉腾找讹三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 例例2 2 在一个33的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移

3、入空格。现在的问题是：对于指定的初始棋局和目标棋局(如图)，给出数码的移动序列。该问题称为八数码难题或重排九宫问题。 2831476581324765初始棋局目标棋局嫌醉龟峨拎摹耪忌锐亭巍在淋蒲猫央蛇塞绳麻料享桐惶秃皑汐查赡蕾高悸三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 状态空间（图）是一类问题的抽象表示，有许多智力问题(如Hanoi塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在状态空间(图)中寻找目标或路径的问题。因此，研究状态空间搜索具有普遍意义。 唁倔致馅葵群釜衣惊

4、蔚崇耙蕊礁球砰肥郑唐钠屡祟年埔磨宫萤华甜含霸毖三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 3 3.1 .1 搜索搜索的概念及种类的概念及种类现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。搜索：是一种求解问题的方法，是寻找从问题初始事实到最终答案的推理路线的一种过程。搜索包含两层含义：一是根据问题的实际情况，按照一定的策略，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线；另一是找到的这条路线是时空复杂度最小的求解路线。3.1.1 3.1.1 搜索的概念搜索

5、的概念刽嵌恼杏栏舶补匹籍地喻焉嚼艺茁苞须孜顿看贤屈块宠伐傈亥骄舶颖谈钮三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 盲目搜索：又称无信息搜索。即在搜索过程中，只按预先规定的搜索控制策略进行搜索。问题本身的特性对搜索控制策略没有任何影响，搜索带有盲目性，效率不高，只用于解决比较简单的问题。启发式搜索：又称有信息搜索。指在搜索求解过程中，根据问题本身的特性来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。搜索求解的效率高，易于求解复杂的问题，但抽取出问题的相关特性和信息难。3.1.2 3.1.2 搜索的种类搜索的种类

6、搜索分为盲目搜索和启发式搜索两种。公竟互逾往猩今敝憨盔郑绥逻垄檀囊找秃宽矛躲箍辊执淳在亿车累汹闰仔三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 状态空间表示法：是一种用状态和算符表示问题的方法。当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。状态空间图：状态空间的图示表示问题形式。状态空间图是一个有向图，节点表示状态，有向边（弧）表示算符。3.2 3.2 盲目搜索策略盲目搜索策略3.2.1 3.2.1 状态空间图的搜索策略状态空间图的搜索策略状态空间图对问题的求解就相当于在有向图上寻找一条从某一节点(初始状态节点)

7、到另一节点(目标状态节点)的路径。粱捻搓肥歉喂下恼朔云霍删卵谊绑慕题愈蜡忱滴佰翼捆捶章肿乖刹沮云龄三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 搜索法求解问题的基本思想：首先将问题的初始状态(初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(后继节点)，然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。退弄抡兑吨红遥螺畴书职疆亮嫉贤犁布悠壕

8、窃称钙际寿啼沫剔沃雌尸郭袜三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 节点扩展节点扩展 概念概念扩展：就是用合适的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求后继节点的过程。已扩展节点：对状态空间图中的某个节点，如果求出了它的后继节点，则此节点为已扩展的节点。未扩展节点：对状态空间图中的某个节点，如果尚未求出它的后继节点，则此节点称为未扩展节点。堆沃掸鹃脯苏柱小抒猫只逼目或释辑室轨霜罗剧肇值劝寝烈罗腆寐岔舷村三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 在对状态空间图搜索求解时，将未扩展的节点

9、存于一个名为OPENOPEN的表中，而将已扩展的节点存于一个名为CLOSEDCLOSED的表中。 状态空间图的一般搜索策略：状态空间图的一般搜索策略：姓由挞贾癸檀旧两态弧标恕忻伎厕玉沙掀急轮津慧招摩枣侈釜摔郁攘她呢三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹。我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点（已扩展的节点）。CLOSED表中存储的是一棵不断成长的搜索树。另一方面，还得不断地把待考查的节点（未扩展的节点）组织在一起，并做某种排列，以便控制搜

10、索的方向和顺序。我们采用一个称为OPEN表的动态数据结构，来专门登记当前待考查的节点。痈屿透澳抉裔族朋崇钵酣贵庞各愤耽丢浇碴技招垫磨绎途艾亩柬啊捍豹糕三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 (1)(1)建立一个只含有初始节点建立一个只含有初始节点S S0 0的搜索图的搜索图G G，把把S S0 0放人放人OPENOPEN表中。表中。(2)(2)建立建立CLOSEDCLOSED表，且置为空表。表，且置为空表。(3)(3)判断判断OPENOPEN表是否为空表，若为空，则问表是否为空表，若为空，则问题无解，退出。题无解，退出。(4)(4)若若OPENO

11、PEN表非空，选择表非空，选择OPENOPEN表中的第一个表中的第一个节点，把它从节点，把它从OPENOPEN表移出，并放人表移出，并放人CLOSEDCLOSED表中，将此节点记为节点表中，将此节点记为节点n n。(5)(5)考察节点考察节点n n是否为目标节点，若是，则问是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从题有解，并成功退出。问题的解即可从图图G G中沿着指针从中沿着指针从n n到到S S0 0的这条路径得到。的这条路径得到。(6)(6)扩展节点扩展节点n n生成一组不是生成一组不是n n的祖先的后继的祖先的后继节点，并将它们记为集合节点，并将它们记为集合M M，将，

12、将M M中的这中的这些节点作为些节点作为n n的后继节点加入图的后继节点加入图G G中。中。(7)(7)对那些对那些未曾在未曾在G G中出现过中出现过的的M M中的节中的节点，设置一个指向父节点点，设置一个指向父节点( (即节点即节点n n) )的指针，并把这些节点加入的指针，并把这些节点加入OPENOPEN表中；对于表中；对于已在已在G G中出现过中出现过的的M M中的中的那些节点，确定是否需要修改指向那些节点，确定是否需要修改指向父节点父节点( (n n节点节点) )的指针；对于那些的指针；对于那些先前已在先前已在G G中出现中出现并且已在并且已在CLOSEDCLOSED表中的那些表中的那

13、些M M中的节点，确定是否中的节点，确定是否需要修改通向它们后继节点的指针。需要修改通向它们后继节点的指针。(8)(8)按某一任意方式或按某种策略重排按某一任意方式或按某种策略重排OPENOPEN表中节点的顺序表中节点的顺序。(9)(9)转第转第(3)(3)步。步。算法算法3.13.1 状态空间图的一般搜索算法状态空间图的一般搜索算法烛漂剩仔输拾忙步迅澜贫视逆派偏衣结失彰栗握滋劣彭薪氖堑变袱肾脑衷三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 呀许俊咎研掐拱滁镐裙壬檄声氧绦看巧僧啼理栅千圣忙锗穗珍杖裴端锻土三章状态空间搜索策略三章状态空间搜索策略第三章第

14、三章 状态空间搜索策略状态空间搜索策略 在搜索过程中，生成了一个图G，它是问题状态空间图的一部分，称为搜索图。由搜索图G中的所有节点及设置的指向父节点的反向指针，所构成的集合T，称为搜索树。在搜索过程中，问题的解就是从初始节点So到目标节点路径上的算符所构成的序列。路径是通过目标节点按设置的指针指向初始节点So回溯而得到的。竣混恕阵瘸姐枕棘铺踏剃损苯寄喝蔓赘歹何聋尼格移廊淤疏嘉蕾绞纹苏瘸三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 3.2.2 3.2.2 宽度优先搜索策略宽度优先搜索策略宽度优先搜索又称为广度优先搜索。基本思想：是从初始节点开始，逐层对

15、节点进行依次扩展，并考察它是否为目标节点。在对下层节点进行扩展(或搜索)之前，必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：“先入先出”，即先进入的节点排在前面，后进入的节点排在后面。戳理您何混街雁仑码芝匈后枚趣汽侍还志蛇毗来铆磕琼钢琢拟叛秤技降绽三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.23.2 状态空间图的宽度优先搜索算法状态空间图的宽度优先搜索算法(1)(1)把初始节点把初始节点S S0 0放人放人OPENOPEN表中。表中。(2)(2)如果如果OPENOPEN表是空表，则没有解

16、，失败退出；否则继续。表是空表，则没有解，失败退出；否则继续。(3)(3)把把OPENOPEN表中的第一个节点表中的第一个节点( (记为节点记为节点n n) )移出，并放人移出，并放人CLOSEDCLOSED表中。表中。(4)(4)判断节点判断节点n n是否为目标节点，若是，则求解结束，并用是否为目标节点，若是，则求解结束，并用回溯法找出解的路径，退出；否则继续执行回溯法找出解的路径，退出；否则继续执行(5)(5)。(5)(5)若节点若节点n n不可扩展，转第不可扩展，转第(2)(2)步；否则继续执行步；否则继续执行(6)(6)步。步。 (6)(6)对节点对节点n n进行扩展，将它的所有后继节

17、点放人进行扩展，将它的所有后继节点放人OPENOPEN表的表的末端，并为这些后继节点设置指向父节点末端，并为这些后继节点设置指向父节点n n的指针，然的指针，然后转第后转第(2)(2)步。步。厄褐委朱胡韶串毛呻旋缀召淌公椒食化忠储拨缺粗铲岿贝试砾掘锗揖燥垄三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 忌见尔佰丸眷访砰奔箔谦侠歇巧剁店台狠墒烯筏休钦苏胆很慰敛牲锭矩曼三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 例例3.13.1 八数码难题：设在33的一个方格棋盘上，摆放着8个数码1、2、3、4、5、6、7、8，有

18、一个方格是空格，其初始状态如下图(a)所示，要求对空格执行下列的操作(或算符)： 左移，上移，右移，下移。 使8个数据最终按下图(b)的格式摆放，图(b)称为目标状态Sg。要求寻找从初始状态到目标状态的路径。2831476512384765S0(a)初始状态Sg(b)目标状态毫咨电项牵殿康伴芬撩财怀紧陵瞪咎骄牛铀教殿秃灌吐蔬衣柄宛碴锤箭税三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 解的路径为解的路径为: :S So o3 38162781627SgSg枢忙漱渝伏狗盛粥掸赐脾滥柒脂僵诞底日丰诉犀阀绦筏腥锤业禽邯命辫咯三章状态空间搜索策略三章状态空间搜索

19、策略第三章第三章 状态空间搜索策略状态空间搜索策略 宽度优先搜索的特点：宽度优先搜索的特点：搜索盲目性较大，效率低。当目标节点距离初始节点较远时，将会产生大量的无用节点。搜索策略是完备的。只要问题有解，宽度优先搜索总可以找到它的解，而且是搜索树中，从初始节点到目标节点的路径最短的解。雪穿狼盟克怂蚜师镍槛尊击做花蜂桑桐管扩汕者胰女婿辽漏滤殆胁词辞哼三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 基本思想：首先扩展最新产生的(即最深的)节点。即从初始节点So开始，在其后继节点中选择一个节点，对其进行考察，若它不是目标节点，则对该节点进行扩展，并再从它的后继节

20、点中选择一个节点进行考察。依次类推，一直搜索下去。当到达某个既非目标节点又无法继续扩展的节点时，才选择其兄弟节点进行考察。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：“后入先出”，即后进入的节点排在前面，先进入的节点排在后面。3.2.3 3.2.3 深度优先搜索深度优先搜索勺唱呆蒂狞照化胃坤花孟捌狮稗汇唾起啊仑赂者措倔游个士寄铆漆粒游届三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.33.3 状态空间图的深度优先搜索算法状态空间图的深度优先搜索算法(1)把初始节点S0放人OPEN表；(2)如果OPEN表为空，则问题无解，退出；(3)

21、从OPEN表中将其第一个节点(节点n)移出，放入已扩展节点表CLOSED中；(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解的路径，退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n ，将其后继节点放到OPEN表的前端，并为其设置指向节点n的指针，然后转第(2)步。修随矗噬剪捉榜筐蹬砷涸萍准卸撞佳莱润哩腥危现码扎瞎讳衔拦城坞干莲三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 峭灶剐困谴椎牺巡框铃宰枉下悉饥咐轻座萤袒业底帽茅侵览颁涪妄濒堂握三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略

22、深度优先搜索与宽度优先搜索的区别就在于：在对节点n进行扩展时，其后继节点在OPEN表中的存放位置。宽度优先搜索是将后继节点放入OPEN表的末端“先入先出先入先出”。深度优先搜索是将后继节点放入OPEN表的前端“后入先出后入先出”。综骚帮冀懂裔怜邻毅络润襟名辊岔莆伦穷派叉邯否蜒亲湃雹浴肢奸铅乔沽三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 例例3.23.2 对例3.1的八数码难题，利用深度优先方法进行搜索求解问题。破桂期成射眯宋秉窟杰险铺赏拈癣叼绎皇绘谤劫砍乃鲤哇锁槽脾验釜淳芹三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间

23、搜索策略 深度优先搜索的特点：深度优先搜索的特点：搜索策略是完备的。搜索若进入某一分支，则沿着这一分支一直搜索下去，对于有限的状态空间图，从理论上讲，解总是能够找到的。搜索效率低。由于某些分支可能扩展得很深，而解又不在这些分支上，这就无疑会降低搜索的效率。戚神坟溯是槐访职厕钡降戏缓妊啮肖拌神姓僧眨晦侥烟笑彼幻涣仪气直垫三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 在深度优先搜索中，为了避免搜索过程沿着无穷的路径一直搜索下去，往往对一个节点扩展的最大深度进行限制。任何节点如果达到了深度界限，就把它作为没有后继节点进行处理，而对另一个分支进行搜索。3.2.

24、4 3.2.4 有界深度优先搜索有界深度优先搜索搜索树中节点深度(d)定义：(1)搜索树中初始节点的深度为0。(2)任何其他节点的深度等于其父辈节点的深度加上1。歉度酮鞠棒唤窄遇怜烫颐屋没啄奏惰佑博溉弯嗽僚滁厘泥念锣业靡账代慕三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.43.4 有界深度优先搜索算法有界深度优先搜索算法 (1)把初始节点So放入OPEN表中。(2)如果OPEN表为空，则问题无解，退出。(3)把OPEN表中的第一个节点n从OPEN表移到CLOSED表。(4)考察节点n是否为目标节点，若是，则求得问题的解，退出；否则继续执行第

25、(5)步。(5)(5)如果节点n的深度dn等于最大深度dm，则转第(2)步。(6)如果节点n不可扩展，即没有后继节点，则转第(2)步；否则继续第(7)步。(7)扩展节点n，将其后继节点放入OPEN表的前端，并为其设置指向节点的指针，转第(2)步。湍歪糖舀辨牛骑踪吁眠豌上研祈踏基常低叔掏拓椭张毕庐碾铲立投汛靴峻三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 仑沼绦织发寨专扑篓局奈耶谦蜕有赦瑰绰列销睹去凹鞭伺丸穗命天重我横三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 例例3.33.3 设八数码难题的初始状态及目标状态

26、分别如下图(a)和图(b)所示，试用有界深度优先搜索策略求解问题。深度界限dm=5。慷崭殖苞磺刊宇祷畅窝误吧涵绍懦份戴赎娟宋倦潞靠歹肃尼湘招赶帮颇廓三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 桃榔岔恕例慰彰葡雍泳噶坏署青没如杯试啤殊窒牢栽画质骑渤疵共投涪沫三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 有界深度优先搜索算法的深度界限的选择很重要。选择过大，可能会影响搜索的效率；选择的过小，有可能求不到解。有界深度优先搜索策略是不完备的。对于某些问题，可能它的解就位于某一分支较深的位置，而界限值选取的没有那么大，

27、就会导致找不到问题的解。圭柄读越篮蝶梨兵辨煮讼颐桩乞橡轧棵陛函屠偷盒赛澄搂许酪梨俞帧夕闹三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 搜索代价问题：在实际问题的搜索求解中，在将一个状态变换成另一个状态时，往往所付出的操作代价(或费用)是不一样的，也就是状态空间图中各有向边的代价是不一样的。这是前面讨论搜索算法没有考虑的。3.2.5 3.2.5 代价树的宽度优先搜索代价树的宽度优先搜索代价树：把有向边上标有代价的搜索树称为代价搜索树，简称代价树。婉孽粮芯陵电招鞠逝夫伞镍涎鸡墨猴际稗狞老免虽持酉设泡岳蹭劫傣砧锌三章状态空间搜索策略三章状态空间搜索策略第三章

28、第三章 状态空间搜索策略状态空间搜索策略 代价计算：在代价树中，把从初始节点So到任意节点i的路径代价记为g(g(i i) )，而把从节点i到其后继节点j的连线之代价(有向边代价)记为C(C(i i, ,，j j) )，则g(j)=g(i)+C(i，j)。代价树宽度优先搜索的基本思想：每次从OPEN表中选择一个代价最小的节点，移入CLOSED表。沤料娩走邹岿茧讯身羚瀑渣考槛蚁佩用缝蹬蚌橡实肢涝误画溅西客闯捆严三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.53.5 代价树的宽度优先搜索算法代价树的宽度优先搜索算法(1)(1)把初始节点把初始节

29、点S So o放入放入OPENOPEN表，令表，令g(Sg(So o)=0)=0。(2)(2)如果如果OPENOPEN表为空，则问题无解，退出。表为空，则问题无解，退出。(3)(3)把把OPENOPEN表中表中代价最小代价最小的节点，即的节点，即排在前端的第一个节点排在前端的第一个节点( (即为节点即为节点n)n)，移入，移入CLOSEDCLOSED表中。表中。(4)(4)如果节点如果节点n n是目标节点，则求得问题的解，退出，否则继续。是目标节点，则求得问题的解，退出，否则继续。(5)(5)判断节点判断节点n n是否可扩展，若不可扩展，则转是否可扩展，若不可扩展，则转(2)(2)步；否则转步

30、；否则转(6)(6)步。步。(6)(6)对节点对节点n n进行扩展，将它们所有的后继节点放入进行扩展，将它们所有的后继节点放入OPENOPEN表中，并对每表中，并对每个个后继节点后继节点j j计算其代价计算其代价g(j)=g(i)+C(ig(j)=g(i)+C(i，j)j)，为每个后继节点设置，为每个后继节点设置指向指向n n节点的指针，然后，根据节点的代价大小对节点的指针，然后，根据节点的代价大小对OPENOPEN表中的表中的所有所有节点进行从小到大的排序节点进行从小到大的排序。(7)(7)转向第转向第(2)(2)步。步。递冰牵掣醒咒这昂娱二盖筐群擂喉腻氨尘蔡真希筋长纵吗架燥诲勾娇仁座三章状

31、态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 岸惕柔溉亚覆匙妥绘啡聂巡粤绸帝道崩序降查审邢醛蛇络彬拐矛姥液壤淮三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 例例3.43.4 推推销销员员旅旅行行问问题题。假假设设A A、B B、C C、D D、E E是是5 5个个城城市市，推推销销员员从从城城市市A A出出发发，到到达达城城市市E E，走走怎怎样样的的路路线线费费用用最最省省?5?5个个城城市市间间的的交交通通图图及及每每两两个个城城市市间间的的旅旅行行费费用用如下图。如下图。惑电误恭巳宪忱旗饲琅枪诚砚马娟督琴告拄宰

32、名奉像宝芝浅挣娶陷驭郎条三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 3.2.6 3.2.6 代价树的深度优先搜索代价树的深度优先搜索代价树宽度优先搜索每次从OPEN表中的全体节点中选择代价最小的节点移人ClOSED表，并对这一节点进行扩展或判断是否为目标节点。代价树深度优先搜索则是从当前扩展节点的后继节点中选择一个代价最小的节点移入CLOSED表，并进行扩展或判断。和蔽碉异捻榆补听势揖耕锯妆站纂鼎杭凭性宅搁爽包沼狰俊瞧私蠢鸣佑朽三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.63.6 代价树的深度优

33、先搜索算法代价树的深度优先搜索算法(1)把初始节点So放人OPEN表中。(2)如果OPEN表为空，则问题无解，退出。(3)将OPEN表中的第一个节点(代价最小的节点记为节点n)移人CLOSED表。(4)如果节点n是目标节点，则求得问题的解，退出；否则转第(5)步。(5)判断节点n是否可扩展，若不可扩展则转第(2)步，否则转第(6)步。(6)(6)对节点n进行扩展，并将其后继节点按有向边代价有向边代价从小到大排序后放入OPEN表的前端前端，并为各后继节点设置指向n节点的指针。(7)转第(2)步。深筷膛东骆瓷焊刷骨骏涟民雀肝猖惯闸卤前言渭棚桓瘪赏宋堕刮揭妒粪餐三章状态空间搜索策略三章状态空间搜索策

34、略第三章第三章 状态空间搜索策略状态空间搜索策略 氖酶窝哩祁化奢坡嘎炎绘谋晓学酌惊功金坞超臂岳猫意诸诡烟烽战玛寺巢三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 卤灾煎巧轰裴斜虽诞幢队洪诱蕴浇玲佩揖都镜轨偏障臻如稍滚摈辕髓勋雏三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 代价树深度优先搜索虽然速度快，但所得到的解不一定是最优解。代价树的深度优先搜索法是不完备的，因为代价树的深度优先搜索法有可能进入无穷分支路径而搜索不到问题的解。获旦寄起熙章桩雅拳沿属淋贴馈融楷特穴今路缝狭粥砧技垛貉计姥柯衷汞三章状态空间搜索策略三

35、章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 3.3 3.3 启发式搜索策略启发式搜索策略启发式搜索：利用问题自身特性信息，以提高搜索效率的搜索策略。又称有信息搜索。3.3.1 3.3.1 启发信息与估价函数启发信息与估价函数启发信息启发信息：于指导搜索过程且与具体问题求解有关的控制性信息。启发信息按其作用来分可以有三种：(1)用于决定要扩展的下一个节点，以免像在宽度优先或深度优先中那样盲目地扩展。(2)在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。(3)用于确定某些应该从搜索树中抛弃或修剪的节点。疆匹伺鼠佰堤嘎微钵楞豹邱战

36、呜峰裴算短昆熄励须历囊争珍薯欧沏磁骚撕三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 估价一个节点价值一般要考虑两方面的因素：已经付出的代价和将要付出的代价。设估价函数为f(x)，则将其定义为： f(x)=g(x)+h(x)f(x)=g(x)+h(x)估价函数估价函数：在决定哪个节点是下一步要扩展的节点上，通常可以构造一个函数来表示节点的“希望”程度，这种函数称为估价函数。其任务就是估计待搜索节点的重要程度，给它们在OPEN表中排定次序。g(x)代价函数代价函数：为初始节点So到节点x已实际付出的代价，可由已生成的搜索树实际计算出来。h(x)启发函数启发

37、函数：是从节点x到目标节点Sg的最优路径的估计代价，用来估计节点x与目标节点Sg接近程度的一种函数。依赖于对问题特性了解的某种经验估计，主要体现了搜索的启发信息。鲤抽叼甥敲外膊邦红陀缮耀厄俭蹬诀静肋屉窟阑乓阶币咽训邢誉贮群盆写三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 一般地，g(x)项体现了搜索的宽度优先趋势，有利于搜索算法的完备性，但影响算法的搜索效率。h(x)项体现了搜索的深度优先趋势，有利于搜索效率的提高，但影响搜索算法的完备性，即有可能找不到问题的解。估价函数是针对具体问题构造的，在构造估价函数时，依赖于问题特性的启发函数h(x)的构造尤为

38、重要，一般可由节点x与目标节点Sg 的差异来决定。钻津狭次困戳恿呜须扁虐打记隋番缔驴叛贡屯济戌疽驰发伶汰曙掏泼逝患三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 3.3.2 3.3.2 最佳优先搜索最佳优先搜索最佳优先搜索基于估价函数f(x)的值来选择最有希望的节点作为下一个要扩展的节点。估价函数值越小，希望程度越大。1. 1. 局部最佳优先搜索局部最佳优先搜索基本思想：当对某一个节点扩展之后，对它的每一个后继节点计算估价函数f(x)的值，并在这些后继节点的范围内，选择一个f(x)的值最小的节点，作为下一个要考察的节点。类似于深度优先搜索法。酝又懈睫敝堪

39、玖瞄姬疟饲湛梳翔饶绪逞氧裳轩孰水托妹诅弊椰妊胖袁仑边三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.73.7 局部最佳优先搜索算法局部最佳优先搜索算法(1)把初始节点So放入OPEN表，并计算估价函数f(So)。(2)如果OPEN为空，则问题无解，退出；否则转第(3)步。(3)从OPEN表中选取第一个节点(记作节点n，其估价函数值最小)移入CLOSED表。(4)考察节点n是否为目标节点，若是，则求得问题的解，退出；否则转第(5)步。(5)如果节点n可扩展，转(6)步；否则转第(2)步。(6)对节点n进行扩展，并对它的所有后继节点计算估价函数f

40、(x)的值，并按估价函数f(x)从小到大的顺序依次放入OPEN表的前端。(7)为每个后继节点设置指向n的指针。(8)转第(2)步。退仇呢奠贺捏天钳溉戊椒阐跃晶揉猫停考垒遗矢己儒襄卒预蟹叫楷沾抚坟三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 慈碘兰椭颇胆造奖妮仇问盒唆约梯敦插冻仟尖傲律彻秦翔酥桌堰钝耙克银三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 2 2全局最佳优先搜索全局最佳优先搜索基本思想：在确定下一个扩展节点时，在OPEN表中的全部节点中选择一个估价函数值f(x)最小的节点，作为下一个被考察的节点。类似于

41、宽度优先搜索。 刚背僧乔脚腥诛郎季涅仲肉游秉畴贾迷赣古哲泛关徘炭缸抚狰众湛化促加三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 算法算法3.83.8 全局最佳优先搜索算法全局最佳优先搜索算法(1)把初始节点So放入OPEN表，计算f(So)。(2)如果OPEN为空表，则问题无解，退出。(3)把OPEN表中第一个节点作为节点n移入CLOSED表。(4)考察节点n是否为目标节点，若是，则求得问题的解，退出；否则转第(5)步。(5)如果节点n可扩展，转第(6)步；否则转第(2)步。(6)对节点n进行扩展，并计算所有后继节点的估价函数f(x)的值，并为每个后继节

42、点设置指向n的指针。(7)把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价f(x)值从小到大的顺序排序。(8)转第(2)步。掣杖润拂掘吾劲段箱窝欠仍勤酋畴咆肘幕禄汤拷帅都棍俄九鸯诛膳瑶患炎三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 奖瓦聂靶笆祷旁考距秃喇萎歪狮龄暴芦汀曝篮序颗酸花罢哨普洞雷灶锅布三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 例例3.53.5 用全局最佳优先搜索方法求解八数码难题。初始状态图及目标状态图分别如下图(a)和(b)所示，试求由So转换为Sg的路径。 骏猩心完雇略温

43、娄恐搀呈碰忠屈寿斌楔败域狠佯鲸弛力打吝也跟孽眉乡摧三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 解：首先定义一个估价函数： f(x)=d(x)+h(x)d(x)：表示节点x在搜索树中的深度；h(x)：表示与节点x对应的棋盘中，与目标节点Sg所对应的棋盘中棋子位置不同的个数。算奖粟记屉祈秉青餐澜虎副穴胆娜涣法呢垒肪慰唆温赐宾窝他绵冒劫路约三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 1. A*算法的定义A*算法也是一种启发式搜索方法，它对算法算法3.13.1中的扩展节点选择方法做了一些限制，选用了一个比较特殊的估

44、价函数。这时的估价函数f(x)=g(x)+h(x)是对下列函数 f*(x)=g*(x)+h*(x) 的一种估计或近似。即： f(x)是对f*(x)的一种估计； g(x)是对g*(x)的估计； h(x)是对h*(x)的估计。3.3.3 A3.3.3 A* *算法算法玫塞隆荷华批搅劳诌必申实秋锤回岩榔空彤挨衫关劣江悟身妇射破寇英滇三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 g*(x)：从节点So到节点x之间最佳路径的实际代价。h*(x)：从x节点到目标节点Sg的最佳路径的代价。f*(x)：表示从节点So到节点x的一条最佳路径的实际代价加上从节点x到目标节

45、点Sg的一条最佳路径的代价之和。g(x) ：从初始节点So到节点x的路径代价，显然恒有g(x)g*(x)。h(x) ：依赖于有关问题领域的启发信息。孩砒震皖省志纽悉命萌郑吉袜捉蚊帝冈饺扒扶错冻纠沸攘恩配投耸泛胰不三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 定定义义3.13.1 如果在一般状态空间图的搜索算法(算法3.1)中的第(8)步，依据估价函数 f(x)=g(x)+h(x) 对OPEN表中的节点进行排序，并且要求启发函数h(x)是h*(x)的一个下界，即h(x)hh(x)h* *(x)(x)，则这种状态空间图的搜索算法就称为A A* *算法算法。

46、如果对启发函数h(x)，不限制条件h(x)h*(x)，则这种状态空间图的搜索算法称为A A算法算法。铱待湍抱献划椰颓奈糖傅澄歇讨滚便误饯共畏缉爹镭局涕文剔厕港盾侍羊三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 在启发式搜索中，估价函数f(x)如果定义得不好，则搜索算法不一定能找到问题的解。即便找到解，也不一定是最优解。A*启发式搜索算法使用了特殊定义的估价函数，它要求启发 函 数 h(x)是 h*(x)的 下 界 ， 即 对 所 有 的 x均 有 ： h(x)h*(x) 。这一要求十分重要，它能保证A*算法找到最优解。A*算法是对算法3.1中的扩展节点

47、选择方法作了限制，它可以使问题的求解更快速、更有效。霖吾撅芬既卜乘辛骋异睹佰姚袋葵咬啼尚诣撕缩旧迭姚抄腹涌猫骗薪坛盗三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 2. A*算法的性质(1)(1)可采纳性可采纳性即对于可求解的状态空间图(从初始节点到目标节点有路径存在)来说， A*算法能在有限步内终止，并找到最优解。讫穆薪每奄春柏悯乏痈拓菲怪斟掌莆微耶卵宏术粱复昌肾崔剪屈汐捶捐臼三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 (2)(2)单调性单调性当启发函数h(x)满足下面限制条件时，所扩展的节点序列估价函数f(

48、x)的值是非递减的，从而减少对OPEN表或CLOSED表的检查和调整，排序简单，提高搜索效率。对所有的节点xi，如果xj是节点xi的任意子节点，有h(xh(xi i)-h(x)-h(xj j)C(x)C(xi i，x xj j) )。其中C(xi，xj)是节点xi到节点xj的有向边代价。目标节点Sg 的启发函数的值为0，即h(Sh(Sg g)=0)=0。臂宁塘吝蝎邱饿罚名长乎扼吏纠浚栗宁关台杭绿页绘畜冤推柿动鳞秋撰宏三章状态空间搜索策略三章状态空间搜索策略第三章第三章 状态空间搜索策略状态空间搜索策略 (3)(3)信息性信息性A*算法的搜索效率主要取决于启发函数h(x)，在满足h(x)h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它携带与求解问题相关的启发信息越多，搜索过程就会在启发信息指导下朝着目标节点前进，所扩展的节点数就不会太多，走的弯路少，搜索效率就会提高。咆傀镶肪掏抄帛驳彤姨颠转朽汹爱丘汉李嘎稀翘识迄千批有悄万腔帆又恢三章状态空间搜索策略三章状态空间搜索策略