人工智能第五章

1、第5章 搜索求解策略5.1基基本本概念一、状态态空间表表示法状态空间间表示法法是用“状态”和“算算符”（“操作作”）来来表示问问题的一一种方法法。基于解答答空间的的问题表表示和求求解方法法，它是是以状态态和算符符为基础础来表示示和求解解问题的的(1)状状态态（state）：表表示问题题解法中中每一步步问题状状况的数数据结构构；Q=q0，q1，qnTQ表状态态，qi为状态分分量(2)算算符符（operator）：把把问题从从一种状状态变换换为另一一种状态态的手段段；称为操作作符或算算符。F：f1,f2,状态空间间：由状状态变量量和操作作表示的的符号体体系，包包含了问问题求解解时全部可能能状态及及

2、其相互互关系。三元组表表示（S，F，G）例设有三枚枚钱币，其排列列处在“正，正正，反”状态，现允许许每次可可翻动其其中任意意一个钱钱币，问问只允许许操作三三次的情情况下，如何翻翻动钱币币使其变变成“正正，正，正”或或“反，反，反反”状态态。状态：(q1,q2,q3)“正面”用“1”表示示，“反反面”用用“0”表示初始状态态集合：（1,1,0）目标状态态集合：（1，1，1），(0,0,0)操作：f1：翻翻q1，f2：翻q2，f3：翻q3F=f1,f2,f3例：MC问题题问题：3个传教士士(Missionary)，3个野人(Cannibal)，一条船，可同时时乘坐2个人，要要求在任任何时刻刻，在河

3、河的两岸岸，传教教士人数数不能少少于野人人的人数数。问：如何过过河？状态：用三元组组(m,c,b)表示示左岸的的传教士士、野人人和船数数。m=0,1,2,3，c=0,1,2,3，b=0,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,q

4、20MC问题状态空间间图ppassqquitq11q11q02(210)不合法p11(00 0)(33 0)达不到二、与/或树（图）表表示法1、分解解：大问问题分解解为若干干个易解解子问题题，子问问题解决决了，大大问题也也就解决决了。ABC或图ABCD与图2、变换换：大问问题变成成若干个个易解子子问题，只要有有一个子子问题解解决了，大问题题也就解解决了。一些关于于与或图图的术语语HMBCDEFGAN父节点与节点弧线或节点子节点端节点基本概念念本原问题题：不能能再分解解或变换换，而且且直接可可解的子子问题。终止节点点：不能能分解或或变换，可直接接求解可解节点点：终止节点点“或”节节点，其其子节点

5、点至少有有一个是是可解节节点“与”节节点，其其子节点点均为可可解节点点不可解节节点：可解节点点的三个个条件都都不满足足的节点点解树：由可解节节点构成成，并可可推出初初始节点点为可解解节点的的子树梵塔问题题可以分解解为三个个子问题题：(1)最大盘以以上由1至2(2)最大盘由由1至3(3)其余盘由由2至3问题的形形式化表表示：三元组(I,j,k)I -C所在钢针针号j -B所在钢针针号k-A所在钢针针号问题：（1，1，1）（3，3，3）ABC123ABC123三阶梵塔塔问题的的与/或或树（113） （123） （111） （113） （123） （122） （111） （333） （122） （3

6、22） （111） （122） （322）（333） （321） （331） （322） （321） （331） （333） 三、搜索索根据问题题的实际际情况不不断寻找找可利用用的知识识，从而而构造一一条代价价较少的的推理路路线，使使问题得得到圆满满解决的的过程。类型：1、问题题表示方方式：状态空间间搜索与/或树树搜索2、是否否使用启启发式信信息盲目搜索索：按预定的的控制策策略进行行搜索，在搜索索过程中中获得的的中间结结果不用用来改进进控制策策略。启发式搜搜索：搜索过程程中加入入与问题题有关的的启发性性信息。（动态态地确定定操作规规则排序序）5.2状状态态空间的的搜索策策略基本思想想：初态作为

7、为当前节节点进行行扩展生生成子节节点，检检查目标标状态是是否出现现，不出出现则按按策略选选一个子子节点进进行扩展展直到目目标状态态出现或或没有可可供扩展展的子节节点。一、一般般的图搜搜索过程程：OPEN表：存存放尚未未被扩展展的节点点CLOSED表表：存放放已被扩扩展的节节点图搜索算算法：1.把初始节节点S放入OPEN表，建立立一个仅仅包含S的图G（搜索图）2.如果OPEN表空，则则以失败败退出。3.把OPEN表中的第第一个节节点取出出放入CLOSED表，称此此节点为为n.4.如果n是目标节节点，则则成功地地结束，解路径径可通过过回溯G中从n到S的指针获获得。5.扩展节点点n，产生一组组子节点

