1、1第5章 搜索求解策略25.1 基本概念一、状态空间表示法状态空间表示法是用“状态”和“算符”（“操作”）来表示问题的一种方法。基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的(1)状态（state）：表示问题解法中每一步问题状况的数据结构；Q=q0，q1，qnT Q表状态，qi为状态分量(2)算符（operator）：把问题从一种状态变换为另一种状态的手段；称为操作符或算符。F：f1,f2,(3)状态空间：由状态变量和操作表示的符号体系，包含了问题求解时全部可能状态及其相互关系。三元组表示（S，F，G）3例 设有三枚钱币，其排列处在“正，正，反”状态，现允许每次可翻
2、动其中任意一个钱币，问只允许操作三次的情况下，如何翻动钱币使其变成“正，正，正”或“反，反，反”状态。状态：(q1,q2,q3)“正面”用“1”表示，“反面”用“0”表示 初始状态集合：（1,1,0）目标状态集合：（1，1，1），(0,0,0)操作：f1：翻q1，f2：翻q2，f3：翻q3 F=f1,f2,f34例：MC问题问题：3个传教士(Missionary)，3个野人(Cannibal)，一条船，可同时乘坐2个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。问：如何过河？状态：用三元组(m,c,b)表示左岸的传教士、野人和船数。m=0,1,2,3，c=0,1,2,3，b=0
3、,1共44232种状态其中有16种可行，14种不可行（危险），2种达不到。初始状态：S=（3，3，1）或 S331 目标状态：G=（0，0，0）或 S000 操作符（规则）Pij（左右），qij（右左）左右：p01,p10,p11,p02,p20 条件：船在左岸 右左：q01,q10,q11,q02,q20 条件：船在右岸 F=p01,p10,p11,p02,p20,q01,q10,q11,q02,q205MC问题状态空间图状态空间图p passq quitq11q11q02 (2 1 0)不合法p11(0 0 0)(3 3 0)达不到6二、与/或树（图）表示法1、分解：大问题分解为若干个易解
4、子问题，子问题解决了，大问题也就解决了。ABC或图ABCD与图2、变换：大问题变成若干个易解子问题，只要有一个子问题解决了，大问题也就解决了。7一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点端节点8基本概念 本原问题：不能再分解或变换，而且直接可解的子问题。本原问题：不能再分解或变换，而且直接可解的子问题。终止节点：不能分解或变换，可直接求解终止节点：不能分解或变换，可直接求解 可解节点：可解节点：终止节点终止节点“或或”节点，其子节点至少有一个是可解节点节点，其子节点至少有一个是可解节点“与与”节点，其子节点均为可解节点节点，其子节点均为可解节点 不可解节点：不可解节点
5、：可解节点的三个条件都不满足的节点可解节点的三个条件都不满足的节点 解树：解树：由可解节点构成，并可推出初始节点为可解节点的由可解节点构成，并可推出初始节点为可解节点的子树子树9梵塔问题 可以分解为三个子问题：(1)最大盘以上由1至2(2)最大盘由1至3(3)其余盘由2至3 问题的形式化表示：三元组(I,j,k)I-C所在钢针号 j-B所在钢针号 k-A所在钢针号 问题：（1，1，1）（3，3，3）ABC123ABC12310三阶梵塔问题的与/或树（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321
6、）（331）（322）（321）（331）（333）11三、搜索 根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。类型：1、问题表示方式：状态空间搜索 与/或树搜索2、是否使用启发式信息 盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间结果不用来改进控制策略。启发式搜索：搜索过程中加入与问题有关的启发性信息。（动态地确定操作规则排序）125.2 状态空间的搜索策略 基本思想：初态作为当前节点进行扩展生成子节点，检查目标状态是否出现，不出现则按策略选一个子节点进行扩展直到目标状态出现或没有可供扩展的子节点。一、一般的图搜索过程：OPEN
7、表：存放尚未被扩展的节点 CLOSED表：存放已被扩展的节点13图搜索算法：1.把初始节点S放入OPEN表，建立一个仅包含S的图G（搜索图）2.如果OPEN表空，则以失败退出。3.把OPEN表中的第一个节点取出放入CLOSED表，称此节点为n.4.如果n是目标节点，则成功地结束，解路径可通过回溯G中从n到S的指针获得。5.扩展节点n，产生一组子节点。把不是n的祖先的那些子节点记作集合M，把M的这些成员作为n的后继节点加入G中。6.对于M的那些未曾在G中出现的成员，建立到n的指针，并把这些成员加到OPEN表中。对于那些已在G中出现的成员，决定是否要修改它指向父节点的指针。对于那些已在G中出现且已
8、扩展的成员，决定是否要修改其后继节点指向父节点的指针。7.按某种搜索策略重排OPEN表中的节点8.转第2步14图图搜搜索索的的一一般般过过程程开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？扩展节点扩展节点n，将其将其子节点处理后子节点处理后放入放入OPEN表，为每个子节点配置指向节点表，为每个子节点配置指向节点n的指针的指针重排重排OPEN表表失败失败成功成功是是是是否否否否节点节点n可扩展吗？可扩展吗？否否是是15 说明：说明：这个一般的图搜索过程，通过不断循环生成一个显这个一
9、般的图搜索过程，通过不断循环生成一个显式表示的图式表示的图G G（搜索图）和一个搜索图）和一个G G的子集的子集T T（搜索树）搜索树）树树T T是由（是由（6 6）中标记的指针决定的，除根节点）中标记的指针决定的，除根节点s s外，外，G G中每个节点只有一个指针指向中每个节点只有一个指针指向G G中的一个父节点中的一个父节点OPENOPEN表中的节点（未扩展节点）是搜索树的端节点，表中的节点（未扩展节点）是搜索树的端节点，即尚未被选作为扩展的节点；即尚未被选作为扩展的节点；CLOSEDCLOSED表中的节点（已表中的节点（已扩展节点），可以是已被扩展而不能生成后继节点的扩展节点），可以是已
10、被扩展而不能生成后继节点的那些端节点，也可以是树中的非端节点那些端节点，也可以是树中的非端节点（7 7）中对）中对OPENOPEN表上的节点进行排序是为了在（表上的节点进行排序是为了在（3 3）中能选出一个中能选出一个“最好最好”的节点优先扩展，不同的排序的节点优先扩展，不同的排序方法可构成形式多样的专门搜索算法方法可构成形式多样的专门搜索算法如果隐含图是一棵树，不会（如果隐含图是一棵树，不会（6 6）中讨论的特殊节点，）中讨论的特殊节点，否则可能这些节点否则可能这些节点*上述算法的关键一步是（上述算法的关键一步是（7 7），对），对OPENOPEN表的排序，表的排序，即决定节点的扩展顺序，典
11、型的有两种节点扩展顺序，即决定节点的扩展顺序，典型的有两种节点扩展顺序，得到两种搜索算法（广度优先搜索、深度优先搜索）得到两种搜索算法（广度优先搜索、深度优先搜索）16二、宽度优先（广度优先）基本思想是：从节点S0开始，逐层地对节点进行扩展，并考察它是否为目标节点，在第n层节点没有全部考察完之前，不对第n+1层的节点进行扩展。OPEN表：按“先进先出”排v特点：一种高代价搜索，但若有解存在，则必能找到它。17 例子八数码难题（8-puzzle problem）1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈
12、节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。181238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图 八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 3845671238456712384567123845671
13、4151617181920211238456719三、深度优先搜索 首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（先进后出）20问题 不一定能找到解 找到的解不一定是最佳解 为了对深度优先搜索作改进,要解决两个问题：回溯问题;有圈造成死循环问题。21四、有界深度优先搜索 如果问题有解且路径长度dm,则一定可求得解；否则得不到解。问题：dm不易确定 这种方法不一定能找到解路径（如果解路径的深度超出了限制深度）另外它得到的解也不一定是最优解 改进 先定一个较小的dm，若未找到解且closed中有待扩展的节
14、点，就将其送回open表。不断改进dm。最优解：增设一表R，每找到一个解就将其放入R的前面。最后求得的解一定最优22五、代价树的广度优先搜索分枝界限法 有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路径。代价树：各边标有代价值的树-一种加权树 代价计算g(x)-sx 代价g(x2)=g(x1)+c(x1,x2)基本思想：OPEN表中的全部节点按代价从小到大排23代代价价树树的的广广度度优优先先搜搜索索开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移
15、至表移至CLOSED表表n为目标节点吗？为目标节点吗？扩展节点扩展节点n，将其将其子节点处理后子节点处理后放入放入OPEN表，为每个子节点表，为每个子节点配置指向节点配置指向节点n的指针，的指针，计算各节点代价计算各节点代价。把把OPEN表中的全部节点按代价从小到大排表中的全部节点按代价从小到大排失败失败成功成功是是是是否否否否节点节点n可扩展吗？可扩展吗？否否是是24例 下图是一个交通图，设A城市是出发地，E城市是目的地，边上的数字代表两城市之间的交通费。试求从A到E最小费用的旅行路线。Ac1d1e2 825六、代价树的深度优先搜索-爬山法 基本思想：将扩展的后继节点按边代价从小到大的顺序放
16、在OPEN表的前端。代价树的广度优先搜索法是完备的且找到的解一定是最优解 代价树的深度优先搜索法是不完备的且找到的解不一定是最优解26七、启发式搜索 问题提出：从理论上讲穷举式搜索能解决任何状态空间问题，但很显然穷举搜索只能解决状态空间很小的简单问题，对于复杂问题会出现“组合爆炸”n阶Hanoi塔问题的状态空间图中有2的n次方减1个结点；博弈问题中，为了取胜可以将所有的算法都试一下，然后选择最佳走步。就所有可能的棋局数来讲，一字棋是9！=3.6*109，国际象棋是10120，围棋是10761。假设每步可以选择一种棋局，用极限并行速度（10-104秒/步）计算，国际象棋的算法得用1016年即1亿
17、亿年才可以算完。解决：利用问题的启发性信息来引导搜索 减少搜索范围 降低问题复杂度 启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。把利用启发信息的搜索方法叫做启发性搜索方法。27启发性信息类型启发性信息类型1）用于扩展节点的选择扩展节点的选择即决定下一个扩展节点,以免象在广度优先和深度优先搜索中那样盲目地扩展2）用于生成节点的选择即用于决定生成哪个或哪几个后继节点,而不是生成所有的节点3）用于删除节点的选择即决定用于从搜索树中抛弃或修剪的节点我们讨论的主要是基于“扩展节点的选择”的启发式搜索，这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这
18、种搜索叫做有序搜索(ordered search)。1、估价函数-评估节点的方法用来估算节点希望程度的量度，叫做估价函数 28f(x)=g(x)+h(x)其中:f(x):从初始节点S0到目标节点Sg的最优路径的代价估计值 g(x)为从初始节点S0到节点x的实际代价值。h(x)为启发函数,是从节点x到目标节点Sg的最优路径的代价h*(n)的估计值。g(x)、h(x)作用分析 一般地,在f(n)中,g(n)的比重越大,越倾向于宽度优先搜索方式;h(n)的比重越大,越倾向于深度优先搜索方式。保持g(n)项就保持了搜索的宽度优先趋势,这有利于搜索的完备性,但影响搜索的效率。在特殊情况下,如果只希望找到
19、达到目标结点的路径而不关心已付出的代价,则g(n)的作用可以忽略。h(n)g(n)时,也可以忽略g(n),这时有f(n)=h(n),这有利于搜索的效率,但影响搜索的完备性。29 定义h（x）的原则：节点x处在最佳路径上的摡率 节点x与目标节点集之间的距离度量或差异度量 根据格局或状态的特点来打分 一般来说,评价一个结点的价值,必须综合考虑两方面的因素:已经付出的代价和将要付出的代价。启发式算法通常由两部分组成:启发方法 使用该方法搜索状态空间的算法。启发式搜索基本思想：以一般的图搜索算法为基础 定义启发函数h（x）计算每个待扩展节点的启发函数值 每次扩展节点后以节点的启发函数值为依据对待扩展节
20、点排序每次扩展节点后以节点的启发函数值为依据对待扩展节点排序 实质：选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。30开始开始把把S放入放入OPEN表，表，计算估价函数计算估价函数 f(s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CLOSED表表i为目标节点吗？为目标节点吗？扩展扩展i，得后继节点得后继节点j，计算计算f(j)，提供返回提供返回节点节点i的指针，利用的指针，利用f(j)对对OPEN表重新排表重新排序，调整亲子关系及指针序，调整亲子关系及指针失败失败成功成功图图 有序搜索算法框图有序搜索算法框图是是否否是是否否v算法31
21、例：八数码难题（8-puzzle problem）f(n)=h(n)+g(n)=w(n)+d(n)h(n)=w(n),w(n)是将牌不在位个数,例如,与目标状态相比,初始状态w(n)=4,即有4个将牌(1,2,6,8)不在位。g(n)=d(n),d(n)是搜索的深度。一般根节点(初始状态)的深度是为0,其他子节点深度为父结点深度加1。规定规则为空格移动(走步规则),规则选取顺序为:左、上、右、下。控制策略为:选取评价函数值最小者进行扩展(往下搜索)。12384567（目标状态）12384567（初始状态）325714563123845671238456712384567（4）（6）（6）212
22、3845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）图 八数码难题的有序搜索树123846（4）73334A算法算法 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为A算法算法。实现类型：局部择优搜索、全局择优搜索2、局部择优搜索-类似深度优先 基本思想：在当前扩展的子节点中选f(x)值最小的子节点为下一个考察的节点 实现：节点n扩展后的各子节点计算出估价值后，按由小到大次序放到OPEN表的首部
23、分析：可把深度优先、代价树的深度优先看成其特例。3、全局择优搜索-类似广度优先 节点n扩展后的各子节点计算出估价值后，送入OPEN表，然后OPEN表中全部节点按估价值由小到大排354、A*算法(Algorithm A*)几个有用的记号 f（x）=g（x）+h（x）f*(x)=g*（x）+h*（x）g*（x）：从节点S到节点x的一条最佳路径的实际代价 h*（x）：从节点 x到某目标节点的一条最佳路径的代价f*(x)：从S开始约束通过节点x的一条最佳路径的代价 分析：g是g*（x）的估计；对于 g（n）来说，一个明显的选择就是搜索树中从到n这段路径的代价，这一代价可以由从n到寻找指针时，把所遇到的
24、各段弧线的代价加起来给出（这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g（x）g*（x）。h是h*（x）的估计；对于h（n），它依赖于有关问题的领域的启发信息。36A*算法-又称最佳图搜索算法，由著名人工智能学者Nilsson提出。定义：如果A算法中使用的启发函数h(n)对任何节点n都有h(n)h*(n)，则称其为A*算法(Algorithm A*)。对于宽度优先搜索算法，h(n)=0，满足h(n)h*(n)。宽度优先算法是A*算法的特殊情形。A*算法的性质：（1）可采纳性 如果一个搜索算法对于任何具有解路径的图都能找到一条最佳解路径。则称此算法是可采纳的。结
25、论：A*算法是可采纳的 证明：对有限图，A*算法一定会在有限步结束 对无限图，只有从S0到Sg有路径存在，则A*算法也必然会结束 A*算法一定会终止在最优路径上37a)对有限图，A*算法一定会在有限步结束证明：因为搜索图为有限图，所以会出现以下情况：算法找到解，则成功结束（算法第4步）算法找不到解，则必然会因OPEN表变空而结束（算法第2步）b)对无限图，只有从S0到Sg有路径存在，则A*算法也必然会结束证明：（分2步）第1步证明：A*结束前,OPEN表中必存在节点n，它是最佳路径上的一个节点，且满足 f(n)f*(s)而根据b)证明可知：在A*结束前，OPEN表中存在最优路径上的节点n,且有
26、f(n)f*(s),所以 f(n)f*(s)h1(n),则在搜索过程中，被A2扩展的节点也必定由A1扩展,即A1扩展的节点不会比A2扩展的节点少，亦即A2扩展的节点集是A1扩展的节点集的子集。41证明:使数学归纳法,对节点的深度应用归纳法对节点的深度应用归纳法。(1)对深度d(n)=0的节点(即初始节点s),若s为目标节点,则A1和A2都不扩展s,否则A1和A2都扩展了s(2)设深度d(n)k时,对所有路径的端节点,定理结论都成立。(3)证明d(n)=k+1时,所有路径的端节点,结论成立。（反证法）设A2搜索树上有一个节点n(d(n)=k+1)被A2扩展了,而对应于A1搜索树上的这个节点n,没
27、有被A1扩展。根据归纳法假设条件,A1扩展了n的父节点,n是在A1搜索树上,因此A1结束时,n必定保留在其OPEN表上,n没有被A1选择扩展,有 f1(n)f*(s),即g1(n)+h1(n)f*(s)所以 h1(n)f*(s)-g1(n)(1)另一方面A2扩展了n,有 f2(n)f*(s),即 g2(n)+h2(n)f*(s)所以 h2(n)f*(s)-g2(n)(2)由于d=k时,A2扩展的节点,A1也一定扩展,故有 g1(n)g2(n)(因A1扩展的节点数可能较多)所以 h1(n)f*(s)-g1(n)f*(s)-g2(n)(3)比较式(2)、(3)可得:至少在节点n上有h1 h2(n)
28、,这与定理的前提条件矛盾,因此存在节点n的假设不成立。证毕 42（3）单调性-指h(n)的单调限制 在A*算法中,每当要扩展一个节点时,都要先检查其子节点是否已在OPEN表或CLOSED表中,有时还需要调整指向父节点的指针,这就增加了搜索的代价.如果对启发函数h(n)加上单调限制,就可以减少检查及调整的工作量,提高搜索效率.单调限制是指h(n)满足两个条件:(1)h(Sg)=0(2)设nj是节点ni的任意子节点,则有:h(ni)-h(nj)c(ni,nj)其中,Sg是目标节点,c(ni,nj)是节点ni到其子节点 nj的弧代价.将上式改写成:h(ni)h(nj)+c(ni,nj)可看出:节点n
29、i到目标节点最优费用的估价不会超过从节点ni到其子节点nj的弧代价加上从nj到目标节点最优费用的估价.可以证明:(1)如果满足单调限制,则当A*选择节点n扩展时,就已经发现了通向节点n的最佳路径.即:g(n)=g*(n)(2)如果A*满足单调限制,则A*所扩展节点序列的估价函数值是单调上升的.43A*算法的理论意义 A*算法的理论意义在于给出了求解最佳解的条件h(n)h*(n)。对给定的问题,函数h*(n)(n是变量)在问题有解的条件下客观上是存在的。但在问题求解过程中不可能都明确知道 例：八数码难题h(n)=w(n)(将牌不在位个数)，显然有h(n)=W(n)h*(n)h(n)=p(n)（每
30、一个将牌与其目标位置之间距离的总和），显然有h(n)=p(n)h*(n)h(n)取值分析：h(n)=0:即启发函数启发信息为0,f(n)=h(n)+g(n)=g(n)d(n)(搜索深度),此实际上是宽度优先搜索。h(n)=W(n):f(n)=h(n)+g(n)=W(n)+d(n)(搜索深度)(前面例子中：初始状态:W(n)=4,d(n)=0)h(n)=p(n):f(n)=h(n)+g(n)=p(n)+d(n)(搜索深度)。(前面例子中：初始状态：p(n)=5,d(n)=0)都是都是A*算法算法44h(n)=p(n)“”节点为被扩的节点“”节点为生成的节点d)455.3 与或树（图）搜索与或树（
31、图）搜索博奕树搜索有序搜索启发式搜索深度优先搜索广度优先搜索盲目搜索46与或图表示法特点 与或图表示问题特点 可分解的问题 可变换的问题 例：如何上班问题 开自家车 车况好（自己修车，他人修车）足够燃料（车开到加油站，自带燃料）步行 身体状况好 足够的时间 公交车 步行到车站 骑车到车站47上班问题开自家车步行乘公交车车况好燃料足他人修自己修他人修加油站自带燃油燃油箱身体好时间够步行到车站骑车到车站 与或图的构成 与节点：分解问题 或节点：变换问题 弧:相关节点的联结 终止节点：本原问题 与或图表示法 与节点,或节点,终止节点 端节点 可解节点 不可解节点 解图48 与或图例子1可解节点23B
32、端节点（不可扩展节点）54t1At2t3t4终止节点开自家车步行车况好燃料足自己修他人修加油站自带燃油燃油箱身体好时间够步行到车站骑车到车站上班问题乘公交车49一、与或树搜索的一般过程1、几个概念 可解标示过程：由可解子节点来确定父节点，祖父节点等为可解节点的过程 不可解标示过程：由不可解子节点来确定父节点，祖父节点等为不可解节点的过程2、基本思想：对与或树（图）标记（示）可解与不可解的递归过程，通过对终节点的可解与否最终确定初始节点是否可解。扩展（自上而下）标示（自下而上）结束条件：初始节点为可解或不可解50搜索过程（1）把原始问题作为初始节点S0,并将其作为当前节点（2）应用分解或变换算符
33、过程对当前节点进行扩展（3）为每个子节点设置指向父节点的指针（4）选择适当的子节点作为当前节点，反复应用（2）（3）步，在此期间要多次应用可解标示过程和不可解标示过程，直到初始节点被标示为可解节点或不可解节点。搜索树：搜索过程所形成的节点和指针结构 解树：若已标示初始节点是可解的，则由初始节点及其下属的可解节点就构成了解树 节点的删除可解节点的不可解后裔不可解节点的全部后裔51二、与或树的广度优先搜索（1）把初始节点S0放入OPEN表（2）把OPEN表中的第一个节点（n）取出放入CLOSED表（3）n可扩展 OPEN表按“先进先出”排 子节点加入OPEN表尾时要判断其是否为终止节点。若是，则标
34、示可解并调用可解标示过程标示其祖先节点。若S0可解则结束，否则删去具有可解祖先的子节点。（4）n不可扩展 标示为不可解节点并调用不可解标示过程标示其祖先节点。若S0不可解则结束，否则删去具有不可解祖先的子节点。（5）转（2）52解树构成：1,2,3,4,5,t1,t2,t3,t453三、与或树的深度优先搜索（1）把初始节点S0放入OPEN表（2）把OPEN表中的第一个节点（n）取出放入CLOSED表（3）n可扩展 OPEN表按“后进先出”排 子节点加入OPEN表首时要判断其是否为终止节点。若是，则标示可解并调用可解标示过程标示其祖先节点。若S0可解则结束，否则删去具有可解祖先的子节点。（4）n
35、不可扩展（若深度界限，当不可扩展处理）标示为不可解节点并调用不可解标示过程标示其祖先节点。若S0不可解则结束，否则删去具有不可解祖先的子节点。（5）转（2）54四、与或树的有序搜索 根据代价决定搜索路线-求最优解树 是与或图启发式搜索的一种特例 与或图启发式搜索算法也称为AO*算法1、扩展节点时代价计算节点x的代价为h(x)X：终止节点 h(x)=0 端节点（非终止）h(x)=或节点 与节点55根节点的代价-解树的代价 左边的解树S0,A,t1,C,t3H(s0)=2+4+6+2=14(按和)H(s0)=8+2=10(按最大)右边的解树s0,B,t2,D,t4H(s0)=1+5+3+2=11(
36、按和)H(s0)=6+2=8(按最大)无论按和代价还是最大代价，右边的解树都是最优解树56问题1）由于h(yi)不是终止节点则无法知道其值 引入启发函数计算h(yi)2）每当有一代新节点生成时，都要自下而上地重新计算其先辈节点的代价h3）选出扩展的节点应是代价最小的部分解树（图）中的节点 希望树：可能成为最优解树的一部分2、希望树T 在搜索过程中任一时刻求出的局部解图（树）其代价都是最小的。这个局部解图即是希望图（树）1)S0在T中 2)x在T中 若x为“或”接点，则满足minc(x,yi)+h(yi)的子节点yi也在T中 若x为“与”接点，则其所有子节点yi也在T中573、与或树的有序搜索过
37、程 目标：寻找最小代价的解树，最优解图(树)方法：按解图生成的方法,分步生成局部解图,重新计算节点的耗散值（代价）,从中选择一个代价最小的局部解图用于扩展，同时使用标示过程。与其他搜索过程的不同点：从OPEN表中选希望树T的端节点N作为当前节点送入CLOSED表 扩展N时所产生的子节点均需计算自身及其先辈节点的h值 具体过程：（1）把S0放入OPEN表中，计算h(S0)（2）计算希望树T（3）依次在OPEN表中取出T的端节点n放入CLOSED表（4）根据n的三种可能做以下工作：58n的三种可能：“终止节点”、不是但可扩展、不是且不可扩展“终止节点”标记n为可解节点在T上应用可解标记过程，对n的
38、先辈节点中的所有可解节点进行标记如果初始节点S0被标记为可解，则T就是最优解树，成功退出否则，从OPEN表中删去具有可解先辈的所有节点转（2）59不是“终止节点”但可扩展扩展节点n，生成 n的所有子节点把这些子节点都放入OPEN表，并为每一个子节点设置指向父节点n的指针计算这些子节点及其先辈节点的h值转（2）不是“终止节点”且不可扩展标记n为不可解节点在T上应用不可解标记过程，对n的先辈节点中的所有不可解节点进行标记如果初始节点S0被标记为不可解，则问题无解，失败退出否则，从OPEN表中删去具有不可解先辈的所有节点转（2）60与或树示例：设：在搜索过程中每次扩展两层且按一层或节点、一层与节点的
39、间隔方式进行扩展按和计算。10、S0扩展两层 S0 A D B C E F 3 3 3 2 判断：右子树为当前的T按“和”计算6120、扩展E S0 9 A D 8 11 B C E 7 2 F 3 3 7 6 3 2 2 2 30计算T右子树h(s0)=12左子树h(s0)=9所以T应改为左子树按“和”计算6240、扩展B S0 9 A D 8 11 B 3 3C E 7 2 F 2G J6 7 6 3 2 2 2 H0 I0 K2 L2 因 H，I可解，调用可解标记过程得：G，B可解计算T，仍是左子树删除可解节点的后裔（B的后裔）6350、扩展C S0 9 A D 8 11 B 3 3C
40、E 7 2 F 2G J6 7 6 3 2 2 2 H0 I0 K2 L2 M 2 O9 N 0 P 0 5 2 N，P可解，调用可解标记过程得：M，C，A可解，所以推出S0为可解节点，结束。64五、博弈树的启发式搜索1、博弈树 诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈树：以一方立场（我方）来看博弈过程用图表示出来，得到的与或树 初始节点为博弈的初始格局。与或节点交替出现，我方扩展节点之间是“或”的关系，敌方为“与”节点。使我方获胜的终局都是本原问题，使敌方获胜的终局都是不可解节点 博弈的特点：二人零和，全信息，非偶然 二人零和：结果必有一方获胜，或平局。全信息：参与者都了
41、解对手当前和过去的走步，也可以推测出将要走的招术。非偶然:根据当前情况（一般不能看到终局），选取对自己最为有利而对对方最为不利的对策65 如何找到博弈必胜的策略 思路：尽选择对自己有利的方案，向前尽量多看几步 基本概念 静态估值：每个结点的势态估计值。倒推值：由每个结点的静态估值倒推出父结点的估计值。或节点(MAX节点)，其倒推值选 取各分枝中最大值。与节点(MIN节点)，其倒推值选取各分枝中最小值。基本思想(极大极小法)。以一定深度生成博奕树(扩展一级或二级),应用各节点的静态估计值计算出(倒推出)每个非端节点的倒退值。选取”或”节点(我方，MAX)得分极大的棋步(对或节点来说)选取”与”节
42、点(敌方，MIN)得分极小的棋步(对与节点来说)逐级搜索，求解博奕问题。662、博奕树极大极小搜索一字棋游戏极小极大分析法：设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。用叉号表示MAX，用圆圈代表MIN。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义：设棋局为P，估价函数为e(P)。e(p)=(所有空格都放上MAX的棋子之后,MAX的三子成线(行、列、对角)的总数)(所有空格都放上MIN的棋子之后,MIN的三子成线(行、列、对角)的总数)67e(p)若P是M
43、AX必胜的棋局，则e(P)+。若P是B必胜的棋局，则e(P)-。具有对称性的两个棋局算作一个棋局 求解过程 搜索树 端节点的估计值-表示MAX不可再分+表示MIN不可再分 极大极小分析方法计算倒推值 选取对MAX最有利的方案68应用极大极小分析法产生深度为2的博奕树，以决定下一步应该如何走棋静态估值倒推值69六、剪枝枝术 极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了-剪枝技术。基本思想：边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一
44、些分枝，从而节约了机器开销，提高了搜索效率。SABC=2D=7E=1F未定70 值“与”节点：取当前子节点中最小倒推值作为其倒推值的上界-值“或”节点：取当前子节点中最大倒推值作为其倒推值的下界-值 剪枝枝术的一般规律 任何“或”节点x的值大于等于其先辈节点的值,则x以下的分枝可以停止搜索，并使x的倒推值为.这种剪枝称为剪枝.任何“与”节点x的值小于等于其先辈节点的值,则x以下的分枝可以停止搜索，并使x的倒推值为.这种剪枝称为剪枝 一个节点的第一个子节点的倒推值是很重要。71S0S2S1S3S4S5S63523剪枝-剪枝剪枝剪枝S0BAE=2=1=1=555S981-2FGHMNPQ2L4*=-2=2*72-剪枝技术的搜索效率分析 要进行-修剪，必须至少使某一部分的搜索树生长到最大深度，因为和值必须以端节点的静态估值为依据。因此采用-剪枝技术通常都要使用某种深度优先的搜索方法。在一次搜索期间修剪的枝数取决于早期的、值与最终倒推值之间的近似程度。起始节点的最终倒推值等于某个端节点的静态估值。如果在深度优先搜索过程中第一次就遇到这个端节点，则修剪枝数最大。当前修剪枝数最大时，需要生成和估计的端节点数就最少。
