状态空间搜索策略

1、状态空间搜索策略21搜索基本概念2搜索的一般过程状态空间搜索策略 从已知的事实出发（问题的初始状态） 寻找可用的知识（搜索） 一步一步推出最终结论（问题的目标状态） 问题求解搜索 状态节点父节点编号状态节点父节点：存放刚刚生成的节点：存放将要扩展和 / 或已经扩展的节点1）把初始节点S0放入OPEN，并建立只包含S0的图，记为 。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点取出放入CLOSED，并记为节点n。4）考察节点是否为目标节点，是，得解，退出。5）扩展节点n，生成一组子节点。 把其中不是节点n先辈的那些子节点记为集合，把这些子节点作为节点n的子节点加入 。6）针对

2、中子节点的不同情况：(1)对于那些未曾在中出现过的成员设置一个指向父节点（即节点n）的指针，把它们放入OPEN。(2)对于那些先前曾在中出现过的成员，确定是否需要修改其指向父节点（即节点n）的指针(3)对于对那些先前曾在 中出现过的、并已经扩展了的成员，确定是否需要修改其后继节点指向父节点的指针按某种对中的节点进行排序。8）转2）。 有编号为1、2、3的三个柱子和标识为A、B的尺寸依次为小、大的有中心孔的圆盘；初始状态下盘按A、B顺序堆放在1号柱子上，目标状态下盘以同样次序顺序堆放在3号柱子上，盘子的搬移须遵守以下规则：每次只能搬一个盘子，且较大盘不能压放在较小盘之上。1 2 3AB1 2 3

3、AB状态： 以三元素组描述问题状态 三个元素依次指示盘子A、B所在的柱子编号 Tower of Hanoi问题状态描述为：S=（1,1），G= （3,3）算子F：A(i,j)：把圆盘A从第i号柱子移到第j号柱子B(i,j)：把圆盘B从第i号柱子移到第j号柱子 状态与算子 全部可能的状态：（1,1）（1,2）（1,3） （2,1）（2,2）（2,3）（3,1）（3,2）（3,3）（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（2,3）（3,3）（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）求解路径（1,1）AB（2,1）

4、（2,3）（3,3）求解路径33212311A（2,3）B（1,3）A（1,2）二阶Tower of Hanoi塔状态空间图(局部)状态空间可描述为一个有向图节点指示状态节点间的有向弧表示状态变迁弧上的标签则指示导致状态变迁的操作算子状态用于记载问题求解（即搜索）过程中某一时刻问题现状状态空间图33212311A（2,3）B（1,3）A（1,2）33212311A（2,3）B（1,3）A（1,2）通过搜索得到的图为搜索图。由搜索图中的所有节点及反向指针所构成的集合是一棵树，为搜索树。 有N个有孔的盘子，最初这些盘子都叠放在柱a上（如图1），要求将这N个盘子借助柱b从柱a移到柱c（如图2），移动

5、时有以下限制，如何移动？每次只能移动一个盘子；大盘不能放在小盘上。 S02 83 147 65 在3*3的方格棋盘上放置分别标语有数字的八张牌： 初始状态为S0 目标状态为Sg 。 可使用的操作算符： 位于空格的的牌 移入空格。 S2 23 1 847 65Sg1 23847 65 S123 1 8 47 6 5 S3 1 23 847 651 广度优先搜索2 深度优先搜索3 有限深度优先搜索4 代价树广度优先搜索5 代价树深度优先搜索1）把初始节点S0放入OPEN。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n ）取出放入CLOSED。4）考察节点n是否为

6、目标节点，是，得解，退出。5）若节点n不可扩展，转2）。 6）扩展节点n ，将其子节点放入OPEN的，并为每一个子节点都配一个指向父节点的指针，然后转2）。1）把初始节点S0放入OPEN。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n ）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。 6）扩展节点n ，将其子节点放入OPEN的，并为每一个子节点都配一个指向父节点的指针，然后转2）。搜索过程：1）把初始节点S0放入OPEN，置S0的深度d(S0)。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个

