状态空间搜索策略

状态空间搜索策略第一页，共五十一页，编辑于2023年，星期三13.1搜索1搜索基本概念2搜索的一般过程第二页，共五十一页，编辑于2023年，星期三21.搜索从已知的事实出发（问题的初始状态）寻找可用的知识（搜索）一步一步推出最终结论（问题的目标状态）

问题求解搜索第三页，共五十一页，编辑于2023年，星期三3

2搜索的一般过程

OPEN：存放刚刚生成的节点CLOSED：存放将要扩展和/或已经扩展的节点OPENCLOSED第四页，共五十一页，编辑于2023年，星期三41）把初始节点S0放入OPEN，并建立只包含S0的图，记为G。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点取出放入CLOSED，并记为节点n。4）考察节点是否为目标节点，是，得解，退出。5）扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记为集合M，把这些子节点作为节点n的子节点加入G。第五页，共五十一页，编辑于2023年，星期三56）针对M中子节点的不同情况：(1)对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，把它们放入OPEN。(2)对于那些先前曾在G中出现过的M成员，确定是否需要修改其指向父节点（即节点n）的指针(3)对于对那些先前曾在G中出现过的、并已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针7）按某种搜索策略对OPEN中的节点进行排序。8）转2）。第六页，共五十一页，编辑于2023年，星期三6TowerofHanoi问题有编号为1、2、3的三个柱子和标识为A、B的尺寸依次为小、大的有中心孔的圆盘；初始状态下盘按A、B顺序堆放在1号柱子上，目标状态下盘以同样次序顺序堆放在3号柱子上，盘子的搬移须遵守以下规则：每次只能搬一个盘子，且较大盘不能压放在较小盘之上。123AB123AB第七页，共五十一页，编辑于2023年，星期三7状态：以三元素组描述问题状态三个元素依次指示盘子A、B所在的柱子编号TowerofHanoi问题状态描述为：S=（1,1），G=（3,3）算子F：A(i,j)：把圆盘A从第i号柱子移到第j号柱子B(i,j)：把圆盘B从第i号柱子移到第j号柱子

状态与算子第八页，共五十一页，编辑于2023年，星期三8全部可能的状态：（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）第九页，共五十一页，编辑于2023年，星期三9（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）求解路径第十页，共五十一页，编辑于2023年，星期三10（1,1）AB（2,1）（2,3）（3,3）求解路径第十一页，共五十一页，编辑于2023年，星期三1133212311A（2,3）B（1,3）A（1,2）二阶TowerofHanoi塔状态空间图(局部)第十二页，共五十一页，编辑于2023年，星期三12

状态空间可描述为一个有向图节点指示状态节点间的有向弧表示状态变迁弧上的标签则指示导致状态变迁的操作算子状态用于记载问题求解（即搜索）过程中某一时刻问题现状状态空间图33212311A（2,3）B（1,3）A（1,2）第十三页，共五十一页，编辑于2023年，星期三13搜索图与搜索树33212311A（2,3）B（1,3）A（1,2）通过搜索得到的图为搜索图。由搜索图中的所有节点及反向指针所构成的集合是一棵树，为搜索树。第十四页，共五十一页，编辑于2023年，星期三14TowerofHanoi问题

有N个有孔的盘子，最初这些盘子都叠放在柱a上（如图1），要求将这N个盘子借助柱b从柱a移到柱c（如图2），移动时有以下限制，如何移动？每次只能移动一个盘子；大盘不能放在小盘上。第十五页，共五十一页，编辑于2023年，星期三15重排九宫问题

S02 8 3 1 4 7 6 5

在3*3的方格棋盘上放置分别标语有数字的八张牌：1，2，3，4，5，6，7，8初始状态为S0

目标状态为Sg。

可使用的操作算符：位于空格的左、下、右、上的牌移入空格。

S2

2 3 18 4 76 5 Sg1 2 3 8 47 6 5

S12 3

18 476 5

S3

12 3 8 4 76 5第十六页，共五十一页，编辑于2023年，星期三163．2盲目搜索1广度优先搜索2深度优先搜索3有限深度优先搜索4代价树广度优先搜索5代价树深度优先搜索第十七页，共五十一页，编辑于2023年，星期三171广度优先搜索1）把初始节点S0放入OPEN。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点放入OPEN的尾部，并为每一个子节点都配一个指向父节点的指针，然后转2）。第十八页，共五十一页，编辑于2023年，星期三18重排九宫问题重排九宫问题第十九页，共五十一页，编辑于2023年，星期三19第二十页，共五十一页，编辑于2023年，星期三20第二十一页，共五十一页，编辑于2023年，星期三21第二十二页，共五十一页，编辑于2023年，星期三22第二十三页，共五十一页，编辑于2023年，星期三232深度优先搜索1）把初始节点S0放入OPEN。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点放入OPEN的首部，并为每一个子节点都配一个指向父节点的指针，然后转2）。第二十四页，共五十一页，编辑于2023年，星期三24重排九宫问题第二十五页，共五十一页，编辑于2023年，星期三25重排九宫问题第二十六页，共五十一页，编辑于2023年，星期三26重排九宫问题第二十七页，共五十一页，编辑于2023年，星期三27重排九宫问题第二十八页，共五十一页，编辑于2023年，星期三28重排九宫问题第二十九页，共五十一页，编辑于2023年，星期三29重排九宫问题第三十页，共五十一页，编辑于2023年，星期三30重排九宫问题第三十一页，共五十一页，编辑于2023年，星期三313有界深度优先搜索搜索过程：1）把初始节点S0放入OPEN，置S0的深度d(S0)。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n的深度d(节点n)=dm，转2）。6）若节点n不可扩展，转2）。7）扩展节点n，将其子节点放入OPEN的首部，并为每一个子节点都配一个指向父节点的指针，然后转2）。见p269例6.6