8、点。把不不是n的祖先的那那些子节节点记作作集合M，把M的这些成成员作为为n的后继节节点加入入G中。6.对于M的那些未未曾在G中出现的的成员，建立到到n的指针，并把这这些成员员加到OPEN表中。对于那些些已在G中出现的的成员，决定是是否要修修改它指指向父节节点的指指针。对于那些些已在G中出现且且已扩展展的成员员，决定定是否要要修改其其后继节节点指向向父节点点的指针针。7.按某种搜搜索策略略重排OPEN表中的节节点8.转第2步图搜索的的一般过过程开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？扩展节点n，将其子节点处理后放入OPEN表，为每个

9、子节点配置指向节点n的指针重排OPEN表失败成功是是否否节点n可扩展吗？否是说明：这个一般般的图搜搜索过程程，通过过不断循循环生成成一个显显式表示示的图G（搜索图）和一个个G的子集T（搜索树）树T是由（6）中标记记的指针针决定的的，除根根节点s外，G中每个节节点只有有一个指指针指向向G中的一个个父节点点OPEN表中的节节点（未未扩展节节点）是是搜索树树的端节节点，即即尚未被被选作为为扩展的的节点；CLOSED表中的节节点（已已扩展节节点），可以是是已被扩扩展而不不能生成成后继节节点的那那些端节节点，也也可以是是树中的的非端节节点（7）中对OPEN表上的节节点进行行排序是是为了在在（3）中能选选

10、出一个个“最好好”的节节点优先先扩展，不同的的排序方方法可构构成形式式多样的的专门搜搜索算法法如果隐含含图是一一棵树，不会（6）中讨论论的特殊殊节点，否则可可能这些些节点*上上述算法法的关键键一步是是（7），对OPEN表的排序序，即决决定节点点的扩展展顺序，典型的的有两种种节点扩扩展顺序序，得到到两种搜搜索算法法（广度度优先搜搜索、深深度优先先搜索）二、宽度度优先（广度优优先）基本思想想是：从节点S0开始，逐逐层地对对节点进进行扩展展，并考考察它是是否为目目标节点点，在第第n层节点没没有全部部考察完完之前，不对第第n+1层的节点点进行扩扩展。OPEN表：按“先进先先出”排排特点：一种高代代价搜

11、索索，但若若有解存存在，则则必能找找到它。例子八数码难难题（8-puzzleproblem）1238456712384567（目标状态）（初始状状态）规定：将牌移入入空格的的顺序为为：从空空格左边边开始顺顺时针旋旋转。不不许斜向向移动，也不返返回先辈辈节点。从图可见见，要扩扩展26个节点，共生成成46个节点之之后才求求得解（目标节节点）。1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图八八数码难难题的

12、宽宽度优先先搜索树树13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567三、深度度优先搜搜索首先扩展展最新产产生的(即最深深的)节节点。深深度相等等的节点点可以任任意排列列。与宽度优优先搜索索算法最最根本的的不同在在于：将将扩展的的后继节节点放在在OPEN表的的前端。（先进进后出）问题不一定能能找到解解找到的解解不一定定是最佳佳解为了对深深度优先先搜索作作改进,要

13、解决两两个问题题：回溯问题题;有圈造成成死循环环问题。四、有界界深度优优先搜索索如果问题题有解且且路径长长度dm,则一定定可求得得解；否否则得不不到解。问题：dm不易确定定这种方法法不一定定能找到到解路径径（如果果解路径径的深度度超出了了限制深深度）另外它得得到的解解也不一一定是最最优解改进先定一个个较小的的dm，若未找找到解且且closed中有待待扩展的的节点，就将其其送回open表。不不断改进进dm。最优解：增设一一表R，每找到到一个解解就将其其放入R的前面面。最后后求得的的解一定定最优五、代价价树的广广度优先先搜索分枝界界限法有些问题题并不要要求有应应用算符符序列为为最少的的解，而而是要

