Ch 5 状态空间搜索策略new.ppt

1、第5章：状态空间搜索策略，搜索，5.1搜索概述，在解空间中寻找解的过程和搜索策略的出现问题(1)结构差或无结构问题，没有解析解(2)理论上可解的问题，计算复杂度可能太高。基本搜索方法(1)盲搜索，根据预定策略搜索，不考虑问题本身的特性(2)启发式搜索通过使用与问题相关的启发式信息来加速搜索过程。启发式信息和评价函数反映了问题的特点。可用于确定搜索方向的信息评估函数的功能是根据作为选择搜索方向的基础的启发式信息来计算对应于特定搜索方向的评估值。本地搜索与全局搜索在确定搜索方向时，您是考虑本地信息还是全局信息？任何解决方案与最佳解决方案、搜索方法、图形搜索方法、广度优先、深度优先、有限深度优先、启

2、发式最佳图形搜索方法(A*、AO*)、游戏搜索方法、MiniMax、Alpha-Beta修剪(Scorging)、现代优化搜索方法，如爬山、模拟退火、遗传算法、搜索策略评估、完整性，如果问题得到解决，是否能保证找到？优化(Optimization)如果问题有不同的解决方案，你能找到最佳解决方案吗？时间复杂度-找到一个解决方案需要多少时间和空间复杂度-在搜索过程中需要占用多少内存，时空复杂度的度量，状态空间图的大小，分支因子，b，目标节点的深度，d，路径的最大长度，m，搜索深度限制，l，5.2，问题及其搜索过程的表示，状态空间表示用“状态”表示问题， 问题解决状态通过“算子”的变化表明问题的解决

3、过程，基于“状态”和“算子”的状态空间是问题解决过程中任何时刻的状态算子，即由操作问题的所有状态(包括初始状态和目标状态)和所有可用算子组成的集合，使问题从一种状态变为另一种状态，称为问题的状态空间。 初始状态、中间状态1、中间状态2、目标状态、状态空间示例：二阶梵塔问题，有三个钢针，它们的编号分别为1、2、3。在最初的状态下，两个金块，甲和乙，穿在钢针上。甲比乙小，甲位于乙之上.要求将两个金块全部移动到另一个钢针上，并规定一次只能移动一个金块，任何时候都不能将大块放在小块上。Sk=Sk0，Sk1表示问题的状态，其中Sk0表示金钢片a所在的钢针号，Sk1表示金钢片b所在的钢针号。有九种可能的问

4、题状态：SO=(1，l) S1=(1，2) S2=(1，3) S3=(2，1) S4=(2，2) S5=(2，3) S6=(3，1) S7=(3，2) S8 B(i，J)表示将金钢片B从I #钢针移动到J #钢针。有12种操作：a (1，3) a (2，1) a (2，3) a (3，1) a (3，2) b (1，3) b (2，1) b (2，3) b (3，1) b (3) A(1，3)，b (1，2)，a (3，2)，根据状态和操作符，可以形成二阶梵塔问题的状态图，最短路径解，八数游戏(八数问题)描述如下：on这个游戏解决的问题是：给定一个卡片的初始布局或结构(称为初始状态)和一个目标

