状态空间搜索策略

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

问题求解搜索第3页，共51页，2023年，2月20日，星期六3

2搜索的一般过程

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

状态与算子第8页，共51页，2023年，2月20日，星期六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）第9页，共51页，2023年，2月20日，星期六9（1,1）（1,2）（1,3）AB（2,1）（2,2）（2,3）（3,1）（3,2）（3,3）求解路径第10页，共51页，2023年，2月20日，星期六10（1,1）AB（2,1）（2,3）（3,3）求解路径第11页，共51页，2023年，2月20日，星期六1133212311A（2,3）B（1,3）A（1,2）二阶TowerofHanoi塔状态空间图(局部)第12页，共51页，2023年，2月20日，星期六12

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

有N个有孔的盘子，最初这些盘子都叠放在柱a上（如图1），要求将这N个盘子借助柱b从柱a移到柱c（如图2），移动时有以下限制，如何移动？每次只能移动一个盘子；大盘不能放在小盘上。第15页，共51页，2023年，2月20日，星期六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第16页，共51页，2023年，2月20日，星期六163．2盲目搜索1广度优先搜索2深度优先搜索3有限深度优先搜索4代价树广度优先搜索5代价树深度优先搜索第17页，共51页，2023年，2月20日，星期六171广度优先搜索1）把初始节点S0放入OPEN。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点放入OPEN的尾部，并为每一个子节点都配一个指向父节点的指针，然后转2）。第18页，共51页，2023年，2月20日，星期六18重排九宫问题重排九宫问题第19页，共51页，2023年，2月20日，星期六19第20页，共51页，2023年，2月20日，星期六20第21页，共51页，2023年，2月20日，星期六21第22页，共51页，2023年，2月20日，星期六22第23页，共51页，2023年，2月20日，星期六232深度优先搜索1）把初始节点S0放入OPEN。2）检查OPEN是否为空，是，无解，退出。3）把OPEN第一个节点（并记该节点为n）取出放入CLOSED。4）考察节点n是否为目标节点，是，得解，退出。5）若节点n不可扩展，转2）。6）扩展节点n，将其子节点放入OPEN的首部，并为每一个子节点都配一个指向父节点的指针，然后转2）。第24页，共51页，2023年，2月20日，星期六24重排九宫问题第25页，共51页，2023年，2月20日，星期六25重排九宫问题第26页，共51页，2023年，2月20日，星期六26重排九宫问题第27页，共51页，2023年，2月20日，星期六27重排九宫问题第28页，共51页，2023年，2月20日，星期六28重排九宫问题第29页，共51页，2023年，2月20日，星期六29重排九宫问题第30页，共51页，2023年，2月20日，星期六30重排九宫问题第31页，共51页，2023年，2月20日，星期六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

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

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

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

第38页，共51页，2023年，2月20日，星期六38

1局部择优搜索

●

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

2全局择优搜索●

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

设估价函数为f(x)=d(x)+h(x)其中d(x)表示节点x的深度，h(x)表示节点x的格局与目标节点格局不相同的牌数．第41页，共51页，2023年，2月20日，星期六41搜索树八数码问题

第42页，共51页，2023年，2月20日，星期六42第43页，共51页，2023年，2月20日，星期六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）三个函数值的的估计值，是一种预测。

第44页，共51页，2023年，2月20日，星期六44

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

A算法每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。第45页，共51页，2023年，2月20日，星期六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*算法是可采纳的。第46页，共51页，2023年，2月20日，星期六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*扩展节点集的子集。（通过搜索树深度应用数学归纳法证明）。第47页，共51页，2023年，2月20日，星期六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值是非递减的。第48页，共51页，2023年，2月20日，星期六48例题八数码问题:初始状态和目标状态

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

第49页，共51页，2023年，2月20日，星期六49

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