7、节点（并记该节点为n ）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n的深度d(节点n)=dm，转2）。6）若节点n不可扩展，转2）。 7）扩展节点n ，将其子节点放入OPEN的首部，并为每一个子节点都配一个指向父节点的指针，然后转2）。见p269例 边上标有代价(或费用)的树为代价树. 在代价树中,若有g(x)表示从初始节点S0到节点x的代价,用c(x1,x2)表示从父节点x1到子节点x2的代价,则有: g(x2)=g(x1)+c(x1,x2)搜索过程：1）把初始节点S0放入OPEN，令g(S0)=0。2）检查OPEN是否为空，是，无解，退出。3）把OPEN

8、第一个节点（并记该节点为n ）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n ，将其子节点放入OPEN，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，并按各节点的代价对OPEN表中的全部节点进行排序（从小到大），然后转2）。代价树广度优先搜索搜索过程：1）把初始节点S0放入OPEN，令g(S0)=0。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n ）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n ，将其子节点按边代

9、价从小到大进行排序放入OPEN首部，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，然后转2）。1. 宽度优先、深度优先搜索，其主要的差别是OPEN表中待扩展节点的顺序问题。 2. 盲目搜索(弱方法)效率低，耗费过多的计算空间与时间。3. 若选择最有希望的节点加以扩展，则搜索效率将会大为提高。 启发式搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度，我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。 一种最常用的方法是定义一个评价函数,g(x)为从初始节点s0到节点x已经实际付出的代价；h(x)是从节点x到目标节点Sg的最

10、短路径的估计,它体现了问题的启发性信息。 h(x)称为启发函数。搜索树八数码问题 基本思想：定义一个评价函数f:f（n）g（n）h（n）其中n是被评价的节点。g*(n)：表示从初始节点s到节点n的最短路径的代价；h*(n)：表示从节点n到目标节点g的最短路径的代价；f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的代价。而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值的的估计值，是一种预测。利用评价函数f(n)g(n)h(n)来排列OPEN表节点顺序的图搜索算法称为A算法。 A算法每次按照f(n)值的大小对OPEN表中

11、的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。在A算法中的f(x) = g(x) + h(x)中每一节点x都有h(x) h*(x) h(x)是的h*(x)下界 则该A算法称为 A*算法。下面从理论上讨论A* 算法的几个重要特性： (1) A*算法的可采纳性 可采纳性：对于一个可解状态空间图（即从S0到G存在路径），如果搜索算法能找到一条最佳路径，则称该搜索算法是可采纳的（即算法找到一条最佳路径解后终止）。 结论1：A* 算法是可采纳的。（2） A* 算法的最优性算法的最优性 （即信息量的比较）（即信息量的

12、比较） A* 算法的搜索效率在很大程度上取决于算法的搜索效率在很大程度上取决于h(x)，在满足，在满足h(x)h*(x)下，下，h(x)的值越大，表明携带启发性信息越多。的值越大，表明携带启发性信息越多。 结论结论2：设有两个：设有两个A* 算法算法A1* 和和A2*： A1*：f1(x) = g1(x)+ h1(x) A2*：f2(x) = g2(x)+ h2(x) 对所有的非目标节点对所有的非目标节点x均有：均有： h2(x) h1(x) （A2*比比A1*有更多的信息）有更多的信息） 则则A1* 扩展节点数不会比扩展节点数不会比A2* 扩展节点少。扩展节点少。 即即A2* 的扩展节点集是的扩展节点集是A1* 扩展节点集的子集。扩展节点集的子集。 （通过搜索树深度应用数学归纳法证明）。（通过搜索树深度应用数学归纳法证明）。（3）A*算法的改进算法的改进 ( h(x)的单调性限制的单调性限制 ) 单调性限制：单调性限制： h(sg) = 0 设设xj是是xi的任意子节点有：的任意子节点有： h(xi) h(xj) + c ( xi, xj) 结论结论3：当：当h满足单调性限制，则满足单调性限制，则A* 算法扩展的每算法扩展的每个节点个节点x都满足：都满足： g(x) = g*(x) 保证每次扩展的路径是最优路径。保证每次扩展的路径是最优路径。 且且A*算法所扩展的节点序