5、布局(称为目标状态)，询问如何移动卡片来实现从初始状态到目标状态的转换。5.3通用图搜索算法，无论是状态空间还是“与”的问题表示还是图，问题求解过程都可以看作是在“图”中搜索。基本思想不是存储所有的搜索图，而是逐步扩展解决问题所需的搜索子图。特定方法从初始状态开始，不断扩展当前节点，即生成子节点，直到目标状态出现在这些子节点中，或者没有可扩展的节点。数据结构，打开表(未扩展节点表)存储未扩展节点，关闭表(扩展节点表)存储扩展节点，打开表：关闭表：算法步骤，步骤1将初始节点S0放入打开表，并建立只包含S0的图g；第二步：从开放表中取出要扩展的节点，放入封闭表中；(不同搜索策略之间的差异主要体现在

6、这一点上。)步骤3扩展节点，并将扩展后的未出现在G中的子节点放入Open表中；根据需要修改节点的指针；步骤4重复步骤2-3，直到状态空间：待扩展的节点是目标节点或开表为空，盲目搜索策略，广度(宽度)优先搜索，教师制作的节点先扩展深度优先搜索，然后生成节点先扩展有限深度优先搜索，在深度优先策略中增加深度限制，在广度优先和深度优先之间折衷，完整，最小路径解，效率，盲目搜索示例(状态空间)为：八张标有数字1、2、3、4、5、6、7和8的牌放在3*3的棋盘上。初始状态S0和目标状态Sg分别如图所示。您可以使用以下操作：左空格、上空格、右空格和下空格来查找从初始状态到目标状态的解决方案路径。广度优先搜索

7、算法如下：(1)将初始节点放入开放表中；(2)如果“打开”表为空，则没有解决问题的方法，并且无法退出；(3)取出“打开”表中的第一个节点，将其放入“关闭”表中，并将该节点记录为“否”；(4)展开节点N，如果没有后续节点，转到步骤(2)；(5)将N的所有后继节点放在开放表的末尾，并提供从这些后继节点到父节点的指针(编号为N)；(6)如果在新生成的后继节点中存在目标节点，则找到解决方案。从目标节点到初始节点的返回指针可以得到解，算法成功退出。否则，转到(2)继续。s，l，o，m，f，p，q，n，f，f，开始节点，开始，将S0放入打开表，打开表是否为空，失败，将第一个节点n移出打开表并将其放入，成功

8、，否，是，否，是，原理图，算法框图，Sg，解决方案的路径是：S0 3 8 16 26(Sg)，宽度优先搜索8位数字谜，宽度优先搜索是一个完整的策略，即只要深度优先搜索深度优先搜索是一种稍后生成的节点先扩展的策略。搜索过程如下：从初始节点S0开始，从其子节点中选择一个新生成的节点进行调查。如果子节点不是目标节点并且可以展开，展开子节点，然后向下搜索，直到子节点既不是目标节点也不能继续展开，然后选择其兄弟节点进行调查。该图如下：S0，1，2，3，7，6，8，4，5，9，启动节点，将S0放入打开表，S0是否为目标节点，打开表是否为空表，将打开表中的第一个节点n移动到关闭表中，节点n的深度是否等于深度

9、是否有后续节点为目标节点，成功，失败，成功，是，否，是，否，否，示意图，算法框图，深度优先搜索算法如下(3)取出“打开”表中的第一个节点，将其放入“关闭”表中，并将该节点记录为“否”；(4)检查节点N是否为目标节点，如果是，则得到问题的解决方案并成功退出；(5)如果节点n不可扩展，请转到(2)；(6)展开节点N，将其子节点放在打开表的头部，为每个子节点设置一个指向父节点的指针，然后转到(2)。从深度优先搜索算法可以看出，一旦搜索进入一个分支，它将沿着这个分支继续。如果目标恰好在这个分支上，它可以很快找到解决方案。然而，如果目标不在该分支上，并且该分支是无限分支，则在搜索过程中不可能找到解决方案

10、。因此，深度优先搜索是一个不完整的策略，即使问题有解决方案，它也可能无法找到解决方案。解的路径是： so: l 11 12 13 14: SG，SG，有界深度优先搜索八位数字谜，28 34 765，s0，1，28 31 47 65，2，23 84 765，11，28 34 765，28 36 47 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 3 7 6 5，2 3 7 6 5，2 8 3 4 5 5 7 6，2 8 3 6 4 4 7 5，2 8 3 6 4 7 5，3，7，13，8 3 2 1 4 7 6

