人工智能搜索策略 优质ppt课件.ppt

搜 索 策 略,搜索问题，人工智能的一个基本问题,在二十世纪五十年代人工智能概念的提出至今，人工智能界已对搜索技术开展了大量研究，取得了丰硕的成果。 搜索是人工智能的一个基本问题，是推理不可分割的一部分。一个问题的求解过程其实就是搜索过程，所以搜索实际上就是求解问题的一种方法。Nilsson把搜索列为人工智能研究中的四个核心问题之一。本部分将讨论目标状态和最优路径的确定，以及如何从初始状态经过变换得到目标状态等，将在各节分别讨论一些通用的搜索策略，以及状态空间搜索和树搜索策略。最后简要介绍智能搜索算法的效率和约束满足问题。,3.1 基本概念（Basic Conception）,现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。 在这一过程中，所要解决的问题是如何寻找可利用的知识，即如何确定推理路线，才能使在付出尽量少的代价下把问题圆满解决。 如果存在多条路线可实现对问题的求解，那就又存在着这样的问题，即如何从这多条求解路线中，选出一条使它的求解代价最小，以提高求解程序的运行效率。,根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条解决问题的推理路线的过程，就称为搜索。1.搜索包含两层含义找到从初始事实到问题最终答案的一条推理路线;找到的这条路线是时间和空 间复杂度最小的求解路线。举一个具体的例子 实现一个能够中国象棋下棋的程序。,3.1 基本概念（Basic Conception）3.1.1 什么是搜索 (Whats search),2.搜索的种类(The type of search) 搜索分为盲目搜索和启发式搜索两种盲目搜索又称无信息搜索，也就是说，在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。这就使得这样的搜索带有盲目性，效率不高。盲目搜索只用于解决比较简单的问题。启发式搜索又称有信息搜索，它是指在搜索求解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。,3.1.1 什么是搜索 (Whats search),问题求解系统可在两种基本情况下运用启发式策略：一个问题由于在问题陈述和数据获取方面固有的模糊性，可能会使它没有一个确定的解，即它是一个模糊系统。虽然一个问题可能有确定解，但是求解过程中的搜索代价将令人难以接受，在很多问题中，其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。在这种情况下，穷尽式搜索策略如宽度优先和深度优先搜索，在一个给定的较实际的时空内很可能得不到最终的解，而启发式策略则通过引导搜索向最有希望的方向进行来降低搜索复杂度。通过仔细考虑，删除某些状态及其后裔，启发式策略可以消除组合爆炸，并得到令人能接受的解。,3.1.1 什么是搜索 (Whats search),3.1.1 什么是搜索 (Whats search),启发式策略的缺点： 极易出错。在解决问题过程中启发仅仅是下一步将要采取措施的一个猜想，它常常根据经验和直觉来判断。 由于启发式搜索只利用特定问题的有限的信息，如当前open表中状态的描述及其之间的关系，要想准确地预测下一步在状态空间中采取的具体的搜索行为是很难办到的。一个启发式搜索可能得到一个次最佳解，也可能一无所获，这是启发式搜索固有的局限性，而这种局限性不可能由所谓更好的启发式策略或更有效的搜索算法来彻底消除。,3.1.2 适合于搜索的知识表示方法,状态空间表示法： 算符、状态、状态空间与或树表示法： 分解、等价变化；本原问题、端节点与终止节点、可解节点、不可解节点、解树,状态空间搜索策略分类：盲目搜索 按事先规定好的路线进行搜索，不使用与问题有关的启发性信息；适用于其状态空间图是树状结构的一类问题。它包括广度优先搜索、深度优先搜索、有界深度优先搜索、代价树的广度优先搜索以及代价树的深度优先搜索。启发式搜索搜索过程中使用与问题有关的启发性信息，并以启发性信息指导搜索过程；可以高效地求解结构复杂的问题。它包括局部择优搜索、全局择优搜索和A*算法。,3.2 状态空间的搜索策略,3.2.1 状态空间的一般搜索过程,1.状态空间图 状态空间图是一个有向图，当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。如果从状态空间图的角度来看，则对问题的求解就相当于 在有向图上寻找一条从某一节点(初始状态节点)到另一节点(目标状态节点)的路径。,3.2.1 状态空间的一般搜索过程,2.状态空间搜索法求解问题的基本思想 首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择适当的算符作用于当前状态，生成一组后继状态(或称后继节点)， 然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。,3.状态空间的搜索过程需要的两个数据结构 OPEN表：用于存放刚生成的节点，这些节点也是待扩展的，所以OPEN表也称为未扩展节点表； CLOSED表：CLOSED表则是用来存放将要扩展或已经扩展的节点，所以它被称为已扩展节点表。4.状态空间的一般搜索过程描述如下:把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；检查OPEN表是否为空，若为空则问题无解，退出。把 OPEN 表的第一个节点取出并放入 CLOSED 表，并记该节点为节点 n；检查节点 n 是否是目标节点，如果是目标节点，则说明得到了问题的解，过程成功退出，并返回从节点 n 逆向回溯到S0得出的路径；,3.2.1状态空间的一般搜索过程,扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中。 针对M中子节点的不同情况，分别进行如下处理：对于那些未曾在G 图中出现过的 M 成员设置一个指向父节点（即节点n）的指针，并把它们加入 OPEN 表对于那些先前已在G图中出现过的M成员，确定是否需要修改它指向父节点的指针。对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针。按某种搜索策略对OPEN表中的节点进行排序。转第2）步。,3.2.1状态空间的一般搜索过程,S9扩展之后生成的子节点有S1,S6,S12,S13。但是，S1是S9的祖先节点，所以S9的子集M=S6,S12,S13其中，S13满足第1种情况；S12满第2种情况；S6满足第3种情况。,下面对上述过程作一些说明：1) 上述过程是状态空间的一般搜索过程，具有通用性，在此之后讨论的各种搜索策略都可看作是它的一个特例。各种搜索策略的主要区别是对 OPEN 表中节点排序的准则不同。 例如广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。2) 一个节点经一个算符操作后一般只生成一个子节点，但适用于一个节点的算符可能有多个，此时就会生成一组子节点。在这些子节点中可能有些是当前扩展节点 ( 即节点n)的父节点，祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。余下的子节点记作集合M，并加入图 G 中。这就是第 5) 步要说明的意思。3) 一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节点被再次生成。此时，它究竟应作为哪个节点的后继节点呢？一般由原始节点到该节点路径上所付出的代价来决定，哪条路径付出的代价小，相应的节点就作为它的父节点。,4) 通过搜索所得到的图称为搜索图，由搜索图中的所有节点及反向指针(在第6)步形成的指向父节点的指针)所构成的集合是一棵树，称为搜索树。5) 在搜索过程中，一旦某个被考察的节点是目标节点 (第5)步)就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成的，而路径由第7) 步形成的反向指针指定。6) 如果在搜索中一直找不到目标节点，而且 OPEN 表中不再有可供扩展的节点，则搜索失败，在第3) 步退出。7) 由于盲目搜索仅适用于其状态空间是树状结构的问题，因此对盲目搜索而言，不会出现一般搜索过程第6) 步中，两点的问题，每个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指针方向。,5.搜索过程举例：,3.2.1状态空间的一般搜索过程,实心黑点代表已扩展了节点，它们位于CLOSED表上；空心圆圈代表未扩展的节点，它们位于OPEN表上；有向边旁边的箭头是指向父节点的指针，它们是在第 6) 步形成的。,假设现在要扩展节点 1，并且只生成单一的后继节点 2 。但是目前节点 2 已有父节点 3，即节点 2 在先前扩节点 3 时已被生成了，现在又作为节点 1 的后继节点被再次生成。,一. 广度优先搜索,广度优先搜索又称为宽度优先搜索。基本思想是：从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前， 不对第n+1层的节点进行扩展。OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。,3.2.2 状态空间的盲目搜索,广度优先搜索过程:1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)；2) 如果OPEN是个空表，则没有解，失败退出；否则继续；3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中；4) 扩展节点n。如果没有后继节点，则转向上述第 2) 步；5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针；6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第2)步。,一. 广度优先搜索,广度优先搜索示意图：,一. 广度优先搜索,一. 广度优先搜索,广度优先搜索举例：重排九宫问题。在33的方格棋盘上放置分别标有数字1,2,3,4,5,6,7,8的八张牌，初始状态为S0，目标状态为Sg，如图所示。可用的算符有四种。按照左上右下的顺序遍历,初始状态,目标状态,解路径：S0-3-8-16-26,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,缺点：盲目性大，当目标节点距离初始节点较远时将会产生许多无用节点；搜索效率低。优点：是完备的。,深度优先搜索 在深度优先搜索中，我们首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。 对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。,二、 深度优先搜索,示意图,例：按深度优先搜索生成的八数码难题搜索树其算法的基本思想与广度优先搜索类似，唯一不同就在第5)步中： 把n的所有后继节点放到OPEN表的首部，并提供从这些后继节点回到n的指针。,缺点：有可能陷入无穷分支。算法是不完备的。,基本思想：对深度优先搜索引入搜索深度的界限（设为dm）当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。,三、有界深度优先搜索,有界深度优先搜索算法如下：把起始节点S0放到未扩展节点OPEN表中，置S0的深度为d(S0)=0；如果OPEN为一空表，则失败退出；OPEN表的第一个节点(节点n)从OPEN表移到CLOSED表；考查结点n是否为目标节点。若是，则求得了问题的解，退出；如果节点n的深度d(节点n)等于最大深度(dm)，则转2)；若节点n不可扩展，则转第2)步；扩展节点n,将其子节点放入OPEN表的首部，并为其配置指向父节点的指针。然后转第2)步。,三、有界深度优先搜索,设深度界限 dm4，用有界深度优先搜索方法求解图,由于解的路径长度事先难以预料，所以要恰当地给出dm的值是比较困难的，且所求出的解也不一定是最优解。改进方法：先任意给定一个较小的数作为dm ，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限dm仍未发现目标节点，并且CLOSED表中仍有待扩展节点时就将这些节点送回OPEN表，同时增大深度界限，继续向下搜索。如此不断地增大dm，只要问题有解，就一定可以找到它。但此时找到的解不一定是最优解。,代价树 边上标有代价(或费用)的树称为代价树。 g(x)表示从初始节点S0到节点x的代价；c(x1,x2)表示从父结点x1到子节点x2的代价。 g(x2)=g(x1)+ c(x1,x2)代价树广度优先搜索的基本思想: 每次从 OPEN 表中选择节点往 CLOSED 表传送时，总是选择其代价为最小的节点。也就是说，OPEN 表中的节点在任一时刻都是按其代价从小至大排序的，代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置上。,四、代价树广度优先搜索,搜索过程如下：(1) 把初始节点 S0 放入OPEN 表，令 g(S0)=0 。(2) 如果 OPEN 表为空，则问题无解，退出。(3) 把 OPEN 表的第一个节点 ( 记为节点 i) 取出放入 CLOSED 表。(4) 考察节点 i 是否为目标节点。若是，则求得了问题的解，退出。(5) 若节点 i 不可扩展，则转第 (2) 步。(6) 扩展节点 i，将其子节点放入 OPEN 表中，且为其配置指向父节点的指针；计算各子节点的代价，并按各节点的代价对 OPEN 表中的全部节点进行排序 (按从小到大的顺序)，然后转第 (2) 步。,如果问题有解，该搜索过程一定可以求得它并且求出的是最优解。举例：五城市间的交通路线图，A 城市是出发地，E 城市是目的地，两城市间的交通费用 ( 代价 ) 如图中数字所示。求从 A 到 E 的最小费用交通路线。,四、代价树广度优先搜索,5,为了应用代价树的广度优先搜索方法求解此问题，需先将交通图转换为代价树。 转换的方法是：从起始节点 A 开始，把与它直接相邻的节点作为它的子节点。对其它节点也做相同的处理。但若一个节点已作为某节点的直系先辈节点时，就不能再作为这个节点的子节点。 另外，目的节点不再扩展了。,g(x)表示从初始节点S0到节点x的代价；c(x1,x2)表示从父结点x1到子节点x2的代价。代价树深度优先搜索的过程：(1) 把初始节点 S0 放入 OPEN 表中。(2) 如果 OPEN 表为空，则问题无解，退出。(3) 把 OPEN 表的第一个节点 ( 记为节点 n) 取出放入 CLOSED 表。(4) 考察节点 n 是否为目标节点。若是，则求得了问题的解，退出。(5) 若节点n不可扩展，则转第 (2) 步。(6) 扩展节点n，将OPEN 表中所有节点按边代价从小到大的顺序排列，并为各子节点配置指向父节点的指针，然后转第 (2) 步。,四、代价树广度优先搜索,g(x)表示从初始节点S0到节点x的代价；c(x1,x2)表示从父结点x1到子节点x2的代价。代价树深度优先搜索的过程：(1) 把初始节点 S0 放入 OPEN 表中。(2) 如果 OPEN 表为空，则问题无解，退出。(3) 把 OPEN 表的第一个节点 ( 记为节点 n) 取出放入 CLOSED 表。(4) 考察节点 n 是否为目标节点。若是，则求得了问题的解，退出。(5) 若节点n不可扩展，则转第 (2) 步。(6) 扩展节点n，将其子节点按边代价从小到大的顺序放到 OPEN 表的首部，并为各子节点配置指向父节点的指针，然后转第 (2) 步。,五、代价树深度优先搜索,五、代价树深度优先搜索,在代价树的广度优先搜索中，每次都是从 OPEN表的全体节点中选择一个代价最小的节点送入 CLOSED 表进行考察；代价树的深度优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入 CLOSED 表进行考察。,一般情况下这两种方法得到的结果不一定相同。另外，由于代价树的深度优先搜索有可能进入无穷分支路径，因此它是不完备的。,前面讨论的搜索方法都是非启发式搜索，它们或者是按事先规定的路线进行搜索，或者是按已经付出的代价决定下一步要搜索的节点。 它们的一个共同特点是都没有利用问题本身的特性信息，在决定要被扩展的节点时，都没有考虑该节点在解的路径上的可能性有多大，它是否有利于问题求解以及求出的解是否为最优解等。 因此这些搜索方法都具有较大的盲目性，产生的无用节点较多，搜索空间较大，效率不高。,3.2.3状态空间的启发式搜索,启发式搜索要用到问题自身的某些特性信息，以指导搜索朝着最有希望的方向前进。由于这种搜索针对性较强，因而原则上只需要搜索问题的部分状态空间，效率较高。 启发性信息：可用于指导搜索过程，且与具体问题求解有关的控制性信息陈述性启发信息：一般被用于更准确、更精练地描述状态，使问题的状态空间缩小，如待求问题的特定状况等属于此类信息。过程性启发信息：一般被用于构造操作算子，使操作算子少而精，如一些规律性知识属于此类信息。控制性启发信息：它是关于表示控制策略方面的知识，包括协调整个问题求解过程中所使用的各种处理方法、搜索策略、控制结构等有关的知识。,估价函数 用于估价节点重要性或“有希望”程度的函数称为估价函数。其一般形式为：f(x)=g(x)+h(x)g(x) 为从初始节点 S0 到节点 x 已经实际付出的代价；h(x) 是从节点 x 到目标节点 S 的最优路径的估计代价，它体现了问题的启发性信息，其形式要根据问题的特性确定。它可以是节点 x 到目标节点的距离或差异，可以是x格局的得分，也可以是节点 x 处于最优路径上的概率等等。h (x) 称为启发函数。,3.2.3状态空间的启发式搜索,估价函数 f(z) 表示从初始节点经过节点 Z 到达目标节点的最优路径的代价估计值，它的作用是估价 OPEN 表中各节点的重要程度，决定它们在 OPEN 表中的次序。 g(z) 指出了搜索的横向趋势，它有利于搜索的完备性，但影响搜索的效率。如果我们只关心到达目标节点的路径，并且希望有较高的搜索效率，则 g(z) 可以忽略，但此时会影响搜索的完备性。 在确定 f(z) 时，要权衡各种利弊得失，使 g(z) 与 h (z) 各占适当的比重。,5.2.3状态空间的启发式搜索,举例：对 8 数码问题，评估函数可以表示为：f(z) =d(z)+ (z) d(z)表示节点 Z 在搜索树中的深度， (z)表示节点 Z 不在目标状态中相应位置的数码个数，(z)就包含了问题的启发式信息。一般来说，某节点(z) 越大，即“不在目标位”的数码个数越多，说明它离目标节点越远。 对初始节点 S0，由于 d(S0)=0，(S0) =3，因此f(S0)=3。,3.2.3状态空间的启发式搜索,目标状态,初始状态,几种启发式算法,1. 局部择优搜索是对深度优先搜索方法的一种改进。基本思想：当一个节点被扩展以后，按f(x)对每一个子节点计算估价值，并选择最小者作为下一个要考查的节点，由于它每次都只是在子节点的范围内选择下一个要考查的节点，范围比较窄，所以称为局部择优搜索。,搜索过程：(1)把初始节点s0放入OPEN表，计算f(s0)；(2)如果OPEN表为空，则问题无解，退出；(3)把OPEN表的第一个节点（记为n）取出放入CLOSED表；(4)考查节点n是否为目标节点。若是，则求得了问题的解，退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，用估价函数f(x)计算每个子节点的估价值，并按估价值从大到小的顺序依次放到OPEN表的首部，为每个子节点配置指向父节点的指针。然后转第(2)步。,几种启发式算法,f(z) =d(z)+ (z)d(z)表示节点 Z 在搜索树中的深度，(z)表示节点 Z 不在目标状态中相应位置的数码个数,目标状态,初始状态,几种启发式算法,深度优先搜索、代价树的深度优先搜索以及局部择优搜索的相同点：都是以子节点作为考察范围。不同点：它们选择节点的标准不一样。深度优先搜索以子节点的深度作为选择标准，后生成的子节点先被考察；代价树深度优先搜索以各子节点到父节点的代价作为选择标准，代价小者优先被选择；局部择优搜索以估价函数的值作为选择标准，哪一个子节点的f值最小就优先被选择。另外，在局部择优搜索中，若令f(x)=g(x),则局部择优搜索就成为代价树的深度优先搜索；若令f(x)=d(x)，这里d(x)表示节点x的深度，则局部择优搜索就成为深度优先搜索。,2.全局择优搜索每次总是从OPEN表的全体节点中选择一个估价值最小的节点。搜索过程：(1)把初始节点S0放入OPEN表，计算f(s0)；(2)如果OPEN表为空，则搜索失败，退出；(3)把OPEN表中的第一个节点（记为n）从表中移出放入CLOSED表；(4)考查节点n是否为目标节点。若是，则求得了问题的解，退出；(5)若节点n不可扩展，则转第（2）步；(6)扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小至大的顺序进行排序；(7)转第（2）步。,几种启发式算法,f(z) =d(z)+ (z)d(z)表示节点 Z 在搜索树中的深度，(z)表示节点 Z 不在目标状态中相应位置的数码个数,目标状态,初始状态,如果使一般搜索过程满足如下限制，则它就成为A*算法：（1）把OPEN表中的节点按估价函数f(x)=g(x)+h(x)的从小到大进行排序；（2）代价函数g(x)是对g*(x)的估计， g*(x)0。 g*(x)是从初始节点S0到节点x的最小代价；（3）启发函数h(x)是h*(x)的下界，即对所有的x均有：h(x)h*(x) 。h*(x)是从节点x到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。通过n的最佳路径：f*(n)=g*(n)+h*(n)最小的路径，即从S出发，通过节点n的，到达目标节点的代价和最小的路径。,3. A*算法( 最佳图搜索算法),g(x)比较容易得到，它实际上就是从初始节点S0到节点x的路径代价，恒有g(x) g*(x) ,而且在算法执行过程中随着更多搜索信息的获得，g(x)的值呈下降的趋势。h(x)的确定依赖于具体问题领域的启发性信息，其中h(x)h*(x)的限制是十分重要的，它可保证A*算法能找到最优解。,3.2.3状态空间的启发式搜索,从节点S0开始，经扩展得到x1与x2，且g(x1)=3， g(x2)=7；对x1扩展后得到X2与X3,此时g(x2)=6， g(x3)=5.显然，后来算出的g(x2)比先前算出的小。,3.2.3状态空间的启发式搜索,A*算法描述过程：(1) 把S放入OPEN表，记f(S)=h(S)，令CLOSED为空表。(2) 重复下列过程，直至找到目标节点止。若OPEN为空表，则宣告失败。(3) 选取OPEN表中未扩展过的具有最小f值的节点为最佳节点BESTNODE，并把它放入CLOSED表。(4) 若BESTNODE为一目标节点，则成功求得一解。(5) 若BESTNODE不是目标节点，则扩展之，产生后继节点集SUCCSSORi|i=1,2,n。(6) 对每个SUCCSSORi进行下列过程： (a) 建立从SUCCSSORi返回BESTNODE的指针。 (b) 计算g(SUCSSORi)=g(BESTNODE)+ c(BESNODE,SUCSSORi)。,(c)如果SUCCSSORi在OPEN表中,则比较新旧路径代价。如果从S0到SUCSSORi的新路径旧路径,则重新确定SUCSSORi的父辈节点为BESTNODE，记下较小代价g(SUCSSORi),并修正f(SUCSSORi)值。 (d)如果SUCCSSORi不在OPEN表中，在CLOSE表中,且从S0到SUCSSORi的新路径CLOSED表中的g(SUCCSSORi),则更新CLOSED表中的估价函数值并从CLOSED表中移出节点SUCCSSORi放入OPEN表中。 (e)如果SUCCSSORi不在OPEN表中也不在CLOSED表中时，求出SUCCSSORi的估价函数值并将其插入OPEN表中。(7) 按照估价函数值将OPEN表中的节点排序；(8) GO LOOP,后继节点表,A*算法的特性（1） A*算法可纳性 对于可解状态空间图（即从初始节点到目标节点有路径存在）来说，如果一个搜索算法能在有限步内终止，并且能找到最优解，则称该搜索算法是可纳的。 A*算法是可纳的，即它能在有限步内终止并找到最优解。（2） A*算法的最优性 A*算法的效率在很大程度上取决于h(x)，在满足h(x)h*(x)的前提下， h(x)的值越大越好。 h(x)的值越大，表明它携带的启发性信息越多，搜索时扩展的节点数越少，搜索的效率越高。（3）h(x)的单调性限制 在A*算法中，每当要扩展一个节点时都要先检查其子节点是否已在OPEN 表或CLOSED表中，有时还需要调整指向父节点的指针，这就增加了搜索的代价。如果对启发函数h(x)加上单调性限制，就可减少检查及调整的工作量，从而减少搜索代价。,3.3 与/或树的搜索策略,盲目搜索 包括与/或树的广度优先搜索、与/或树的深度优先搜索、与/或树的有界深度优先搜索启发式搜索包括与/或树的有序搜索、博弈树的启发式搜索。,用与/或树方法求解问题时，首先要定义问题的描述方法及分解或变换问题的算符，然后就可用它们通过搜索生成与/或树，从而求得原始问题的解。 由可解子节点来确定父节点、祖父节点等为可解节点的过程称为可解标示过程；由不可解子节点来确定其父节点、祖父节点等为不可解节点的过程称为不可解标示过程。 在与/或树的搜索过程中将反复使用这两个过程，直到初始节点(即原始问题)被标示为可解或不可解节点为止。,3.3 与/或树的搜索策略,(1) 把原始问题作为初始节点 S0，并把它作为当前节点。(2) 应用分解或等价变换算符对当前节点进行扩展。(3) 为每个子节点设置指向父节点的指针。(4) 选择合适的子节点作为当前节点，反复执行第 (2) 步和第 (3) 步，在此期间要多次调用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点为止。 由这个搜索过程所形成的节点和指针结构称为搜索树。与/或树搜索的目标是寻找解树，从而求得原始问题的解。,3.3.1 与/或树的一般搜索过程,说明： 如果在某时刻被选为扩展的节点不可扩展，并且它不是终止节点，则此节点就是不可解节点。 此时可应用不可解标示过程确定初始节点是否为不可解节点，如果可以肯定初始节点是不可解的，则搜索失败；否则继续扩展节点。 可解与不可解标示过程都是自下而上进行的，即由子节点的可解性确定父节点的可解性。由于与/或树搜索的目标是寻找解树，因此，如果已确定某个节点为可解节点，则其不可解的后裔节点就不再有用，可从搜索树中删去；如果已确定某个节点是不可解节点， 则其全部后裔节点都不再有用，可从搜索树中删去，但当前这个不可解节点还不能删去，因为在判断其先辈节点的可解性时还要用到它。 这是与/或树搜索的两个特有的性质，可用来提高搜索效率。,1.与/或树的广度优先搜索 与状态空间的广度优先搜索类似，也是按照“先产生的节点先扩展”的原则进行搜索，只是在搜索过程中要多次调用可解标示过程和不可解标示过程。搜索过程：(1) 把初始节点 S0 放入 OPEN 表。(2) 把 OPEN 表中的第一个节点 (记为节点n) 取出放人 CLOSED 表。(3) 如果节点n可扩展，则做下列工作： 扩展节点n，将其子节点放入OPEN表的尾部，并为每个子节点配置指向父节点的指针，以备标示过程使用。,3.3.2 与/或树的盲目搜索, 考察这些子节点中是否有终止节点。若有，则标示这些终止节点为可解节点，并应用可解标示过程对其父节点、祖父节点等先辈节点中的可解节点进行标示。如果初始节点S0也被标示为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。 转第 (2) 步。(4) 如果节点n不可扩展，则做下列工作： 标示节点n为不可解节点。 应用不可解标示过程对节点n的先辈节点中不可解的节点进行标示。如果初始节点S0也被标示为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从 OPEN 表中删去具有不可解先辈的节点 。,3.3.2 与/或树的盲目搜索,举例：P46 2.10,3.3.2 与/或树的盲目搜索,2.与/或树的深度优先搜索 和与/或树的广度优先搜索过程基本相同，只是要把第 (3)步的第点改为“扩展节点 n，将其子节点放入 OPEN 表的首部，并为每个子节点配置指向父节点的指针，以备标示过程使用”。这样就可使后产生的节点先被扩展。3.与/或树的有界深度优先搜索也可以像状态空间的有界深度优先搜索那样为与/或树的深度优先搜索规定一个深度界限，使搜索在规定的范围内进行。其搜索过程如下：(1) 把初始节点 S0 放入 OPEN 表。(2) 把 OPEN 表中的第一个节点 ( 记为节点n ) 取出放入 CLOSED 表。(3) 如果节点n的深度大于等于深度界限，则转第 (5) 步的第点。,(4) 如果节点n可扩展，则做下列工作: 扩展节点 n，将其子节点放入 OPEN 表的首部，并为每个子节点配置指向父节点的指针，以备标示过程使用。 考察这些子节点中有否终止节点。若有,则标示这些终止节点为可解节点，并应用可解标示过程对其先辈节点中的可解节点进行标示。如果初始节点 S0 也被标示为可解节点，则搜索成功，退出搜索过程如果不能确定 S0 为可解节点，则从 OPEN 表中删去具有可解先辈的节点。 转第 (2) 步。(5) 如果节点n不可扩展，则做下列工作： 标示节点n为不可解节点。 应用不可解标示过程对节点 n 的先辈节点中不可解的节点进行标示。如果初始节点S0也被标示为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从 OPEN 表中删去具有不可解先辈的节点。 转第 (2) 步。,广度优先搜索及深度优先搜索都是盲目搜索，其共同点是： (1) 搜索从初始节点开始，先自上而下地进行搜索，寻找终止节点及端点节，然后再自下而上地进行标示，一旦初始节点被标示为可解节点或不可解节点，搜索就不再继续进行。(2) 搜索都是按确定路线进行的，当要选择一个节点进行扩展时，只是根据节点在与/或树中所处的位置，而没有考虑要付出的代价，因而求得的解树不一定是代价最小的解树，即不一定是最优解树。,3.3.2 与/或树的盲目搜索,3.3.3 与/或树的启发式搜索,1.与/或树的有序搜索 与/或树的有序搜索是用来求取代价最小的解树的一种搜索方法，为了求得代价最小的解树，就要在每次确定欲扩展的节点时，先往前多看几步，计算一下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。Def:像这样根据代价决定搜索路线的方法称为与/或树的有序搜索，它是一种启发式搜索策略。相关概念： (1)解树的代价:为进行有序搜索，需要计算解树的代价，而解树的代价可通过计算解树中节点的代价得到.(2)希望树：,下面首先给出计算节点代价的方法，然后再说明如何求解树的代价。 设用c(x,y)表示节点x到其子节点y的代价，则计算节点x的代价的方法如下： (1) 如果x是终止节点，则定义节点 x 的代价 h(x)=0； (2) 如果x是“或”节点，y1,y2,yn 是它的子节点，则节点x的代价由下式计算得到 h(x)=minc(x,yi)+h(yi)，(1in) (3) 如果x是“与”节点，则节点x的代价有两种计算方法：和代价法与最大代价法。 若按和代价法计算，则有h(z)=(c(z,yi)+h(yi) 若按最大代价法计算，则有h(z)=max(c(z,yi)+h(yi) (4) 如果x不可扩展，且又不是终止节点，则定义 h(z)=。,3.3.3 与/或树的启发式搜索,举例：下图是一棵与/或树，其中包括两棵解树，一棵解树由S0，A，t1和t2组成；另一棵解树由S0，B，D，G，t4和t5组成。在此与/或树中，t1,t2,t3,t4,t5为终止节点；E,F是端节点，其代价为；边上的数字是该边的代价。,由左边的解树可得:按和代价：h(A)=11,h(S0)=13按最大代价：h(A)=6,h(S0)=8由右边的解树可得:按和代价：h(G)=3,h(D)=4,h(B)=6,h(S0)=8按最大代价：h(G)=2,h(D)=3,h(B)=5,h(S0)=7,(2) 希望树: 无论是用和代价方法还是最大代价方法，当要计算任一节点x的代价 h(x)时，都要求己知其子节点 yi 的代价 h(yi) 。 搜索是自上而下进行的，即先有父节点，后有子节点，除非节点x的全部子节点都是不可扩展节点，否则子节点的代价是不知道的。此时节点x的代价h(x)如何计算呢？,3.3.3 与/或树的启发式搜索,3.3.3 与/或树的启发式搜索,解决的办法是:根据问题本身提供的启发性信息定义一个启发函数，由此启发函数估算出子节点集的代价 h(yi)，按和代价或最大代价算出节点x的代价值h(x)，有了h(x)，节点x的父节点，祖父节点以及直到初始节点 S0的各先辈节点的代价 h 都可自下而上的逐层推算出来。当节点yi被扩展后，也是先用启发函数估算出其子节点的代价，然后再算出h(yi)。 注意：此时算出的h(yi) 可能与原先估算出的h(yi)不相同，这时应该用后算出的h(yi)取代原先估算出的h(yi)，并且按此h(yi)自下而上地重新计算各先辈节点的 h 值。当节点yi的子节点又被扩展时，上述过程又要重复进行一遍。,总之，每当有一代新的节点生成时，都要自下而上地重新计算其先辈节点的代价h，这是一个自上而下地生成新节点，又自下而上地计算代价h的反复进行的过程。有序搜索的目的是求出最优解树，即代价最小的解树。要求搜索过程中任一时刻求出的部分解树其代价都应是最小的。为此，每次选择欲扩展的节点时都应挑选有希望成为最优解树一部分的节点进行扩展。由于这些节点及其先辈节点(包括初始节点S0)所构成的与/或树有可能成为最优解树的一部分，因此称它为“希望树”。,在搜索过程中，随着新节点的不断生成，节点的代价值是不断变化的，因此希望树也是不断变化的。在某一时刻，这一部分节点构成希望树，但到另一时刻，可能是另一些节点构成希望树，随当时的情况而定。但不管如何变化，任一时刻的希望树都必须包含初始节点 S0，而且它是对最优解树近根部分的某种估计。,3.3.3 与/或树的启发式搜索,下面给出希望树的定义：(1) 初始节点S0在希望树T中。(2) 如果节点z在希望树T中，则一定有： 如果z是具有子节点y1,y2,yn的“或”节点，则具有h(z)=minc(z,yi)+h(yi)(1in)值的那个子节点 yt 也应在T中。如果z是“与”节点，则它的全部子节点都应在T中。,3.3.3 与/或树的启发式搜索,与/或树的有序搜索过程:(1) 把初始节点S0放入 OPEN 表中。(2) 求出希望树 T，即根据当前搜索树中节点的代价h求出以S0为根的希望树T。(3) 依次把OPEN表中T的端节点N选出放入CLOSED表中。(4) 如果节点N是终止节点，则做下列工作： 标示N为可解节点。 对T应用可解标示过程，把N的先辈节点中的可解节点都标示为可解节点。 若初始节点S0能被标示为可解节点，则T就是最优解树，成功退出。 否则，从OPEN表中删去具有可解先辈的所有节点。,3.3.3 与/或树的启发式搜索,(5) 如果节点 N 不是终止节点，且它不可扩展，则做下列工作： 标示 N 为不可解节点。 对 T 应用不可解标示过程，把 N 的先辈节点中的不可解节点都标示为不可解节点。 若初始节点S0也被标示为不可解节点，则失败退出。