第三十二页，共五十一页，编辑于2023年，星期三324代价树广度优先搜索边上标有代价(或费用)的树为代价树.在代价树中,若有g(x)表示从初始节点S0到节点x的代价,用c(x1,x2)表示从父节点x1到子节点x2的代价,则有:g(x2)=g(x1)+c(x1,x2)第三十三页，共五十一页，编辑于2023年，星期三334代价树广度优先搜索搜索过程：1）把初始节点S0放入OPEN，令g(S0)=0。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点放入OPEN，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，并按各节点的代价对OPEN表中的全部节点进行排序（从小到大），然后转2）。第三十四页，共五十一页，编辑于2023年，星期三34代价树广度优先搜索第三十五页，共五十一页，编辑于2023年，星期三355代价树深度优先搜索搜索过程：1）把初始节点S0放入OPEN，令g(S0)=0。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点按边代价从小到大进行排序放入OPEN首部，并为每一个子节点都配一个指向父节点的指针计算各子节点的代价，然后转2）。第三十六页，共五十一页，编辑于2023年，星期三361.宽度优先、深度优先搜索，其主要的差别是OPEN表中待扩展节点的顺序问题。2.盲目搜索(弱方法)效率低，耗费过多的计算空间与时间。3.若选择最有希望的节点加以扩展，则搜索效率将会大为提高。小结第三十七页，共五十一页，编辑于2023年，星期三373.3启发式搜索启发式搜索：启发式搜索是利用问题本身的某些启发信息，以制导搜索朝着最有希望的方向前进。

启发式搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度，我们总是希望能找到最有希望通向目标节点的待扩展节点优先扩展。一种最常用的方法是定义一个评价函数,:f(x)=g(x)+h(x)g(x)为从初始节点s0到节点x已经实际付出的代价；

h(x)是从节点x到目标节点Sg的最短路径的估计,它体现了问题的启发性信息。h(x)称为启发函数。

第三十八页，共五十一页，编辑于2023年，星期三38

1局部择优搜索

●

局部择优搜索：当一个节点被扩展后，按f(x)对每个子节点计算估价值，并选择最小者作为下一个要考查的节点。由于它每次都只是在子节点的范围中选择要考查的子节点，所以称为局部择优搜索。深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以子节点作为考察范围的，这是它们的共同处。在局部择优搜索中，若令f(x)=g(x),则局部择优搜索就成为代价树的深度优先搜索；若令f(x)=d(x),这里d(x)表示节点x的深度,则局部择优搜索就成为深度优先搜索。所以深度优先搜索和代价树的深度优先搜索可看作局部择优搜索的两个特例。第三十九页，共五十一页，编辑于2023年，星期三39

2全局择优搜索●

全局择优搜索：每次都是从OPEN表的全体节点中选择一个估价值最小的节点进行扩展。在全局择优搜索中，如果f(x)=g(x),则它就成为代价树的广度优先搜索；若令f(x)=d(x)（这里d(x)表示节点x的深度）,则它就成为广度优先搜索。所以广度优先搜索和代价树的广度优先搜索可看作全局择优搜索的两个特例。第四十页，共五十一页，编辑于2023年，星期三40例用全局择优搜索求解重排九宫问题，其初始状态和目标状态如图所示：

设估价函数为f(x)=d(x)+h(x)其中d(x)表示节点x的深度，h(x)表示节点x的格局与目标节点格局不相同的牌数．第四十一页，共五十一页，编辑于2023年，星期三41搜索树八数码问题

第四十二页，共五十一页，编辑于2023年，星期三42第四十三页，共五十一页，编辑于2023年，星期三433启发式搜索算法A基本思想：定义一个评价函数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）三个函数值的的估计值，是一种预测。

第四十四页，共五十一页，编辑于2023年，星期三44

利用评价函数f(n)＝g(n)＋h(n)来排列OPEN表节点顺序的图搜索算法称为A算法。

A算法每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。第四十五页，共五十一页，编辑于2023年，星期三454最佳图搜索算法A﹡（OptimalSearch）

在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*算法是可采纳的。第四十六页，共五十一页，编辑于2023年，星期三46（2）A*算法的最优性（即信息量的比较）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*扩展节点集的子集。（通过搜索树深度应用数学归纳法证明）。第四十七页，共五十一页，编辑于2023年，星期三47（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*算法所扩展的节点序列的f值是非递减的。第四十八页，共五十一页，编辑于2023年，星期三48例题八数码问题:初始状态和目标状态

试用A*算法求解该问题.

第四十九页，共五十一页，编辑于2023年，星期三49

解：（1）估价函数f1(n)=d(n)+w(n)