第五章状态空间搜索策略课件

第五章状态空间搜索策第五章状态空间搜索策略略2024/7/16第五章状态空间搜索策略5.1 搜索的概念及种类5.2 盲目搜索5.3 启发式搜索第五章状态空间搜索策略5.1 搜索的概念及种类搜索的概念：搜索的概念：找到从初始事实到问题最终答案的一条推理路线，找找到从初始事实到问题最终答案的一条推理路线，找到的这条路线是时间和空间复杂度最小的求解路线到的这条路线是时间和空间复杂度最小的求解路线搜索种类：搜索种类：“盲目搜索盲目搜索”，即系统根据事先确定好的某种固定，即系统根据事先确定好的某种固定排序（依次或随机）调用规则。排序（依次或随机）调用规则。“启发式搜索启发式搜索”，即考虑问题领域可应用的知识，即考虑问题领域可应用的知识，根据具体情况动态地确定规则的排序，优先调用较根据具体情况动态地确定规则的排序，优先调用较合适的规则使用。合适的规则使用。第五章状态空间搜索策略搜索例子：回溯搜索算法搜索例子：回溯搜索算法BACKTRACK（DATA）DATA：当前状态。：当前状态。返回值：返回值：成功成功：返回从当前状态到目标状态的：返回从当前状态到目标状态的路径（以规则表的形式表示）路径（以规则表的形式表示）失败失败：返回：返回FAIL。第五章状态空间搜索策略四皇后问题四皇后问题皇后问题皇后问题 在一个在一个4*4的国际象棋棋盘上，一次一个地摆布四的国际象棋棋盘上，一次一个地摆布四枚棋子，摆好后满足每行、每列和对角线上只允许枚棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子之间不许相互攻击。出现一枚棋子，即棋子之间不许相互攻击。第五章状态空间搜索策略四皇后问题（续）四皇后问题（续）综合数据库：综合数据库：DATA=L(表），表），L的元素属于的元素属于ij，1i,j4。DATA非空，其表元素表示棋子所在的行和列非空，其表元素表示棋子所在的行和列 规则集：规则集：if 1 i 4 且在且在i-1行上有一个皇后行上有一个皇后 then 在在第第ij位置放上皇后。位置放上皇后。搜索策略搜索策略 固定次序：固定次序：R11,R12,R13,R21,R22,R44第五章状态空间搜索策略()第五章状态空间搜索策略()Q(1,1)第五章状态空间搜索策略()QQ(1,1)(1,1)(2,3)第五章状态空间搜索策略()Q(1,1)(1,1)(2,3)第五章状态空间搜索策略()QQ(1,1)(1,1)(2,3)(1,1)(2,4)第五章状态空间搜索策略()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)第五章状态空间搜索策略()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第五章状态空间搜索策略()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第五章状态空间搜索策略()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第五章状态空间搜索策略()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)第五章状态空间搜索策略()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)第五章状态空间搜索策略()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)第五章状态空间搜索策略()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)Q(1,2)(2,4)(3,1)(4,3)第五章状态空间搜索策略5.1 搜索的概念及种类5.2 盲目搜索5.3 启发式搜索5.2.1 状态空间图的一般搜索算法5.2.2 宽度优先搜索策略5.2.3 深度优先搜索策略5.2.4 代价树的宽度优先搜索策略5.2.5 代价树的深度优先搜索策略第五章状态空间搜索策略5.2 盲目搜索策略5.2.1 状态空间图的一般搜索算法状态空间表示法：用来表示问题及其搜索过程的一种方法。(P62)主要构成：（1）状态，描述问题求解过程中不同时刻状况的数据结构；（2）算符：使问题由一个状态变为另一个状态的操作。（3）状态空间：一个问题的全部状态及一切可用算符构成的集合。一般包括3部分（初始状态集合S，算符集合F，目标状态集合G）（4）问题的求解：从S出发经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列构成了问题的一个求解状态空间图：把状态空间的问题求解过程用图的形式表示出来。节点代表状态，弧代表算符第五章状态空间搜索策略5.2.1 状态空间图的一般搜索算法几个概念：扩展：用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程就是求后继节点的过程。已扩展节点：已经求出了其后继节点的节点。未扩展节点：尚未求出后继节点的节点。OPEN表：存放未扩展的节点，记录当前节点及其父节点。CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。图2.26的节点（1，1）能生成两个后继节点（2，1）（3，1）第五章状态空间搜索策略状态空间的一般搜索算法一般搜索算法的描述：建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中建立CLOSED表，且置为空表判断OPEN表是否为空表，若为空，则问题无解，退出选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到S0的路径得到。若不是转扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点，设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；对于已在G中出现过并已在closed表中的M中的节点，确定是否需要修改通向他们后继节点的指针。按某一任意方式或某种策略某一任意方式或某种策略重排OPEN表中节点的顺序转特例第五章状态空间搜索策略图的一些概念：（1）节点深度：根节点深度=0，其它节点深度=父节点深度+1（2）路径 设一节点序列为(n0,n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。（3）路径的消耗值一条路径的消耗值等于连接这条路径各节点间所有消耗值的总和。用C(ni,nj)表示从ni到nj的路径的消耗值。0123第五章状态空间搜索策略节点类型说明.mkmjmln扩展点扩展点n，产生，产生mk：没在：没在OPEN和和CLOSED表中出现过表中出现过mj：在：在OPEN表中出现过表中出现过ml：在：在CLOSED表中出现过表中出现过第五章状态空间搜索策略S123645将要扩展节点将要扩展节点6第五章状态空间搜索策略S126453修改修改4节点的返回指针节点的返回指针第五章状态空间搜索策略S126453将要扩展节点将要扩展节点1第五章状态空间搜索策略S12645修改修改2和和4的返回指针的返回指针第五章状态空间搜索策略5.2 无信息图搜索过程无信息图搜索过程盲目搜索策略盲目搜索策略5.2.2 宽度优先搜索宽度优先搜索5.2.3 深度优先搜索深度优先搜索5.2.4 代价树的宽度优先代价树的宽度优先5.2.5 代价树的深度优先代价树的深度优先第五章状态空间搜索策略1 1、定义、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。2 2、特点、特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。5.2.2 宽度优先搜索策略第五章状态空间搜索策略3 3、宽度优先搜索算法、宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。第五章状态空间搜索策略例：例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：1 2 3 8 4 7 6 55.2.2 宽度优先搜索策略第五章状态空间搜索策略2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标82 3 41 8 7 6 54第五章状态空间搜索策略宽度优先搜索的性质宽度优先搜索的性质当问题有解时，一定能找到解。当问题有解时，一定能找到解。当问题为单位消耗值，且问题有解时，一定能当问题为单位消耗值，且问题有解时，一定能找到最优解。找到最优解。算法与问题无关，具有通用性。算法与问题无关，具有通用性。时间效率和空间效率都比较低。时间效率和空间效率都比较低。第五章状态空间搜索策略1 1、定义、定义 在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。2 2、特点、特点 首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。3 3、深度界限、深度界限 为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。5.2.3 深度优先搜索策略第五章状态空间搜索策略3 3、深度优先搜索算法、深度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出（5）如果没有后继节点，则转向上述第(2)步。(6)扩展节点n，把n的所有后继节点放到OPEN表前前端，并提供从这些后继节点回到n的指针。转向第(2)步。第五章状态空间搜索策略2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789101112131 2 3 8 47 6 5目标第五章状态空间搜索策略深度优先搜索的性质深度优先搜索的性质一般不能保证找到最优解。一般不能保证找到最优解。当深度限制不合理时，可能找不到解。当深度限制不合理时，可能找不到解。最坏情况时，搜索空间等同于穷举。最坏情况时，搜索空间等同于穷举。第五章状态空间搜索策略1 1、定义、定义 状态空间图中各节点之间有向边的代价是不同的，有向边上标有代价的搜索树成为代价搜索树。2 2、特点、特点 每次从OPEN表中选择一个代价最小的节点，移入CLOSED表。3 3、C(i,j):C(i,j):从节点从节点i i到其后继节点到其后继节点j j的连线代价；的连线代价；g g（x x）:从初始节点到任意节点从初始节点到任意节点x x的路径代价；的路径代价；g(j)=g(i)+C(i,j).g(j)=g(i)+C(i,j).5.2.4 代价树的宽度优先搜索第五章状态空间搜索策略4 4、代价树的宽度优先搜索算法、代价树的宽度优先搜索算法(1)把起始节点放到OPEN表中，令g(S0)=0。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中代价最小的节点（即排在最前端的节点n），移入CLOSED的扩展节点表中。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，将他们的所有后继节点放到OPEN表中，并对每个后继节点j计算其总代价g(j)=g(j)+C(i,j),为每个后继节点指向n节点的指针，然后根据节点的代价大小对OPEN表中的所有节点进行从小到大的排序。(7)转向第(2)步。例子：推销员旅行问题例子：推销员旅行问题P193第五章状态空间搜索策略ACBDE768765gC节点n父节点A第五章状态空间搜索策略ACBDE768765gC节点n父节点A66BA77CA第五章状态空间搜索策略ACBDE768765gC节点n父节点A66BA71175CDAB第五章状态空间搜索策略ACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E路线：A-C-E第五章状态空间搜索策略代价树的宽度优先搜索每次从OPEN表中的全体节点中选择代价最小的节点移入CLOSED表进行扩展或判断。代价树的深度优先搜索从刚刚扩展的节点的后继节点中选择一个代价最小的节点移入CLOSED表中，并进行扩展或判断。5.2.5 代价树的深度优先搜索第五章状态空间搜索策略4 4、代价树的深度优先搜索算法、代价树的深度优先搜索算法(1)把起始节点放到OPEN表中，令g(S0)=0。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中的第一个节点（代价最小的节点n），移入CLOSED表。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，并将其后继节点按有向边代价（C(i,j)）从小到大排序后放到OPEN表前端，并为每个后继节点设置指向n节点的指针。(7)转向第(2)步。第五章状态空间搜索策略ACBDE768765gC节点n父节点A第五章状态空间搜索策略ACBDE768765gC节点n父节点A66BA77CA第五章状态空间搜索策略ACBDE768765gC节点n父节点A66BA71175CDAB第五章状态空间搜索策略ACBDE768765gC节点n父节点A66BA71117187578CDECABDD节点扩展顺序：A，B，C，D，E路线：A-B-D-E第五章状态空间搜索策略ACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E路线：A-C-E第五章状态空间搜索策略5.1 搜索的概念及种类5.2 盲目搜索5.3 启发式搜索5.3.1 启发信息与估价函数5.3.2 最佳优先搜索5.3.3 A*搜索算法第五章状态空间搜索策略5.3 启发式图搜索启发式图搜索 5.3.1启发信息与估价函数启发信息与估价函数定义定义利用与问题有关的知识（即：利用与问题有关的知识（即：启发信息启发信息）来引导搜索，达到）来引导搜索，达到减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索方法。方法。核心问题：核心问题：启发信息应用，启发能力度量和如何获得启发信息。启发信息应用，启发能力度量和如何获得启发信息。启发信息的启发信息的强度强度强：降低搜索工作量，但可能导致找不到最优解。强：降低搜索工作量，但可能导致找不到最优解。弱：一般导致工作量加大，极限情况下变为盲目搜索，但可弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。能可以找到最优解。第五章状态空间搜索策略希望：希望：引入启发知识，在保证找到最佳解的前提下，尽可引入启发知识，在保证找到最佳解的前提下，尽可能减少搜索范围，提高搜索效率。能减少搜索范围，提高搜索效率。搜索算法的效果：搜索算法的效果：可以用启发能力的强弱来度量。可以用启发能力的强弱来度量。考虑考虑解路径的消耗值解路径的消耗值和和求得路径所需搜索的消耗求得路径所需搜索的消耗值值两者的某种组合最小。两者的某种组合最小。考虑搜索方法对求解所有可能遇见的问题，其平考虑搜索方法对求解所有可能遇见的问题，其平均的组合消耗最小。均的组合消耗最小。第五章状态空间搜索策略问题的关键问题的关键如何寻找最有希望的节点如何寻找最有希望的节点 启发搜索过程中，要对启发搜索过程中，要对OPEN表进行表进行排序，这就需要有一种方法来计算待排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同扩展节点有希望通向目标节点的不同程度。程度。我们总希望能找到最有希望通向目标我们总希望能找到最有希望通向目标节点的待扩展节点优先扩展。节点的待扩展节点优先扩展。第五章状态空间搜索策略基本思想基本思想定义一个定义一个估价函数估价函数f（Evaluation Function），对），对当前的搜索状态进行评估，找出一个当前的搜索状态进行评估，找出一个“最有希望最有希望”的节点来扩展。的节点来扩展。第五章状态空间搜索策略估价函数的格式：估价函数的格式：f(n)=g(n)+h(n)f(n)：估价函数g(n)：代价函数，初始节点到节点n已实际付出的代价 h(n)：启发函数，从节点n到目标节点的最优路径的估计代价第五章状态空间搜索策略5.3.2 最佳优先搜索最佳优先搜索局部最佳优先搜索局部最佳优先搜索全局最佳优先搜索全局最佳优先搜索局部最佳优先搜索局部最佳优先搜索：(1)把起始节点放到OPEN表中，并计算估价函数f(S0)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中的第一个节点（股价函数最小的节点n），移入CLOSED表。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，并对其所有后继节点计算估价函数f（n）的值，并按其值从小到大排序后放到OPEN表前端，并为每个后继节点设置指向n节点的指针。(7)转向第(2)步。全局最佳优先搜索全局最佳优先搜索：(1)把起始节点放到OPEN表中，并计算估价函数f(S0)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中的第一个节点（股价函数最小的节点n），移入CLOSED表。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，并对其所有后继节点计算估价函数f（n）的值，并为每个后继节点设置指向n节点的指针。把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价函数值从小到大的顺序排序。(7)转向第(2)步。第五章状态空间搜索策略例子定义评价函数：定义评价函数：f(n)=g(n)+h(n)=d(n)+h(n)；d(n)：代表节点的深度，表示从初始节点到当前节点的消耗值；：代表节点的深度，表示从初始节点到当前节点的消耗值；h(n)：为当前节点：为当前节点“不在位不在位”的牌数。的牌数。2 8 31 6 47 51 2 38 47 6 5第五章状态空间搜索策略h计算举例h(n)=4 2 8 31 6 47 51 2 3457 6 8第五章状态空间搜索策略2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s0(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456第五章状态空间搜索策略 A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。令k(ni，nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点，函数k没有定义)。于是，从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n,ti)给出。令h*(n)表示整个目标节点集合ti上所有k(n,ti)中最小的一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n，函数h*没有定义)。5.3.3 A*算法第五章状态空间搜索策略估价函数估价函数f(n)=g(n)+h(n)是对下列函数的一种估计或近似：f*(n)=g*(n)+h*(n)f*(n)：从初始节点到节点n的一条最佳路径的实际代价加上从节点n到目标节点的最佳路径的代价之和。g*(n)：从初始节点到节点n之间最小路径的实际代价 h*(n)：从节点n到目标节点的最小代价路径上代价 恒有：恒有：g*(n)g(n)在在A*算法中，要求启发函数算法中，要求启发函数h(n)是是h*(n)的下界。的下界。h(n)h*(n)极端情况下，若极端情况下，若h(n)=0，一定能找到最佳解路径，一定能找到最佳解路径第五章状态空间搜索策略演讲完毕，谢谢听讲!再见，see you again3rew3rew2024/7/16第五章状态空间搜索策略