第二章搜索—基于状态空间的搜索.ppt

,第 二章,用以搜索状态空间的结构与策略,用以搜索状态空间的结构与策略,第二章-2,内容,2.0 简介 2.1 图论 2.2 问题状态空间的表示 2.3 状态空间搜索的方向 2.4 一般图搜索 2.5 常见的盲目式搜索技术,用以搜索状态空间的结构与策略,第二章-3,2.0 简介,什么是问题？,?,用以搜索状态空间的结构与策略,第二章-4,2.0 简介,问题（现代认知心理学）：在给定信息和目标状态之间有某些障碍需要加以克服的情境。给定：有关问题条件的描述，即问题的起始状态；目标：有关构成问题结论的描述，即问题的目标状态；障碍：无法直接到达目标，必须通过一定的思维活动才 能找到答案，达到目标状态。问题解决（信息加工观点）：就是搜索问题空间，寻找一条从起始状态通向目标状态的通路，或使用算子使起始状态逐步过渡到目标状态。按解决问题所需的领域特有知识的多寡，问题求解系统可 以划分为两大类：知识贫乏系统：依靠搜索技术去解决问题。知识丰富系统：依靠推理的识别技术解决问题。,用以搜索状态空间的结构与策略,第二章-5,2.0 简介,搜索人工智能所研究的对象大多是属于结构不良或非结构化的问题。对于这些问题，一般很难获得其全部信息，更没有现成的算法可供求解使用。只能依靠经验，利用已有知识逐步摸索求解。根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程搜索。对那些结构性能较好，理论上有算法可依的问题，如果问题或算法的复杂性较高（如按指数形式增长），由于受计算机在时间和空间上的限制，也无法付诸实用。组合爆炸问题。,用以搜索状态空间的结构与策略,第二章-6,2.0 简介,搜索的分类根据搜索过程是否使用启发式信息盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，因此这种搜索具有盲目性。启发式搜索：搜索过程中加入与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。根据问题的表示方式状态空间搜索：基于问题到状态空间表示求解问题所进 行的搜索。与或树搜索：基于问题的与或树表示利用问题归约 法来求解问题时所进行的搜索。,第六章,用以搜索状态空间的结构与策略,第二章-7,内容,2.0 简介 2.1 图论 2.2 问题状态空间的表示 2.3 状态空间搜索的方向 2.4 一般图搜索 2.5 常见的盲目式搜索技术,用以搜索状态空间的结构与策略,第二章-8,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,用以搜索状态空间的结构与策略,第二章-9,2.1 图论,例1：从某王姓家族的四代中找王A的后代且其寿命为X的人,用以搜索状态空间的结构与策略,第二章-10,2.1 图论,例2：哥尼斯堡七桥问题（瑞士数学家-欧拉）,用以搜索状态空间的结构与策略,第二章-11,2.1 图论,图节点和连接这些节点的弧的集合。,带标签的有向图,用以搜索状态空间的结构与策略,第二章-12,2.1 图论,有根图具有一个唯一节点（根），从这个节点到图中所有节点都存在一条路径。,用以搜索状态空间的结构与策略,第二章-13,2.1 图论,树两个节点之间最多有一条路径的图。,用以搜索状态空间的结构与策略,第二章-14,内容,2.0 简介 2.1 图论 2.2 问题状态空间的表示 2.3 状态空间搜索的方向 2.4 一般图搜索 2.5 常见的盲目式搜索技术,用以搜索状态空间的结构与策略,第二章-15,2.2 问题状态空间的表示,状态空间表示法用来表示问题及其搜索过程的一种形式化方法。状态操作状态空间 什么是状态？状态（State）是表示问题求解过程中每一步问题状况的数据结构：SkSk0，Sk1，对每一个分量给予确定的值时，得到一个具体的状态。任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。,用以搜索状态空间的结构与策略,第二章-16,2.2 问题状态空间的表示,什么是操作？操作（Operator）算符当对一个问题状态使用某个可用操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。,用以搜索状态空间的结构与策略,第二章-17,2.2 问题状态空间的表示,什么是状态空间？状态空间（State space）用来描述一个问题的全部状态以及这些状态之间的相互关系。状态空间常用一个三元组表示：（S，F，G）S：为问题的所有初始状态的集合；F：为操作的集合；G：为目标状态的集合。,问题求解过程实际上是一个搜索过程,用以搜索状态空间的结构与策略,第二章-18,2.2 问题状态空间的表示,【例2.1】二阶Hanoi问题设有三根钢针，它们的编号分别是1号、2号和3号;在初始情况下，l号钢针上穿有A、B两个金片;A比B小，A位于B的上面;要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。如何将A、B两个金片移到2号或三号钢针上面？,用以搜索状态空间的结构与策略,第二章-19,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,用以搜索状态空间的结构与策略,第二章-20,2.2 问题状态空间的表示,操作A(i,j)表示把金片A从第i号钢针移到j号钢针上；B(i,j)表示把金片B从第i号钢针移到j号钢针上；所有的操作共有12种：,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),用以搜索状态空间的结构与策略,第二章-21,2.2 问题状态空间的表示,状态空间9种状态、12种操作，得到二阶梵塔问题的状态空间图,用以搜索状态空间的结构与策略,第二章-22,2.2 问题状态空间的表示,用以搜索状态空间的结构与策略,第二章-23,2.2 问题状态空间的表示,【例2.2】猴子摘香蕉问题。,用以搜索状态空间的结构与策略,第二章-24,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)目标状态,用以搜索状态空间的结构与策略,第二章-25,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),用以搜索状态空间的结构与策略,第二章-26,2.2 问题状态空间的表示,状态空间图,用以搜索状态空间的结构与策略,第二章-27,2.2 问题状态空间的表示,【例2.3】8格拼图游戏,用以搜索状态空间的结构与策略,第二章-28,2.2 问题状态空间的表示,【例2.4】巡回推销员问题（货郎担问题TSP）,巡回推销员问题的一个实例,用以搜索状态空间的结构与策略,第二章-29,2.2 问题状态空间的表示,用以搜索状态空间的结构与策略,第二章-30,2.2 问题状态空间的表示,控制搜索复杂度的策略启发信息：比如“去访问最近的未访问过城市”来构建路径。,最近邻启发式搜索,用以搜索状态空间的结构与策略,第二章-31,2.2 问题状态空间的表示,思考题农夫带狼、山羊、菜过河问题船太小，农夫每次只能带一样过河；如果没有农夫看管，则狼要吃羊，羊要吃菜。设计一个过河方案，使得农夫、狼、山羊、菜都能不受损失地过河。画出相应的状态空间图,用以搜索状态空间的结构与策略,第二章-32,Sample crossings for the farmer,wolf,goat,and cabbage problem.,用以搜索状态空间的结构与策略,第二章-33,Portion of the state space graph of the farmer,wolf,goat,and cabbage problem,including unsafe states.,用以搜索状态空间的结构与策略,第二章-34,内容,2.0 简介 2.1 图论 2.2 问题状态空间的表示 2.3 状态空间搜索的方向 2.4 一般图搜索 2.5 常见的盲目式搜索技术,用以搜索状态空间的结构与策略,第二章-35,2.3 状态空间搜索的方向,数据驱动搜索（data-driven search）正向追索（forward chaining）问题求解程序从问题的给定事实和改变状态的合法移动和规则的集合入手。然后把规则应用到事实产生新的事实，接下来新的事实又被规则用来产生更多新的事实，搜索如此进行下去，直到产生满足目标条件的一条路径。目标驱动搜索（goal-driven search）反向追索（backward chaining）从求解的目标着手。先分析怎样使用合法的移动来产生这个目标，并求出要应用这些移动必须具备的条件。这些条件成为要搜索的新目标（子目标）。然后继续反向追溯相继的子目标，直至返回到问题中的事实。这样便找到了从问题到目标的移动会规则链。,用以搜索状态空间的结构与策略,第二章-36,2.3 状态空间搜索的方向,使用哪种搜索策略取决于问题本身的结构。,目标导向的搜索有效地裁减了无关的搜索路径,用以搜索状态空间的结构与策略,第二章-37,2.3 状态空间搜索的方向,数据导向的搜索把无关的数据和它们的结论裁减，然后从很多可能的目标中确定一个目标,使用哪种搜索策略取决于问题本身的结构。,用以搜索状态空间的结构与策略,第二章-38,内容,2.0 简介 2.1 图论 2.2 问题状态空间的表示 2.3 状态空间搜索的方向 2.4 一般图搜索 2.5 常见的盲目式搜索技术,用以搜索状态空间的结构与策略,第二章-39,2.4.1 一般图搜索的实现,图搜索问题（Question）问题求解程序能否被赋予可靠的机制（不犯任何错误）穿越状态空间达到预期的目标状态，并建立解路径？问题求解程序必须穿越空间的不同路径直到找到目标。回溯：系统试验地穿越状态空间的所有路径的一种技术。回溯搜索：从起始状态出发沿一条路径前进要么达到目标，要么到达一个“死端”。如果发现目标，退出搜索并返回解路径；如果到达一个死端，那么便回溯到路径上含有未分析过兄弟的最近节点，并沿这个分支继续下去。,用以搜索状态空间的结构与策略,第二章-40,2.4.1 一般图搜索的实现,用以搜索状态空间的结构与策略,第二章-41,2.4.1 一般图搜索的实现,对假想状态空间的回溯搜索,用以搜索状态空间的结构与策略,第二章-42,2.4.1 一般图搜索的实现,回溯搜索算法SL：状态列表，列出当前正在试验路径的状态。如果发现目标，那么SL便包含了解路径上状态的有序列表。NSL：新状态列表，含有等待评估的节点，也就是其后代还没有被产生和搜索的节点。DE：用来记录死端，列出已经发现其后代不包含目标的状态。如果再次遇到这些状态，它们会被检测为是DE中的元素并立即不再考虑。注意：在定义可用于一般情况（图而不是树）的回溯算法时，必须探测任何状态的多次出现以便不会再次进入这种状态而导致“死”循环。（如何实现？）,用以搜索状态空间的结构与策略,第二章-43,用以搜索状态空间的结构与策略,第二章-45,思考题,动态跟踪回溯算法。从状态A开始。记录NSL、SL、CS等的逐项值。,用以搜索状态空间的结构与策略,第二章-46,2.4.2 一般图搜索的过程,状态空间搜索的基本思想:,用以搜索状态空间的结构与策略,第二章-47,2.4.2 一般图搜索的过程,状态空间搜索的基本思想:先把问题的初始状态作为当前扩展节点对其进行 扩展，生成一组子节点;检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没出现，则再按照某种搜索策略从已生成的子 节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或 者没有可供扩展的节点为止。所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。,用以搜索状态空间的结构与策略,第二章-48,2.4.2 一般图搜索的过程,数据结构Open表：用于存放刚生成的节点，由于这些节点还没有进行扩展，因此 Open表也称为“未扩展节点表”。Closed表：用于存放已经扩展或将要扩展的节点，因此Closed表也称为“已扩展节点表”。符号S0：问题的初始状态。G：搜索过程所得到的搜索图。M：当前扩展节点新生成的且不为自己先辈的子节点集,用以搜索状态空间的结构与策略,第二章-49,2.4.2 一般图搜索的过程,状态空间的一般图搜索过程为：（1）把初始节点S0放入Open表，并建立目前仅包含S0的图 G；（2）检查Open表是否为空，若为空，则问题无解，失败退 出；（3）把 Open表的第一个节点取出放入Closed表，并记该节 点为节点n；（4）考察节点n是否为目标节点。若是则得到了问题的解，成功退出；（5）扩展节点n，生成一组子节点。把这些子节点中不是节 点n先辈的那部分子节点记入集合M，并把这些子节点 作为节点n的子节点加人G中。（6）针对M中子节点的不同情况，分别作如下处理：,用以搜索状态空间的结构与策略,第二章-50,2.4.2 一般图搜索的过程,（6）针对M中子节点的不同情况，分别作如下处理：对那些没有在G中出现过的M成员设置一个指向其父节 点（即节点n）的指针，并把它放入 Open表。对那些原来已在G中出现过，但还没有被扩展的M成 员，确定是否需要修改它指向父节点的指针。对于那些先前已在G中出现过，并已经扩展了的M成 员，确定是否需要修改其后继节点指向父节点的指 针。（7）按某种策略对Open表中的节点进行排序。（8）转第（2）步。,用以搜索状态空间的结构与策略,第二章-51,2.4.2 一般图搜索的过程,例如：扩展过程中某时刻的搜索图。黄色的节点位于Closed表中；紫色的节点位于Open表中；每条边的代价为1；,用以搜索状态空间的结构与策略,第二章-52,2.4.2 一般图搜索的过程,用以搜索状态空间的结构与策略,第二章-53,用以搜索状态空间的结构与策略,第二章-54,2.4.2 一般图搜索的过程,思考题：理解一般图搜索算法，OPEN表和CLOSE表的作用是什么？为何要标记从子节点到父节点的指针？举例说明对三类子节点处理方式的差异。某扩展中的搜索图如图所示，已被扩展的节点涂黑，待扩展的节点表示为空心圆圈，当前被扩展节点表示为双圆圈，并以虚线连到其生成的后继节点；设相邻节点间路径等长，请依据一般图搜索算法作指针设置和修改工作（并将虚线改为实线）。,用以搜索状态空间的结构与策略,第二章-55,内容,2.0 简介 2.1 图论 2.2 问题状态空间的表示 2.3 状态空间搜索的方向 2.4 一般图搜索 2.5 常见的盲目式搜索技术,用以搜索状态空间的结构与策略,第二章-56,内容,2.5 常见的盲目式搜索技术2.5.1 广度优先搜索2.5.2 深度优先搜索2.5.3 有界深度优先搜索2.5.4 代价树搜索2.5.4.1 代价树的广度优先搜索2.5.4.2 代价树的深度优先搜索,用以搜索状态空间的结构与策略,第二章-57,2.5.1 广度优先搜索,(宽度优先搜索)基本思想：先生成的节点先扩展；在第n层节点还没有全部搜索完之前，不进入第nl层节点的搜索；Open表中的节点first-in-first-out；Open表是队列。,用以搜索状态空间的结构与策略,第二章-58,2.5.1 广度优先搜索,广度优先搜索算法：（l）把初始节点S0放入Open表中；（2）如果Open表为空，则问题无解，失败退出；（3）把 Open表的第一个节点取出放入Closed表，并记该节点为n；（4）考察节点n是否为目标节点。若是，则得到问 题的解，成功退出；（5）若节点n不可扩展，则转第（2）步；（6）扩展节点 n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然 后转第（2）步。,用以搜索状态空间的结构与策略,第二章-59,用以搜索状态空间的结构与策略,第二章-60,2.5.1 广度优先搜索,Sg,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,用以搜索状态空间的结构与策略,第二章-62,2.5.1 广度优先搜索,第六次迭代时Open表和Closed表中的状态,用以搜索状态空间的结构与策略,第二章-63,2.5.1 广度优先搜索,【例】八数码难题（八格拼图游戏）操作：移动空格空格左移，空格上移，空相右移，空格下移问题：如何使用广度优先搜索策略寻找路径？,八数码难题,用以搜索状态空间的结构与策略,第二章-64,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,用以搜索状态空间的结构与策略,第二章-65,2.5.1 广度优先搜索,算法分析：广度优先搜索是一种完备策略，即只要问题有 解，它就一定可以找到解。广度优先搜索找到的解，一定是路径最短的解。广度优先搜索的主要缺点是盲目性较大，尤其是 当目标节点距初始节点较远时，将产生许多无用 的节点，因此其搜索效率较低。,用以搜索状态空间的结构与策略,第二章-66,内容,2.5 常见的盲目式搜索技术2.5.1 广度优先搜索2.5.2 深度优先搜索2.5.3 有界深度优先搜索2.5.4 代价树搜索2.5.4.1 代价树的广度优先搜索2.5.4.2 代价树的深度优先搜索,用以搜索状态空间的结构与策略,第二章-67,2.5.2 深度优先搜索,基本思想：采用首先扩展最新产生的(即最深的)节点的策略；搜索过程:从初始节点开始，在其子节点中选择一个最新生成的 节点进行考察；如果该子节点不是目标节点且可以扩展，则扩展该子 节点；再在此子节点的子节点中选择一个最新生成的节点进 行考察；依此向下搜索，直到某个子节点既不是目标节点，又 不能继续扩展时，才选择其兄弟节点进行考察。,Open表中的节点first-in-last-outOpen表是一种栈结构,用以搜索状态空间的结构与策略,第二章-68,2.5.2 深度优先搜索,深度优先搜索算法：（l）把初始节点S0放人Open表中；（2）如果Open表为空，则问题无解，失败退出；（3）把Open表的第一个节点取出放入Closed表，并记该节点为n；（4）考察节点n是否为目标节点。若是，则得到问 题的解，成功退出；（5）若节点n不可扩展，则转第（2）步；（6）扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针，然 后转第（2）步。,用以搜索状态空间的结构与策略,第二章-69,2.5.2 深度优先搜索,用以搜索状态空间的结构与策略,第二章-70,【例2.6】八数码难题。,2 8 3 47 6 5,S0,1,深度优先搜索,用以搜索状态空间的结构与策略,第二章-72,2.5.2 深度优先搜索,分析：搜索一旦进入某个分支，就将沿着这个分支一直 进行下去；如果目标恰好在这个分支上，则它可 以很快找到解。但是，如果目标不在这个分支 上，且该分支是一个无穷分支，则搜索过程就不 可能找到解。深度优先搜索是一种不完备的盲目搜索策略。即使问题有解，它也不一定能够找到解 即使在能找到解的情况下，按深度优先找到的解 也不一定是路径最短的解。搜索所用的时间取决于目标位于树种的位置。,用以搜索状态空间的结构与策略,第二章-73,内容,2.5 常见的盲目式搜索技术2.5.1 广度优先搜索2.5.2 深度优先搜索2.5.3 有界深度优先搜索2.5.4 代价树搜索2.5.4.1 代价树的广度优先搜索2.5.4.2 代价树的深度优先搜索,用以搜索状态空间的结构与策略,第二章-74,2.5.3 有界深度优先搜索,由来：两种搜索策略都存在缺点。基本思想：一种较好的折衷办法是在深度优先策略中引入深度限制，即采用有界深度优先搜索。有界深度优先搜索过程总体上按深度优先策略进行，但对搜索深度需要给出一个深度限制dm。当搜索深度达到了dm，但还没有找到目标时，就停止该分支的搜索，换到另外一个分支进行搜索。,用以搜索状态空间的结构与策略,第二章-75,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）步。,用以搜索状态空间的结构与策略,第二章-76,2.5.3 有界深度优先搜索,用以搜索状态空间的结构与策略,第二章-77,【例2.7】八数码难题。（设深度限制成dm=4）,解路径为:So：l11 12 13 14：Sg,用以搜索状态空间的结构与策略,第二章-78,2.5.3 有界深度优先搜索,用以搜索状态空间的结构与策略,第二章-79,分析：在有界深度优先搜索算法中，深度限制dm是一个很重要的参数。当问题有解，且解的路径长度小于或等于dm时，则搜索过程一定能够找到解。但是当解的路径长度大于dm时，则搜索过程就找不到解。深度限制dm的值不能太大。当dm的值太大时，搜索过程将产生过多的无用节点，既浪费计算机资源，又降低了搜索效率。,2.5.3 有界深度优先搜索,为解决上述问题，可采用如下改进办法：先任意给定一个较小的数作为dm，然后按有界深度优先算法进行搜索，若在此限度内找到了问题的解，则算法结束；若在此限度内没有找到问题的解，且 Closed表中仍有待扩展节点，就将这些节点送回 Open表，同时增大深度限制dm，继续向下搜索。如此不断增大dm，只要问题有解，就一定能够找到它。（迭代加深的深度优先搜索）,用以搜索状态空间的结构与策略,第二章-80,内容,2.5 常见的盲目式搜索技术2.5.1 广度优先搜索2.5.2 深度优先搜索2.5.3 有界深度优先搜索2.5.4 代价树搜索2.5.4.1 代价树的广度优先搜索2.5.4.2 代价树的深度优先搜索,用以搜索状态空间的结构与策略,第二章-81,2.5.4 代价树搜索,基本思想：在前面讨论的各种搜索策略中，实际上都作了一种假设，认为状态空间中各边的代价都相同，且都为一个单位量。从而，可用路径的长度来代替路径的代价。对许多实际问题，这种假设是不现实的，它们的状态空间中的各个边的代价不可能完全相同。为此，我们需要在搜索树中给每条边都标上其代价。这种边上标有代价的树称为代价树。在代价树中，最小代价的路径和最短路径（即路径长度最短）是有可能不同的。最短路径不一定是最小代价路径；最小代价路径不一定是最短路径。代价树搜索的目的是为了找到最佳解，即找到一条代价最小的解路径。,用以搜索状态空间的结构与策略,第二章-82,2.5.4 代价树搜索,代价树中，节点代价的定义：g（n）：表示从初始节点S0到节点n的代价；c（n1，n2）：表示从父节点n1到其子节点n2的代价；g（n2）=g（n1）c（n1，n2）代价树的搜索策略:代价树的广度优先搜索代价树的深度优先搜索,用以搜索状态空间的结构与策略,第二章-83,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）步。,用以搜索状态空间的结构与策略,第二章-84,2.5.4.1 代价树的广度优先搜索,用以搜索状态空间的结构与策略,第二章-85,2.5.4.1 代价树的广度优先搜索,【例】城市交通问题。设有5个城市，它们之间的交通线路如图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从A市出发到E市，费用最小的交通路线。,A,C,D,E,B,3,2,3,4,4,5,转化成代价树,用以搜索状态空间的结构与策略,第二章-86,2.5.4.2 代价树的深度优先搜索,代价树的深度优先搜索和代价树的广度优先搜索的区别在于：每次选择最小代价节点的方法不同。广度优先搜索每次都是从Open表的全体节点中选择一个代价最小的节点。深度优先搜索则是从刚扩展的子节点中选择一个代价最小的节点。,