状态空间搜索策略课件

第五章状态空间搜索策略S0Sg问题全状态空间问题的搜索空间解路径主要内容：状态空间的搜索问题第五章状态空间搜索策略S0Sg问题全状态空间问题的搜索15.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.1搜索的概念及种类25.1搜索的概念及种类搜索的概念：找到从初始事实到问题最终答案的一条推理路线，找到的这条路线是时间和空间复杂度最小的求解路线搜索种类：“盲目搜索”，即系统根据事先确定好的某种固定排序（依次或随机）调用规则。“启发式搜索”，即考虑问题领域可应用的知识，根据具体情况动态地确定规则的排序，优先调用较合适的规则使用。5.1搜索的概念及种类搜索的概念：3搜索例子：回溯搜索算法

BACKTRACK（DATA）

DATA：当前状态。返回值：成功：返回从当前状态到目标状态的路径（以规则表的形式表示） 失败：返回FAIL。搜索例子：回溯搜索算法 BACKTRACK（DATA）4四皇后问题皇后问题

在一个4*4的国际象棋棋盘上，一次一个地摆布四枚棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子之间不许相互攻击。四皇后问题皇后问题5四皇后问题（续）综合数据库：DATA=L(表），L的元素属于{ij}，1≤i,j≤4。DATA非空，其表元素表示棋子所在的行和列规则集：if1≤i≤4且在i-1行上有一个皇后then在第ij位置放上皇后。搜索策略固定次序：R11,R12,R13,…,R21,R22,R44四皇后问题（续）综合数据库：DATA=L(表），L的元素属6()()7()Q((1,1))()Q((1,1))8()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))9()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,111()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,112()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,113()Q((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)14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)15()((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)16()((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)17()((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)18()((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))()((1,1))((1,1)(2,3))((1,1)195.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.2.1状态空间图的一般搜索算法5.2.2宽度优先搜索策略5.2.3深度优先搜索策略5.2.4代价树的宽度优先搜索策略5.2.5代价树的深度优先搜索策略5.1搜索的概念及种类5.2.1状态空间图的一般搜索算法205.2盲目搜索策略

5.2.1状态空间图的一般搜索算法状态空间表示法：用来表示问题及其搜索过程的一种方法。(P62)主要构成：（1）状态，描述问题求解过程中不同时刻状况的数据结构；（2）算符：使问题由一个状态变为另一个状态的操作。（3）状态空间：一个问题的全部状态及一切可用算符构成的集合。一般包括3部分（初始状态集合S，算符集合F，目标状态集合G）（4）问题的求解：从S出发经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列构成了问题的一个求解状态空间图：把状态空间的问题求解过程用图的形式表示出来。节点代表状态，弧代表算符5.2盲目搜索策略

5.2.1状态空间图的一般搜索算法215.2.1状态空间图的一般搜索算法几个概念：扩展：用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程就是求后继节点的过程。已扩展节点：已经求出了其后继节点的节点。未扩展节点：尚未求出后继节点的节点。OPEN表：存放未扩展的节点，记录当前节点及其父节点。CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。图2.26的节点（1，1）能生成两个后继节点（2，1）（3，1）5.2.1状态空间图的一般搜索算法几个概念：图2.26的22状态空间的一般搜索算法一般搜索算法的描述：建立一个只含有初始节点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表中节点的顺序转③特例状态空间的一般搜索算法一般搜索算法的描述：特例23图的一些概念：（1）节点深度： 根节点深度=0，其它节点深度=父节点深度+1（2）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。（3）路径的消耗值 一条路径的消耗值等于连接这条路径各节点间所有消耗值的总和。用C(ni,nj)表示从ni到nj的路径的消耗值。0123图的一些概念：012324节点类型说明…...…...…...…...…...mkmjmln扩展点n，产生mk：没在OPEN和CLOSED表中出现过mj：在OPEN表中出现过ml：在CLOSED表中出现过节点类型说明…...…...…...…...…...mkmj25S123645将要扩展节点6S123645将要扩展节点626S126453修改4节点的返回指针S126453修改4节点的返回指针27S126453将要扩展节点1S126453将要扩展节点128S12645修改2和4的返回指针S12645修改2和4的返回指针295.2无信息图搜索过程

——盲目搜索策略5.2.2宽度优先搜索5.2.3深度优先搜索5.2.4代价树的宽度优先5.2.5代价树的深度优先5.2无信息图搜索过程

——盲目搜索策略5.2.2宽度优301、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)。2、特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

5.2.2宽度优先搜索策略1、定义5.2.2宽度优先搜索策略313、宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。3、宽度优先搜索算法32例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：123847655.2.2宽度优先搜索策略例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题3323184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标82341876542323283234宽度优先搜索的性质当问题有解时，一定能找到解。当问题为单位消耗值，且问题有解时，一定能找到最优解。算法与问题无关，具有通用性。时间效率和空间效率都比较低。宽度优先搜索的性质当问题有解时，一定能找到解。351、定义在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索(depth-firstsearch)。2、特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。3、深度界限为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。5.2.3深度优先搜索策略1、定义5.2.3深度优先搜索策略363、深度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出（5）如果没有后继节点，则转向上述第(2)步。(6)扩展节点n，把n的所有后继节点放到OPEN表前端，并提供从这些后继节点回到n的指针。转向第(2)步。3、深度优先搜索算法372318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目标2323283238深度优先搜索的性质一般不能保证找到最优解。当深度限制不合理时，可能找不到解。最坏情况时，搜索空间等同于穷举。深度优先搜索的性质一般不能保证找到最优解。391、定义状态空间图中各节点之间有向边的代价是不同的，有向边上标有代价的搜索树成为代价搜索树。2、特点每次从OPEN表中选择一个代价最小的节点，移入CLOSED表。3、C(i,j):从节点i到其后继节点j的连线代价；g（x）:从初始节点到任意节点x的路径代价；g(j)=g(i)+C(i,j).5.2.4代价树的宽度优先搜索1、定义5.2.4代价树的宽度优先搜索404、代价树的宽度优先搜索算法

(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)步。例子：推销员旅行问题P1934、代价树的宽度优先搜索算法例子：推销员旅行问题P19341ACBDE768765gC节点n父节点AACBDE768765gC节点n父节点A42ACBDE768765gC节点n父节点A66BA77CAACBDE768765gC节点n父节点A66BA77CA43ACBDE768765gC节点n父节点A66BA71175CDABACBDE768765gC节点n父节点A66BA77CA44ACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E路线：A---C----EACBDE768765gC节点n父节点A66BA77CA节点45代价树的宽度优先搜索每次从OPEN表中的全体节点中选择代价最小的节点移入CLOSED表进行扩展或判断。代价树的深度优先搜索从刚刚扩展的节点的后继节点中选择一个代价最小的节点移入CLOSED表中，并进行扩展或判断。5.2.5代价树的深度优先搜索代价树的宽度优先搜索每次从OPEN表中的全体节点中选择代价最464、代价树的深度优先搜索算法

(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)步。4、代价树的深度优先搜索算法47ACBDE768765gC节点n父节点AACBDE768765gC节点n父节点A48ACBDE768765gC节点n父节点A66BA77CAACBDE768765gC节点n父节点A66BA77CA49ACBDE768765gC节点n父节点A66BA71175CDABACBDE768765gC节点n父节点A66BA77CA50ACBDE768765gC节点n父节点A66BA71117187578CDECABDD节点扩展顺序：A，B，C，D，E路线：A----B----D----EACBDE768765gC节点n父节点A66BA77CA节点51ACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E路线：A---C----EACBDE768765gC节点n父节点A66BA77CA节点525.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.3.1启发信息与估价函数5.3.2最佳优先搜索5.3.3A*搜索算法5.1搜索的概念及种类5.3.1启发信息与估价函数535.3启发式图搜索

5.3.1启发信息与估价函数定义利用与问题有关的知识（即：启发信息）来引导搜索，达到减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索方法。核心问题：启发信息应用，启发能力度量和如何获得启发信息。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解。弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。5.3启发式图搜索

5.3.1启发信息与估价函数定义54希望：引入启发知识，在保证找到最佳解的前提下，尽可能减少搜索范围，提高搜索效率。搜索算法的效果：可以用启发能力的强弱来度量。考虑解路径的消耗值和求得路径所需搜索的消耗值两者的某种组合最小。考虑搜索方法对求解所有可能遇见的问题，其平均的组合消耗最小。希望：引入启发知识，在保证找到最佳解的前提下，尽可能减少搜索55问题的关键如何寻找最有希望的节点启发搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度。我们总希望能找到最有希望通向目标节点的待扩展节点优先扩展。问题的关键如何寻找最有希望的节点56基本思想定义一个估价函数f（EvaluationFunction），对当前的搜索状态进行评估，找出一个“最有希望”的节点来扩展。基本思想定义一个估价函数f（EvaluationFunct57估价函数的格式： f(n)=g(n)+h(n) f(n)：估价函数 g(n)：代价函数，初始节点到节点n已实际付出的代价h(n)：启发函数，从节点n到目标节点的最优路径的估计代价估价函数的格式：585.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)步。5.3.2最佳优先搜索局部最佳优先搜索局部最佳优先搜索：59例子定义评价函数： f(n)=g(n)+h(n)=d(n)+h(n)； d(n)：代表节点的深度，表示从初始节点到当前节点的消耗值； h(n)：为当前节点“不在位”的牌数。

2831647512384765例子定义评价函数：2831260h计算举例 h(n)=42

831

647512345768h计算举例 h(n)=42831612831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s0(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)目标123456283283283262A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。令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.3A*算法A*算法是一种有序搜索算法，其特点在于对估价函数的定义63估价函数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，一定能找到最佳解路径估价函数f(n)=g(n)+h(n)是对下列函数的一64A*条件举例8数码问题h(n)=“不在位”的牌数h*(n)=“不在位”牌的距离和2

831

647512345768将牌1：1将牌2：1将牌6：1将牌8：2A*条件举例8数码问题2831265第五章状态空间搜索策略S0Sg问题全状态空间问题的搜索空间解路径主要内容：状态空间的搜索问题第五章状态空间搜索策略S0Sg问题全状态空间问题的搜索665.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.1搜索的概念及种类675.1搜索的概念及种类搜索的概念：找到从初始事实到问题最终答案的一条推理路线，找到的这条路线是时间和空间复杂度最小的求解路线搜索种类：“盲目搜索”，即系统根据事先确定好的某种固定排序（依次或随机）调用规则。“启发式搜索”，即考虑问题领域可应用的知识，根据具体情况动态地确定规则的排序，优先调用较合适的规则使用。5.1搜索的概念及种类搜索的概念：68搜索例子：回溯搜索算法

BACKTRACK（DATA）

DATA：当前状态。返回值：成功：返回从当前状态到目标状态的路径（以规则表的形式表示） 失败：返回FAIL。搜索例子：回溯搜索算法 BACKTRACK（DATA）69四皇后问题皇后问题

在一个4*4的国际象棋棋盘上，一次一个地摆布四枚棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子之间不许相互攻击。四皇后问题皇后问题70四皇后问题（续）综合数据库：DATA=L(表），L的元素属于{ij}，1≤i,j≤4。DATA非空，其表元素表示棋子所在的行和列规则集：if1≤i≤4且在i-1行上有一个皇后then在第ij位置放上皇后。搜索策略固定次序：R11,R12,R13,…,R21,R22,R44四皇后问题（续）综合数据库：DATA=L(表），L的元素属71()()72()Q((1,1))()Q((1,1))73()QQ((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))74()Q((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))75()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,176()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,177()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,178()Q((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)79()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)80()((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)81()((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)82()((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)83()((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))()((1,1))((1,1)(2,3))((1,1)845.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.2.1状态空间图的一般搜索算法5.2.2宽度优先搜索策略5.2.3深度优先搜索策略5.2.4代价树的宽度优先搜索策略5.2.5代价树的深度优先搜索策略5.1搜索的概念及种类5.2.1状态空间图的一般搜索算法855.2盲目搜索策略

5.2.1状态空间图的一般搜索算法状态空间表示法：用来表示问题及其搜索过程的一种方法。(P62)主要构成：（1）状态，描述问题求解过程中不同时刻状况的数据结构；（2）算符：使问题由一个状态变为另一个状态的操作。（3）状态空间：一个问题的全部状态及一切可用算符构成的集合。一般包括3部分（初始状态集合S，算符集合F，目标状态集合G）（4）问题的求解：从S出发经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列构成了问题的一个求解状态空间图：把状态空间的问题求解过程用图的形式表示出来。节点代表状态，弧代表算符5.2盲目搜索策略

5.2.1状态空间图的一般搜索算法865.2.1状态空间图的一般搜索算法几个概念：扩展：用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程就是求后继节点的过程。已扩展节点：已经求出了其后继节点的节点。未扩展节点：尚未求出后继节点的节点。OPEN表：存放未扩展的节点，记录当前节点及其父节点。CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。图2.26的节点（1，1）能生成两个后继节点（2，1）（3，1）5.2.1状态空间图的一般搜索算法几个概念：图2.26的87状态空间的一般搜索算法一般搜索算法的描述：建立一个只含有初始节点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表中节点的顺序转③特例状态空间的一般搜索算法一般搜索算法的描述：特例88图的一些概念：（1）节点深度： 根节点深度=0，其它节点深度=父节点深度+1（2）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。（3）路径的消耗值 一条路径的消耗值等于连接这条路径各节点间所有消耗值的总和。用C(ni,nj)表示从ni到nj的路径的消耗值。0123图的一些概念：012389节点类型说明…...…...…...…...…...mkmjmln扩展点n，产生mk：没在OPEN和CLOSED表中出现过mj：在OPEN表中出现过ml：在CLOSED表中出现过节点类型说明…...…...…...…...…...mkmj90S123645将要扩展节点6S123645将要扩展节点691S126453修改4节点的返回指针S126453修改4节点的返回指针92S126453将要扩展节点1S126453将要扩展节点193S12645修改2和4的返回指针S12645修改2和4的返回指针945.2无信息图搜索过程

——盲目搜索策略5.2.2宽度优先搜索5.2.3深度优先搜索5.2.4代价树的宽度优先5.2.5代价树的深度优先5.2无信息图搜索过程

——盲目搜索策略5.2.2宽度优951、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)。2、特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

5.2.2宽度优先搜索策略1、定义5.2.2宽度优先搜索策略963、宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。3、宽度优先搜索算法97例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：123847655.2.2宽度优先搜索策略例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题9823184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标82341876542323283299宽度优先搜索的性质当问题有解时，一定能找到解。当问题为单位消耗值，且问题有解时，一定能找到最优解。算法与问题无关，具有通用性。时间效率和空间效率都比较低。宽度优先搜索的性质当问题有解时，一定能找到解。1001、定义在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索(depth-firstsearch)。2、特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。3、深度界限为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。5.2.3深度优先搜索策略1、定义5.2.3深度优先搜索策略1013、深度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出（5）如果没有后继节点，则转向上述第(2)步。(6)扩展节点n，把n的所有后继节点放到OPEN表前端，并提供从这些后继节点回到n的指针。转向第(2)步。3、深度优先搜索算法1022318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目标23232832103深度优先搜索的性质一般不能保证找到最优解。当深度限制不合理时，可能找不到解。最坏情况时，搜索空间等同于穷举。深度优先搜索的性质一般不能保证找到最优解。1041、定义状态空间图中各节点之间有向边的代价是不同的，有向边上标有代价的搜索树成为代价搜索树。2、特点每次从OPEN表中选择一个代价最小的节点，移入CLOSED表。3、C(i,j):从节点i到其后继节点j的连线代价；g（x）:从初始节点到任意节点x的路径代价；g(j)=g(i)+C(i,j).5.2.4代价树的宽度优先搜索1、定义5.2.4代价树的宽度优先搜索1054、代价树的宽度优先搜索算法

(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)步。例子：推销员旅行问题P1934、代价树的宽度优先搜索算法例子：推销员旅行问题P193106ACBDE768765gC节点n父节点AACBDE768765gC节点n父节点A107ACBDE768765gC节点n父节点A66BA77CAACBDE768765gC节点n父节点A66BA77CA108ACBDE768765gC节点n父节点A66BA71175CDABACBDE768765gC节点n父节点A66BA77CA109ACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E路线：A---C----EACBDE768765gC节点n父节点A66BA77CA节点110代价树的宽度优先搜索每次从OPEN表中的全体节点中选择代价最小的节点移入CLOSED表进行扩展或判断。代价树的深度优先搜索从刚刚扩展的节点的后继节点中选择一个代价最小的节点移入CLOSED表中，并进行扩展或判断。5.2.5代价树的深度优先搜索代价树的宽度优先搜索每次从OPEN表中的全体节点中选择代价最1114、代价树的深度优先搜索算法

(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)步。4、代价树的深度优先搜索算法112ACBDE768765gC节点n父节点AACBDE768765gC节点n父节点A113ACBDE768765gC节点n父节点A66BA77CAACBDE768765gC节点n父节点A66BA77CA114ACBDE768765gC节点n父节点A66BA71175CDABACBDE768765gC节点n父节点A66BA77CA115ACBDE768765gC节点n父节点A66BA71117187578CDECABDD节点扩展顺序：A，B，C，D，E路线：A----B----D----EACBDE768765gC节点n父节点A66BA77CA节点116ACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E路线：A---C----EACBDE768765gC节点n父节点A66BA77CA节点1175.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.3.1启发信息与估价函数5.3.2最佳优先搜索5.3.3A*搜索算法5.1搜索的概念及种类5.3.1启发信息与估价函数1185.3启发式图搜索

5.3.1启发信息与估价函数定义利用与问题有关的知识（即：启发信息）来引导搜索，达到减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索方法。核心问题：启发信息应用，启发能力度量和如何获得启发信息。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解。弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。5.3启发式图搜索

5.3.1启发信息与估价函数定义119希望：引入启发知识，在保证找到最佳解的前提下，尽可能减少搜索范围，提高搜索效率。搜索算法的效果：可以用启发能力的强弱来度量。考虑解路径的消耗值和求得路径所需搜索的消耗值两者的某种组合最小。考虑搜索方法对求解所有可能遇见的问题，其平均的组合消耗最小。希望：引入启发知识，在保证找到最佳解的前提下，尽可能减少搜索120问题的关键如何寻找最有希望的节点启发搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的不同程度。我们总希望能找到最有希望通向目标节点的待扩展节点优先扩展。问题的关键如何寻找最有希望的节点121基本思想定义一个估价函数f（EvaluationFunction），对当前的搜索状态进行评估，找出一个“最有希望”的节点来扩展。基本思想定义一个估价函数f（EvaluationFunct122估价函数的格式： f(n)=g(n)+h(n) f(n)：估价函数 g(n)：代价函数，初始节点到节点n已实际付出的代价h(n)：启发函数，从节点n到目标节点的最优路径的估计代价估价函数的格式：1235.3.2最佳优先搜索