14、求求具有某某些特性性的解。搜索树树中每条条连接弧弧线上的的有关代代价以及及随之而而求得的的具有最最小代价价的解答答路径。代价树：各边标标有代价价值的树树-一种种加权树树代价计算算g(x)-sx代价g(x2)=g(x1)+c(x1,x2)基本思想想：OPEN表表中的全全部节点点按代价价从小到到大排代价树的的广度优优先搜索索开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？扩展节点n，将其子节点处理后放入OPEN表，为每个子节点配置指向节点n的指针，计算各节点代价。把OPEN表中的全部节点按代价从小到大排失败成功是是否否节点n可扩展吗？否是例下

15、图是一一个交通通图，设设A城市市是出发发地，E城市是是目的地地，边上上的数字字代表两两城市之之间的交交通费。试求从从A到E最小费费用的旅旅行路线线。Ac1d1e28六、代价价树的深深度优先先搜索-爬爬山法基本思想想：将扩扩展的后后继节点点按边代代价从小小到大的的顺序放放在OPEN表表的前端端。代价树的的广度优优先搜索索法是完完备的且且找到的的解一定定是最优优解代价树的的深度优优先搜索索法是不不完备的的且找到到的解不不一定是是最优解解七、启发发式搜索索问题提出出：从理论上上讲穷举举式搜索索能解决决任何状状态空间间问题，但很显显然穷举举搜索只只能解决决状态空空间很小小的简单单问题，对于复复杂问题题

16、会出现现“组合合爆炸”n阶Hanoi塔问题题的状态态空间图图中有2的n次次方减1个结点点；博弈问题题中，为为了取胜胜可以将将所有的的算法都都试一下下，然后后选择最最佳走步步。就所所有可能能的棋局局数来讲讲，一字字棋是9！=3.6*109，国国际象棋棋是10120，围围棋是10761。假设每每步可以以选择一一种棋局局，用极极限并行行速度（10-104秒/步）计计算，国国际象棋棋的算法法得用1016年即即1亿亿亿年才可可以算完完。解决：利用问题题的启发发性信息息来引导导搜索减少搜索索范围降低问题题复杂度度启发信息息：进行行搜索技技术一般般需要某某些有关关具体问问题领域域的特性性的信息息，把此此种信

17、息息叫做启启发信息息。把利利用启发发信息的的搜索方方法叫做做启发性性搜索方方法。启发性信信息类型型1）用于于扩展节点点的选择择即决定下下一个扩扩展节点点,以免免象在广广度优先先和深度度优先搜搜索中那那样盲目目地扩展展2）用于于生成节节点的选选择即用于决决定生成成哪个或或哪几个个后继节节点,而而不是生生成所有有的节点点3）用于于删除节节点的选选择即决定用用于从搜搜索树中中抛弃或或修剪的的节点我们讨论论的主要要是基于于“扩展展节点的的选择”的启发发式搜索索，这种种搜索总总是选择择“最有有希望”的节点点作为下下一个被被扩展的的节点。这种搜搜索叫做做有序搜搜索(ordered search)。1、估价

18、价函数-评评估节点点的方法法用来估算算节点希希望程度度的量度度，叫做做估价函函数f(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),这这有利于于搜索的的效率, 但影影响搜索索的完备备性。定义h（x）的的原则：节点x处处在最佳佳路径上上的摡率率节点x与与目标节节点集之之间的距距离度量量或差异异度量根据格局局或状态态的特点点来打分分一般来说说,评评价一个个结点的的价值, 必须须综合考考虑两方方面的因因素:已已经付付出的代代价和将将要付出出的代价价。启发式算算法通常常由两部部分组成成:启发方法法使用该方方法搜索索状态空空间的算算

20、法。启发式搜搜索基本本思想：以一般的的图搜索索算法为为基础定义启发发函数h（x）计算每个个待扩展展节点的的启发函函数值每次扩展展节点后后以节点点的启发发函数值值为依据据对待扩扩展节点点排序实质：选选择OPEN表表上具有有最小f值的节节点作为为下一个个要扩展展的节点点。开始把S放入OPEN表，计算算估价函函数f (s)OPEN表为空表表？选取OPEN表中f值最小的的节点i放入CLOSED表i为目标节节点吗？扩展i，得后继节节点j，计算f(j)，提供返回回节点i的指针，利用f(j)对OPEN表重新排排序，调调整亲子子关系及及指针失败成功图有序搜索索算法框框图是否是否算法例：八数码难难题（8-puz

21、zleproblem）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（初始状态）5714563123845671238456712