11、 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 7 5 4，4，8，8 3 2 1 4 7 6 5，8 1 3 2 4 7 6 5，5，6，28 37 46 15，28 37 14 65，9，10，1 23 84 76 5，1 23 78 46 5，5 以上讨论的所有搜索方法都不使用问题本身的特征信息，而是根据预设的路径进行搜索，这是盲目的。事实上，如果我们能够利用在搜索过程中获得的问题的一些特征信息来指导搜索过程，将会对搜索非常有益。

12、这种搜索策略利用问题本身的特点来指导搜索过程，提高搜索效率，称为启发式搜索或信息搜索。启发式搜索方法基于问题本身的启发式信息，启发式信息通过赋值函数作用于搜索过程。5.4启发式搜索。启发式算法利用问题的特殊性选择要扩展的节点，从而缩小搜索范围，提高搜索速度。启发式信息可以指导搜索过程，是与具体问题解决过程相关的控制信息。通常有三种类型：帮助确定扩展节点的信息；帮助决定应该生成哪些后续节点的信息；评估函数f(n):用于估计节点成本的函数被定义为在被节点n约束之后从初始节点S0到目标节点Sg的所有路径中的最佳路径的成本估计值。一般形式是f(n)=g(n)h(n)g(n)，它是从初始节点S0到节点n

13、的实际成本.您可以从节点n追溯到初始节点S0，并以最低的成本获得当前路径。将这条路径上所有有向边的成本相加，得到g(n)的值。H(n)是从节点n到目标节点S0的最佳路径的估计成本。它需要根据问题本身的特点来确定，这反映了问题本身的启发式信息，所以它也称为启发式函数。评估函数示例：f(n)=d(n) W(n)，搜索树中节点n的深度，n、中的“不在位置”位数f(S0)=？=0 3=3，根据搜索过程中选择的扩展节点范围，可分为全局首选搜索和局部首选搜索。1.从打开表的所有节点中全局选择一个具有最小赋值函数值的节点进行扩展；2.从新生成的子节点中本地选择具有最小赋值函数值的节点进行扩展。局部最佳优先搜

14、索算法，比较OPEN表中所有节点的f(n)，将OPEN表从小到大重新排列。该算法的效率与垂直搜索算法相似，但它是一种启发式搜索方法，因为它使用与问题特征相关的评估函数来确定下一步要扩展的节点。开始，将s放入open表，计算评估函数f (s)，OPEN表为空？将OPEN表中的第一个节点n放入CLOSED表中。n是目标节点吗？扩展n，计算所有子节点的评估函数值，并提供它们的指针返回节点n，失败、成功、局部最佳优先搜索算法框图，是、否、是、否，将子节点发送到OPEN表中，并根据评估函数值从小到大重新排列其中的所有节点。例如：8字谜题，5，7，搜索到的路径用黄线表示。本主题使用一个简单的评估函数f(n

15、)=W(n)，其中W(n)用于计算对应于节点n的数据库中放错位置的棋子数量。因此，初始节点象棋游戏的f(n)值等于4。第一步有三种情况，我们选择f(n)最小的：依此类推。最后，我们通过七个步骤得到结果。(3)、(5)、(5)、(5)，最佳优先算法有时不能得到最优解，因为它的评价函数f忽略了从初始节点到当前节点的代值。因此，我们可以考虑对评估函数f(n)进行一些修改或限制。5.5 A*算法，对评价函数增加一些限制，以保证最优评价函数f*(n) g*(n) h*(n)，从初始节点到节点n的最小代价，以及从节点n到目标节点的最小代价的启发式搜索算法得到最优解，以及相关限制1。g(n)是g*(n)和g. 2的估计。h(n)是h*(n)的下界，也就是说，任何节点n都有H (n) H * (n)。算法示例1:八位数问题，解1: H (n)=W (n)。虽然h*(n)不能被精确地知道，但是当采用单位成本时，通过估计“非现场”数字的数量，可以得出结论，通过移动至少W(n)个步骤可以达到目标，并且显然存在W(n)个h*(n)，这满足了A*算法的限制。解决方案2: H (n)=P(n)，其中