第三章状态空间搜索策略.ppt

《第三章状态空间搜索策略.ppt》由会员分享，可在线阅读，更多相关《第三章状态空间搜索策略.ppt（61页珍藏版）》请在三一办公上搜索。

1、第三章 状态空间搜索策略,3.1 搜索的概念及种类3.2 盲目搜索策略3.3 启发式搜索策略,例1 走迷宫是人们熟悉的一种游戏，如图就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示。,我们通过例子引入状态空间搜索的概念。,迷宫的有向图表示,走迷宫其实就是从该有向图的初始节点(入口)出发，寻找目标节点(出口)的问题，或者是寻找通向目标节点(出口)的路径的问题。,例2 在一个33的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在

2、的问题是：对于指定的初始棋局和目标棋局(如图)，给出数码的移动序列。该问题称为八数码难题或重排九宫问题。,初始棋局,目标棋局,状态空间（图）是一类问题的抽象表示，有许多智力问题(如Hanoi塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在状态空间(图)中寻找目标或路径的问题。因此，研究状态空间搜索具有普遍意义。,3.1 搜索的概念及种类,现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。,搜索：是一种求解问题的方法，是寻找从问题初始事实到最终答案

3、的推理路线的一种过程。,搜索包含两层含义：一是根据问题的实际情况，按照一定的策略，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线；另一是找到的这条路线是时空复杂度最小的求解路线。,3.1.1 搜索的概念,盲目搜索：又称无信息搜索。即在搜索过程中，只按预先规定的搜索控制策略进行搜索。问题本身的特性对搜索控制策略没有任何影响，搜索带有盲目性，效率不高，只用于解决比较简单的问题。,启发式搜索：又称有信息搜索。指在搜索求解过程中，根据问题本身的特性来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。搜索求解的效率高，易于求解复杂的问题，但抽取出

4、问题的相关特性和信息难。,3.1.2 搜索的种类搜索分为盲目搜索和启发式搜索两种。,状态空间表示法：是一种用状态和算符表示问题的方法。当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。,状态空间图：状态空间的图示表示问题形式。状态空间图是一个有向图，节点表示状态，有向边（弧）表示算符。,3.2 盲目搜索策略,3.2.1 状态空间图的搜索策略,状态空间图对问题的求解就相当于在有向图上寻找一条从某一节点(初始状态节点)到另一节点(目标状态节点)的路径。,搜索法求解问题的基本思想：首先将问题的初始状态(初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一

5、组后继状态(后继节点)，然后检查这组后继状态中有没有目标状态。,如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态。,重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。,节点扩展 概念扩展：就是用合适的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求后继节点的过程。,已扩展节点：对状态空间图中的某个节点，如果求出了它的后继节点，则此节点为已扩展的节点。,未扩展节点：对状态空间图中的某个节点，如果尚未求出它的后继节点，则此节点称为未扩展节点。,在对状态空间图搜索求解时，将未扩展的节点

6、存于一个名为OPEN的表中，而将已扩展的节点存于一个名为CLOSED的表中。,状态空间图的一般搜索策略：,搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹。我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点（已扩展的节点）。CLOSED表中存储的是一棵不断成长的搜索树。,另一方面，还得不断地把待考查的节点（未扩展的节点）组织在一起，并做某种排列，以便控制搜索的方向和顺序。我们采用一个称为OPEN表的动态数据结构，来专门登记当前待考查的节点。,(1)建立一个只含有初始节点S0的搜索图G，把S0放人OPEN表中。(2)建立CLOSED表，且置为空表。

7、(3)判断OPEN表是否为空表，若为空，则问题无解，退出。(4)若OPEN表非空，选择OPEN表中的第一个节点，把它从OPEN表移出，并放人CLOSED表中，将此节点记为节点n。(5)考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从图G中沿着指针从n到S0的这条路径得到。(6)扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中。,(7)对那些未曾在G中出现过的M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n节点)的指针；对

8、于那些先前已在G中出现并且已在CLOSED表中的那些M中的节点，确定是否需要修改通向它们后继节点的指针。(8)按某一任意方式或按某种策略重排OPEN表中节点的顺序。(9)转第(3)步。,算法3.1 状态空间图的一般搜索算法,在搜索过程中，生成了一个图G，它是问题状态空间图的一部分，称为搜索图。,由搜索图G中的所有节点及设置的指向父节点的反向指针，所构成的集合T，称为搜索树。,在搜索过程中，问题的解就是从初始节点So到目标节点路径上的算符所构成的序列。,路径是通过目标节点按设置的指针指向初始节点So回溯而得到的。,3.2.2 宽度优先搜索策略,宽度优先搜索又称为广度优先搜索。基本思想：是从初始节

9、点开始，逐层对节点进行依次扩展，并考察它是否为目标节点。在对下层节点进行扩展(或搜索)之前，必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：“先入先出”，即先进入的节点排在前面，后进入的节点排在后面。,算法3.2 状态空间图的宽度优先搜索算法(1)把初始节点S0放人OPEN表中。(2)如果OPEN表是空表，则没有解，失败退出；否则继续。(3)把OPEN表中的第一个节点(记为节点n)移出，并放人CLOSED表中。(4)判断节点n是否为目标节点，若是，则求解结束，并用回溯法找出解的路径，退出；否则继续执行(5)。(5)若节点n不可扩展，转第(2)步

10、；否则继续执行(6)步。(6)对节点n进行扩展，将它的所有后继节点放人OPEN表的末端，并为这些后继节点设置指向父节点n的指针，然后转第(2)步。,例3.1 八数码难题：设在33的一个方格棋盘上，摆放着8个数码1、2、3、4、5、6、7、8，有一个方格是空格，其初始状态如下图(a)所示，要求对空格执行下列的操作(或算符)：左移，上移，右移，下移。使8个数据最终按下图(b)的格式摆放，图(b)称为目标状态Sg。要求寻找从初始状态到目标状态的路径。,S0(a)初始状态,Sg(b)目标状态,解的路径为:So381627Sg,宽度优先搜索的特点：搜索盲目性较大，效率低。当目标节点距离初始节点较远时，将

11、会产生大量的无用节点。,搜索策略是完备的。只要问题有解，宽度优先搜索总可以找到它的解，而且是搜索树中，从初始节点到目标节点的路径最短的解。,基本思想：首先扩展最新产生的(即最深的)节点。即从初始节点So开始，在其后继节点中选择一个节点，对其进行考察，若它不是目标节点，则对该节点进行扩展，并再从它的后继节点中选择一个节点进行考察。依次类推，一直搜索下去。当到达某个既非目标节点又无法继续扩展的节点时，才选择其兄弟节点进行考察。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：“后入先出”，即后进入的节点排在前面，先进入的节点排在后面。,3.2.3 深度优先搜索,算法3.3 状态空间图的深度优先

12、搜索算法(1)把初始节点S0放人OPEN表；(2)如果OPEN表为空，则问题无解，退出；(3)从OPEN表中将其第一个节点(节点n)移出，放入已扩展节点表CLOSED中；(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解的路径，退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，将其后继节点放到OPEN表的前端，并为其设置指向节点n的指针，然后转第(2)步。,深度优先搜索与宽度优先搜索的区别就在于：在对节点n进行扩展时，其后继节点在OPEN表中的存放位置。,宽度优先搜索是将后继节点放入OPEN表的末端“先入先出”。,深度优先搜索是将后继节点放入OPEN表的前端“后入

13、先出”。,例3.2 对例3.1的八数码难题，利用深度优先方法进行搜索求解问题。,深度优先搜索的特点：搜索策略是完备的。搜索若进入某一分支，则沿着这一分支一直搜索下去，对于有限的状态空间图，从理论上讲，解总是能够找到的。,搜索效率低。由于某些分支可能扩展得很深，而解又不在这些分支上，这就无疑会降低搜索的效率。,在深度优先搜索中，为了避免搜索过程沿着无穷的路径一直搜索下去，往往对一个节点扩展的最大深度进行限制。任何节点如果达到了深度界限，就把它作为没有后继节点进行处理，而对另一个分支进行搜索。,3.2.4 有界深度优先搜索,搜索树中节点深度(d)定义：(1)搜索树中初始节点的深度为0。(2)任何其

14、他节点的深度等于其父辈节点的深度加上1。,算法3.4 有界深度优先搜索算法(1)把初始节点So放入OPEN表中。(2)如果OPEN表为空，则问题无解，退出。(3)把OPEN表中的第一个节点n从OPEN表移到CLOSED表。(4)考察节点n是否为目标节点，若是，则求得问题的解，退出；否则继续执行第(5)步。(5)如果节点n的深度dn等于最大深度dm，则转第(2)步。(6)如果节点n不可扩展，即没有后继节点，则转第(2)步；否则继续第(7)步。(7)扩展节点n，将其后继节点放入OPEN表的前端，并为其设置指向节点的指针，转第(2)步。,例3.3 设八数码难题的初始状态及目标状态分别如下图(a)和图

15、(b)所示，试用有界深度优先搜索策略求解问题。深度界限dm=5。,有界深度优先搜索算法的深度界限的选择很重要。选择过大，可能会影响搜索的效率；选择的过小，有可能求不到解。,有界深度优先搜索策略是不完备的。对于某些问题，可能它的解就位于某一分支较深的位置，而界限值选取的没有那么大，就会导致找不到问题的解。,搜索代价问题：在实际问题的搜索求解中，在将一个状态变换成另一个状态时，往往所付出的操作代价(或费用)是不一样的，也就是状态空间图中各有向边的代价是不一样的。这是前面讨论搜索算法没有考虑的。,3.2.5 代价树的宽度优先搜索,代价树：把有向边上标有代价的搜索树称为代价搜索树，简称代价树。,代价计

16、算：在代价树中，把从初始节点So到任意节点i的路径代价记为g(i)，而把从节点i到其后继节点j的连线之代价(有向边代价)记为C(i,，j)，则g(j)=g(i)+C(i，j)。,代价树宽度优先搜索的基本思想：每次从OPEN表中选择一个代价最小的节点，移入CLOSED表。,算法3.5 代价树的宽度优先搜索算法(1)把初始节点So放入OPEN表，令g(So)=0。(2)如果OPEN表为空，则问题无解，退出。(3)把OPEN表中代价最小的节点，即排在前端的第一个节点(即为节点n)，移入CLOSED表中。(4)如果节点n是目标节点，则求得问题的解，退出，否则继续。(5)判断节点n是否可扩展，若不可扩展

17、，则转(2)步；否则转(6)步。(6)对节点n进行扩展，将它们所有的后继节点放入OPEN表中，并对每个后继节点j计算其代价g(j)=g(i)+C(i，j)，为每个后继节点设置指向n节点的指针，然后，根据节点的代价大小对OPEN表中的所有节点进行从小到大的排序。(7)转向第(2)步。,例3.4 推销员旅行问题。假设A、B、C、D、E是5个城市，推销员从城市A出发，到达城市E，走怎样的路线费用最省?5个城市间的交通图及每两个城市间的旅行费用如下图。,3.2.6 代价树的深度优先搜索,代价树宽度优先搜索每次从OPEN表中的全体节点中选择代价最小的节点移人ClOSED表，并对这一节点进行扩展或判断是否

18、为目标节点。,代价树深度优先搜索则是从当前扩展节点的后继节点中选择一个代价最小的节点移入CLOSED表，并进行扩展或判断。,算法3.6 代价树的深度优先搜索算法(1)把初始节点So放人OPEN表中。(2)如果OPEN表为空，则问题无解，退出。(3)将OPEN表中的第一个节点(代价最小的节点记为节点n)移人CLOSED表。(4)如果节点n是目标节点，则求得问题的解，退出；否则转第(5)步。(5)判断节点n是否可扩展，若不可扩展则转第(2)步，否则转第(6)步。(6)对节点n进行扩展，并将其后继节点按有向边代价从小到大排序后放入OPEN表的前端，并为各后继节点设置指向n节点的指针。(7)转第(2)

19、步。,代价树深度优先搜索虽然速度快，但所得到的解不一定是最优解。,代价树的深度优先搜索法是不完备的，因为代价树的深度优先搜索法有可能进入无穷分支路径而搜索不到问题的解。,3.3 启发式搜索策略,启发式搜索：利用问题自身特性信息，以提高搜索效率的搜索策略。又称有信息搜索。,3.3.1 启发信息与估价函数,启发信息：于指导搜索过程且与具体问题求解有关的控制性信息。,启发信息按其作用来分可以有三种：(1)用于决定要扩展的下一个节点，以免像在宽度优先或深度优先中那样盲目地扩展。(2)在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。(3)用于确定某些应该从

20、搜索树中抛弃或修剪的节点。,估价一个节点价值一般要考虑两方面的因素：已经付出的代价和将要付出的代价。设估价函数为f(x)，则将其定义为：f(x)=g(x)+h(x),估价函数：在决定哪个节点是下一步要扩展的节点上，通常可以构造一个函数来表示节点的“希望”程度，这种函数称为估价函数。其任务就是估计待搜索节点的重要程度，给它们在OPEN表中排定次序。,g(x)代价函数：为初始节点So到节点x已实际付出的代价，可由已生成的搜索树实际计算出来。h(x)启发函数：是从节点x到目标节点Sg的最优路径的估计代价，用来估计节点x与目标节点Sg接近程度的一种函数。依赖于对问题特性了解的某种经验估计，主要体现了搜

21、索的启发信息。,一般地，g(x)项体现了搜索的宽度优先趋势，有利于搜索算法的完备性，但影响算法的搜索效率。h(x)项体现了搜索的深度优先趋势，有利于搜索效率的提高，但影响搜索算法的完备性，即有可能找不到问题的解。,估价函数是针对具体问题构造的，在构造估价函数时，依赖于问题特性的启发函数h(x)的构造尤为重要，一般可由节点x与目标节点Sg 的差异来决定。,3.3.2 最佳优先搜索最佳优先搜索基于估价函数f(x)的值来选择最有希望的节点作为下一个要扩展的节点。估价函数值越小，希望程度越大。,1.局部最佳优先搜索基本思想：当对某一个节点扩展之后，对它的每一个后继节点计算估价函数f(x)的值，并在这些

22、后继节点的范围内，选择一个f(x)的值最小的节点，作为下一个要考察的节点。类似于深度优先搜索法。,算法3.7 局部最佳优先搜索算法(1)把初始节点So放入OPEN表，并计算估价函数f(So)。(2)如果OPEN为空，则问题无解，退出；否则转第(3)步。(3)从OPEN表中选取第一个节点(记作节点n，其估价函数值最小)移入CLOSED表。(4)考察节点n是否为目标节点，若是，则求得问题的解，退出；否则转第(5)步。(5)如果节点n可扩展，转(6)步；否则转第(2)步。(6)对节点n进行扩展，并对它的所有后继节点计算估价函数f(x)的值，并按估价函数f(x)从小到大的顺序依次放入OPEN表的前端。

23、(7)为每个后继节点设置指向n的指针。(8)转第(2)步。,2全局最佳优先搜索基本思想：在确定下一个扩展节点时，在OPEN表中的全部节点中选择一个估价函数值f(x)最小的节点，作为下一个被考察的节点。类似于宽度优先搜索。,算法3.8 全局最佳优先搜索算法(1)把初始节点So放入OPEN表，计算f(So)。(2)如果OPEN为空表，则问题无解，退出。(3)把OPEN表中第一个节点作为节点n移入CLOSED表。(4)考察节点n是否为目标节点，若是，则求得问题的解，退出；否则转第(5)步。(5)如果节点n可扩展，转第(6)步；否则转第(2)步。(6)对节点n进行扩展，并计算所有后继节点的估价函数f(

24、x)的值，并为每个后继节点设置指向n的指针。(7)把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价f(x)值从小到大的顺序排序。(8)转第(2)步。,例3.5 用全局最佳优先搜索方法求解八数码难题。初始状态图及目标状态图分别如下图(a)和(b)所示，试求由So转换为Sg的路径。,解：首先定义一个估价函数：f(x)=d(x)+h(x)d(x)：表示节点x在搜索树中的深度；h(x)：表示与节点x对应的棋盘中，与目标节点Sg所对应的棋盘中棋子位置不同的个数。,1.A*算法的定义A*算法也是一种启发式搜索方法，它对算法3.1中的扩展节点选择方法做了一些限制，选用了一个比较特殊的估价

25、函数。这时的估价函数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 A*算法,g*(x)：从节点So到节点x之间最佳路径的实际代价。h*(x)：从x节点到目标节点Sg的最佳路径的代价。f*(x)：表示从节点So到节点x的一条最佳路径的实际代价加上从节点x到目标节点Sg的一条最佳路径的代价之和。g(x)：从初始节点So到节点x的路径代价，显然恒有g(x)g*(x)。h(x)：依赖于有关问题领域的启发信息。,定义3.1 如果在一般状态空间图的

26、搜索算法(算法3.1)中的第(8)步，依据估价函数 f(x)=g(x)+h(x)对OPEN表中的节点进行排序，并且要求启发函数h(x)是h*(x)的一个下界，即h(x)h*(x)，则这种状态空间图的搜索算法就称为A*算法。如果对启发函数h(x)，不限制条件h(x)h*(x)，则这种状态空间图的搜索算法称为A算法。,在启发式搜索中，估价函数f(x)如果定义得不好，则搜索算法不一定能找到问题的解。即便找到解，也不一定是最优解。,A*启发式搜索算法使用了特殊定义的估价函数，它要求启发函数h(x)是h*(x)的下界，即对所有的x均有：h(x)h*(x)。这一要求十分重要，它能保证A*算法找到最优解。,

27、A*算法是对算法3.1中的扩展节点选择方法作了限制，它可以使问题的求解更快速、更有效。,2.A*算法的性质(1)可采纳性即对于可求解的状态空间图(从初始节点到目标节点有路径存在)来说，A*算法能在有限步内终止，并找到最优解。,(2)单调性当启发函数h(x)满足下面限制条件时，所扩展的节点序列估价函数f(x)的值是非递减的，从而减少对OPEN表或CLOSED表的检查和调整，排序简单，提高搜索效率。,对所有的节点xi，如果xj是节点xi的任意子节点，有h(xi)-h(xj)C(xi，xj)。其中C(xi，xj)是节点xi到节点xj的有向边代价。目标节点Sg 的启发函数的值为0，即h(Sg)=0。,(3)信息性A*算法的搜索效率主要取决于启发函数h(x)，在满足h(x)h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它携带与求解问题相关的启发信息越多，搜索过程就会在启发信息指导下朝着目标节点前进，所扩展的节点数就不会太多，走的弯路少，搜索效率就会提高。,