22、384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）图八八数码难难题的有有序搜索索树123846（4）7A算法利用评价价函数f(n) =g(n)+ h(n)来来排列列OPEN表节节点顺序序的图搜搜索算法法称为A算法。实现类型型：局部部择优搜搜索、全全局择优优搜索2、局部部择优搜搜索-类类似深度度优先基本思想想：在当当前扩展展的子节节点中选选f(x)值值最小的的子节点点为下一一个考察察的节点点实现：

23、节节点n扩扩展后的的各子节节点计算算出估价价值后，按由小小到大次次序放到到OPEN表的的首部分析：可可把深度度优先、代价树树的深度度优先看看成其特特例。3、全局局择优搜搜索-类类似广度度优先节点n扩扩展后的的各子节节点计算算出估价价值后，送入OPEN表，然然后OPEN表表中全部部节点按按估价值值由小到到大排4、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开始始约束通通过节点点

24、x的一一条最佳佳路径的的代价分析：g是g*（x）的的估计；对于g（n）来说说，一个个明显的的选择就就是搜索索树中从从到n这段路路径的代代价，这这一代价价可以由由从n到到寻找找指针时时，把所所遇到的的各段弧弧线的代代价加起起来给出出（这条条路径就就是到目目前为止止用搜索索算法找找到的从从S到n的最小小代价路路径)。这个定定义包含含了g（x）g*（x） 。h是h*（x）的的估计；对于h（n），它依依赖于有有关问题题的领域域的启发发信息。A*算法法-又称最佳佳图搜索索算法，由著名名人工智智能学者者Nilsson提出出。定义：如如果A算算法中使使用的启启发函数数h(n)对任任何节点点n都有有h(n)h

25、*(n)，则则称其为为A*算算法(AlgorithmA*)。对于宽度度优先搜搜索算法法，h(n)=0，满满足h(n)h*(n)。宽度优优先算法法是A*算法的的特殊情情形。A*算法法的性质质：（1）可可采纳性性如果一个个搜索算算法对于于任何具具有解路路径的图图都能找找到一条条最佳解解路径。则称此此算法是是可采纳纳的。结论：A*算法法是可采采纳的证明：对有限图图，A*算法法一定会会在有限限步结束束对无限图图，只有有从S0到Sg有路径径存在，则A*算法也也必然会会结束A*算法法一定会会终止在在最优路路径上a)对有有限图， A*算法一一定会在在有限步步结束证明：因因为搜索索图为有有限图，所以会会出现以

26、以下情况况：算法找到到解，则则成功结结束（算算法第4步）算法找不不到解，则必然然会因OPEN表变空空而结束束（算法法第2步步）b)对无无限图，只有从从S0到到Sg有有路径存存在，则则A*算算法也必必然会结结束证明： （分分2步）第1步证明：A*结束前, OPEN表中必存存在节点点n，它是最佳路路径上的的一个节节点，且且满足f(n)f*(s)而根据b)证明明可知：在A*结束前，OPEN表中中存在最最优路径径上的节节点n, 且有有f(n)f*(s),所所以f(n)f*(s) h1(n),则在搜索索过程中中，被被A2扩展的节节点也必必定由A1扩展,即A1扩展的节节点不会会比A2扩展的节节点少，亦即A

27、2扩展的节节点集是是A1扩展的节节点集的的子集。证明:使数学归归纳法,对节点的的深度应应用归纳纳法。对深度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,没有被A1扩展。根据归归纳法假假设条件件, A1扩展了n的父节点点, n是在A1搜索树上上,因此A1结束时, n必定保留留在其OPE

28、N表上,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上有h1h2(n),这与定理理的前提提条件矛矛盾,因此存在在节点n的假设不不成立。证毕（3）单单调性-指h(n)

29、的单调调限制在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)可看出:节点ni到目标节节点最优优费用的的估价不不

30、会超过过从节点点ni到其子节节点nj的弧代价价加上从从nj到目标节节点最优优费用的的估价.可以证明明:(1)如果满足足单调限限制,则当A*选择节点点n扩展时,就已经发发现了通通向节点点n的最佳路路径.即:g(n)=g*(n)(2)如果A*满足单调调限制,则A*所扩展节节点序列列的估价价函数值值是单调调上升的的.A*算法法的理论论意义A*算法法的理论论意义在在于给出出了求解解最佳解解的条件件h(n) h*(n)。对给定的的问题, 函数数h*(n)(n是是变量)在问题题有解的的条件下下客观上上是存在在的。但但在问题题求解过过程中不不可能都都明确知知道例：八数数码难题题h(n) =w(n)(将牌牌不

31、在位位个数)，显然有h(n) =W(n)h*(n)h(n) =p(n)（每一个将将牌与其其目标位位置之间间距离的的总和），显然有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(

32、n) =5,d(n)=0)都是A*算法h(n) =p(n)“”节节点为被被扩的节节点“”节节点为生生成的节节点d)5.3与或树（图）搜搜索与或图表表示法特特点与或图表表示问题题特点可分解的的问题可变换的的问题例：如何何上班问问题开自家车车车况好（自己修修车，他他人修车车）足够燃料料（车开开到加油油站，自自带燃料料）步行身体状况况好足够的时时间公交车步行到车车站骑车到车车站上班问题开自家车步行乘公交车车况好燃料足他人修自己修他人修加油站自带燃油燃油箱身体好时间够步行到车站骑车到车站与或图的的构成与节点：分解问问题或节点：变换问问题弧:相关关节点的的联结终止节点点：本原原问题与或图表表示法与节点,

33、或节点点,终止止节点端节点可解节点点不可解节节点解图与或图例例子1可解节点23B端节点（不可扩展节点）54t1At2t3t4终止节点开自家车步行车况好燃料足自己修他人修加油站自带燃油燃油箱身体好时间够步行到车站骑车到车站上班问题乘公交车一、与或或树搜索索的一般般过程1、几个个概念可解标示示过程：由可解解子节点点来确定定父节点点，祖父父节点等等为可解解节点的的过程不可解标标示过程程：由不可可解子节节点来确确定父节节点，祖祖父节点点等为不不可解节节点的过过程2、基本本思想：对与或树树（图）标记（示）可可解与不不可解的的递归过过程，通通过对终终节点的的可解与与否最终终确定初初始节点点是否可可解。扩展

34、（自自上而下下）标示（自自下而上上）结束条件件：初始始节点为为可解或或不可解解搜索过程程（1）把原始始问题作作为初始始节点S0,并将其作作为当前前节点（2）应用分解解或变换换算符过过程对当前节节点进行行扩展（3）为每个个子节点点设置指指向父节节点的指指针（4）选择适适当的子子节点作作为当前前节点，反复应应用（2）（3）步，在在此期间间要多次次应用可可解标示示过程和和不可解解标示过过程，直直到初始始节点被被标示为为可解节节点或不不可解节节点。搜索树：搜索过过程所形形成的节节点和指指针结构构解树：若已标标示初始始节点是是可解的的，则由由初始节节点及其其下属的的可解节节点就构构成了解解树节点的删删除

35、可解节点点的不可可解后裔裔不可解节节点的全全部后裔裔二、与或或树的广广度优先先搜索（1）把把初始节节点S0放入OPEN表（2）把把OPEN表中中的第一一个节点点（n）取出放放入CLOSED表（3）n可扩扩展OPEN表按“先进先出出”排子节点加加入OPEN表表尾时要要判断其其是否为为终止节节点。若若是，则则标示可可解并调调用可解解标示过过程标示示其祖先先节点。若S0可解则则结束，否则删删去具有有可解祖祖先的子子节点。（4）n不可可扩展标示为不不可解节节点并调调用不可可解标示示过程标标示其祖祖先节点点。若S0不可可解则结结束，否否则删去去具有不不可解祖祖先的子子节点。（5）转转（2）解树构成成：1

36、,2,3,4,5,t1,t2,t3,t4三、与或或树的深深度优先先搜索（1）把把初始节节点S0放入OPEN表（2）把把OPEN表中中的第一一个节点点（n）取出放放入CLOSED表（3）n可扩扩展OPEN表按“后进先先出”排排子节点加加入OPEN表表首时要要判断其其是否为为终止节节点。若若是，则则标示可可解并调调用可解解标示过过程标示示其祖先先节点。若S0可解则则结束，否则删删去具有有可解祖祖先的子子节点。（4）n不可可扩展（若深度度界限限，当不不可扩展展处理）标示为不不可解节节点并调调用不可可解标示示过程标标示其祖祖先节点点。若S0不可可解则结结束，否否则删去去具有不不可解祖祖先的子子节点。（

37、5）转转（2）四、与或或树的有有序搜索索根据代价价决定搜搜索路线线-求求最优解解树是与或图图启发式式搜索的的一种特特例与或图启启发式搜搜索算法法也称为为AO*算法1、扩展展节点时时代价计计算节点x的的代价为为h(x)X：终止节点点h(x) =0端节点（非终止止）h(x)=或节点与节点根节点的的代价-解树树的代价价左边的解解树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(按和和)H(s0)=6+2=8(按按最大)无论按和和代价还还是最大大代价，右边的的解树都都是最优优解树

38、问题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中中3、与或或树

39、的有有序搜索索过程目标：寻寻找最小小代价的的解树，最优解解图(树树)方法：按按解图生生成的方方法,分分步生成成局部解解图,重重新计算算节点的的耗散值值（代价价）,从从中选选择一个个代价最最小的局局部解图图用于扩扩展，同同时使用用标示过过程。与其他搜搜索过程程的不同同点：从OPEN表中中选希望望树T的的端节点点N作为为当前节节点送入入CLOSED表扩展N时时所产生生的子节节点均需需计算自自身及其其先辈节节点的h值具体过程程：（1）把把S0放放入OPEN表表中，计计算h(S0)（2）计计算希望望树T（3）依依次在OPEN表中取取出T的的端节点点n放入入CLOSED表（4）根根据n的的三种可可能做以

40、以下工作作：n的三种种可能：“终终止节点点”、不不是但可可扩展、不是且且不可扩扩展“终止节节点”标记n为可解解节点在T上上应用可可解标记记过程，对n的的先辈节节点中的的所有可可解节点点进行标标记如果初初始节点点S0被被标记为为可解，则T就就是最优优解树，成功退退出否则，从OPEN表表中删去去具有可可解先辈辈的所有有节点转（2）不是“终终止节点点”但可可扩展扩展节节点n，生成n的所所有子节节点把这些些子节点点都放入入OPEN表，并为每每一个子子节点设设置指向向父节点点n的指指针计算这这些子节节点及其其先辈节节点的h值转（2）不是“终终止节点点”且不不可扩展展标记n为不可可解节点点在T上上应用不不

41、可解标标记过程程，对n的先辈辈节点中中的所有有不可解解节点进进行标记记如果初初始节点点S0被被标记为为不可解解，则问问题无解解，失败败退出否则，从OPEN表表中删去去具有不不可解先先辈的所所有节点点转（2）与或树示示例：设设：在在搜索过过程中每每次扩展展两层且且按一层层或节点点、一层层与节点点的间隔隔方式进进行扩展展按和计计算。10、S0扩扩展两层层判断：右右子树为为当前的的T按“和”计算20、扩展E30计算T右子树h(s0)=12左子树h(s0)=9所以T应应改为左左子树按“和”计算40、扩展B因 H，I可解解，调用用可解标标记过程程得：G，B可可解计算T，仍是左左子树删除可解解节点的的后裔

42、（B的后后裔）50、扩展CN，P可可解，调调用可解解标记过过程得：M，C，A可可解，所以推出出S0为为可解节节点，结结束。五、博弈弈树的启启发式搜搜索1、博弈弈树诸如下棋棋、打牌牌、竞技技、战争争等一类类竞争性性智能活活动称为为博弈。博弈树：以一方方立场（我方）来看博博弈过程程用图表表示出来来，得到到的与或或树初始节点点为博弈弈的初始始格局。与或节点点交替出出现，我我方扩展展节点之之间是“或”的的关系，敌方为为“与”节点。使我方获获胜的终终局都是是本原问问题，使使敌方获获胜的终终局都是是不可解解节点博弈的特特点：二二人零和和，全信信息，非非偶然二人零和和：结果果必有一一方获胜胜，或平平局。全信息：参与者者都了解解对手当当前和过过去的走走步，也也可以推推测出将将要走的的招术。非偶然:根据当前前情况（一般不不能看到到终局），选取对自自己最为为有利而而对对方方最为不不利的对对策如何找到到博弈必必胜的策策略思路：尽尽选择对对自己有有利的方方案，向向前尽量量多看几几步基本概念念静态估值值：每个个结点的的势态估估计值。倒推值：由每个个结点的的静态估估值倒推推出父结结点的估估计值。或节点(MAX节点)，其倒倒推值选选 取各各分枝中中最大值值。与节点(MIN节点)，其倒倒推值选选取各分分枝中最最小值。基本思想想(极大大极小法法)。以