人工智能原理

人工智能原理

第2章搜索技术

〔上〕1 本章内容

2.1搜索与问题求解

2.2无信息搜索战略

2.3启发式搜索战略

2.4部分搜索算法

2.5约束满足问题

2.6博弈搜索

参考书目

附录A*算法可采用性的证明第2章搜索技术22.1搜索与问题求解

2.1.1问题与问题的解

2.1.2问题实例

2.1.3搜索战略第2章搜索技术3搜索与问题求解问题求解过程是搜索答案(目的)的过程/所以问题求解技术也叫搜索技术—经过对形状空间的搜索而求解问题的技术问题求解智能体是一种基于目的的智能体在寻觅到达目的的过程中，当智能面子对多个未知的选项时，首先检验各个不同的导致知评价的形状的能够行动序列，然后选择最正确序列—这个过程就是搜索第2章搜索技术42.1.1问题与问题的解问题可以方式化地定义为4个组成部分智能体的初始形状(即搜索的开场)后继函数—智能体采取的能够行动的描画，通常为<行动，后继形状>/初始形状和后继函数隐含地定义了问题的形状空间/形状空间中的一条途径是经过行动序列衔接起来的一个形状序列目的测试—检查给定的形状是不是目的途径耗散函数—每条途径都有一个数值化的耗散值，反映了性能度量/求解问题的代价第2章搜索技术5问题的解问题的解就是初始形状到目的形状的途径解的优劣由途径耗散函数量度(代价)最优解就是途径耗散函数值最小的途径上述解题过程把处理一个问题的过程描画出来，称之为解题知识的过程性表示过程性知识与陈说性知识相对搜索过程解题的特点—没有直接的方法(公式)可以求解，而是一步一步的探求第2章搜索技术6形状空间数据基：代表了所要处理的问题，有初始形状，能够有目的形状也能够没有形状空间：在解题过程中的每一时辰，数据基都处于一定的形状，数据基一切能够形状的集合称为形状空间有向图：假设把每个形状看成一个节点，那么整个形状空间是一个有向图/该图不一定全连通，即从某些形状不一定能到达另外一些形状第2章搜索技术7问题的可解性可解的：在每个连通部分，每个弧代表一个运算符，将形状改动/假设从代表初始形状的节点出发，有一条途径通向目的形状，那么称此目的形状所代表的问题在当前初始形状下是可解的搜索空间：在解题过程中到达过的一切形状的集合，称为搜索空间不同于形状空间，搜索空间只是其中一部分形状空间和搜索空间都属于过程性知识表示第2章搜索技术82.1.2问题实例玩具问题八数码游戏(九宫图)河内塔八皇后问题真空吸尘器世界现实问题游览商问题超大规模集成电路的规划自动装配排序/蛋白质设计互联网搜索第2章搜索技术9八数码游戏八数码游戏：1-8数字(棋子)/9个方格(棋盘格)/1个空格可用如下方式的规那么来表示数字经过空格进展挪动：<a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9>共24条规那么=4角*2+4边*3+1中间*4搜索顺序举例： (1)优先挪动行数小的棋子(数字) (2)同一行中优先挪动列数大的棋子约束规那么：不使分开既定位置的数字数添加第2章搜索技术10八数码游戏的搜索树第2章搜索技术既定位置=终态11八数码问题方式化初始形状初始形状向量—规定向量中各分量对应的位置，各位置上的初始数字后继函数挪动规那么—按照某条规那么挪动数字，将得到的新向量目的测试新向量能否是目的形状(也是向量方式)途径耗散函数每次挪动代价为1第2章搜索技术12河内塔(1)河内塔问题：n个大小不等的圆盘从一个柱子移到另一个柱子，共有3个柱子(n阶河内塔问题)约束：从第1根柱子挪动到第3根柱子上去，利用第2根柱子/每次挪动1个盘子，且挪动过程必需是小盘落大盘描画：设每个形状为(a1,a2,a3,…,an),ai=1,2,3—表示第i个盘子在第1/2/3根柱子上第2章搜索技术13河内塔(2)递归定义：{(a1,a2,a3,…,an)}为n阶河内塔的形状集合，那么{(a1,a2,a3,…,an,1),(a1,a2,a3,…,an,2),(a1,a2,a3,…,an,3)}是n+1阶河内塔的形状集合1阶河内塔有3个形状，2阶河内塔有9个形状，n阶河内塔有3n个形状，给出1/2/3阶河内塔的形状图第2章搜索技术14河内塔问题图解第2章搜索技术15河内塔问题方式化初始形状初始形状向量—规定向量中各分量对应一切n个盘子，位置上数字代表3个柱子之一后继函数挪动规那么—根据约束条件给出的各形状的后继形状目的测试新向量能否是目的形状(也是向量方式)途径耗散函数每挪动一个盘子的代价为1第2章搜索技术16河内塔问题求解求最短途径问题：形状图中从三角形1个顶点走到另一个顶点结论：(1)假设初始形状或目的形状在三角形顶点上，那么最短途径独一；(2)对于恣意2个形状，最短求解途径至多为2条。(中国某大学研讨生证明)求解过程—对形状空间的搜索—以2阶河内塔为例第2章搜索技术17河内塔问题的搜索树第2章搜索技术1,12,13,11,12,31,13,23,32,1×2,2××√3,12,2×1,32,13,3××2,33,31,21,1××√2,21,23,13,3××√2,23,21,31,1××√18求解过程—树搜索求解问题的过程运用搜索树方式每个形状对应搜索树中一个节点根节点对应于初始形状每次从搜索树的上层节点出发，根据约束条件进入下一个能够的形状，即展开新的一层树节点—节点扩展节点展开的顺序即代表了不同的搜索战略当展开的节点为目的形状时，就找到了问题的一个解第2章搜索技术192.1.3搜索战略研讨搜索过程思索的假设干问题 (1)有限搜索还是无限搜索 (2)知目的还是未知目的 (3)目的或目的+途径 (4)有约束还是无约束 (5)数据驱动(向前搜索)还是目的驱动 (6)单向搜索还是双向搜索第2章搜索技术20搜索的分类搜索过程的分类：形状空间搜索(图搜索方式)，问题空间搜索(层次方法)，博弈空间搜索无信息搜索与启发式搜索启发式：利用中间信息改良控制战略启发式：(1)任何有助于找到问题的解，但不能保证找到解的方法是启发式方法(2)有助于加速求解过程和找到较优解的方法是启发式方法启发式也叫启发函数第2章搜索技术21搜索算法的性能4种途径来评价搜索算法的性能完备性—当问题有解时，算法能否保证找到一个解最优性—算法能否能找到一个最优解(途径耗散函数值最小的途径)时间复杂性—找到一个解需求破费多少时间空间复杂性—在搜索过程中需求占用多少内存第2章搜索技术22性能量度时空复杂性的量度—由形状空间图的大小来衡量/相关度量如下：分支因子b (每次展开的平均节点个数)目的节点的深度d途径的最大长度m 搜索深度限制l搜索耗散第2章搜索技术232.2无信息搜索战略

2.2.1广度优先搜索

2.2.2深度优先搜索和深度有限搜索

2.2.3叠代深化深度优先搜索

2.2.4无信息搜索战略性能比较

2.2.5图搜索算法第2章搜索技术24盲目搜索战略无信息搜索也称盲目搜索：没有任何附加信息，只需生成后继和区分目的与非目的形状有5种盲目搜索战略广度优先搜索代价一致搜索深度优先搜索深度有限搜索迭代深化深度优先搜索第2章搜索技术252.2.1广度优先搜索广度优先搜索过程：首先扩展根节点接着扩展根节点的一切后继节点然后再扩展后继节点的后继，依此类推在下一层任何节点扩展之前搜索树上的本层深度的一切节点都曾经被扩展广度优先搜索可以调用树搜索算法(Tree-Search)实现其参数fringe(边缘/扩展分支)为先进先出队列FIFO第2章搜索技术26树搜索算法(1)functionTree-Search(problem,fringe)returnsolution/failure (initialfringe=empty,mode=FIFO) fringe←Insert(Make-Node(Initial-State[problem]),fringe) dowhile(1) iffringe=Emptythenreturnfailure node←Remove-First(fringe) ifState[node]=GoalthenreturnSolution(node) fringe←Insert-All(Expend(node,problem), fringe)第2章搜索技术27树搜索算法(2)关键在于如何扩展节点functionExpend(node,problem)returnsetofnodes successors←theemptyset foreach<action,result>inSuccessor-Find[problem](State[node])do s←newNode/State[s]←result Parent-Node[s]=node/Action[s]=action Path-Cost[s]=Path-Cost[node]+Step-Cost[node, action,s] Depth[s]←Depth[node]+1 addstosuccessors returnsuccessors第2章搜索技术28广度优先搜索的性能在上述算法中，广度优先搜索以Tree-Search(problem,FIFO-Queue)调用树搜索算法从4种度量来评价广度优先搜索：完备性—总能找到一个解假设每步扩展的耗散一样时，广度优先搜索能找到最优解内存耗费是比执行时间耗费更大的问题指数级的时间耗费(空间和时间耗费的例子参见p60图3.11)第2章搜索技术292.2.2深度优先搜索和深度有限搜索深度优先搜索过程：总是扩展搜索树的当前扩展分支(边缘)中最深的节点搜索直接伸展到搜索树的最深层，直到那里的节点没有后继节点那些没有后继节点的节点扩展终了就从边缘中去掉然后搜索算法回退下一个还有未扩展后继节点的上层节点继续扩展搜索算法参见深度有限搜索算法(l=∞)第2章搜索技术30深度优先搜索的性能深度优先搜索经过后进先出队列LIFO(栈)调用Tree-Search实现/通常运用递归函数实现，依次对当前节点的子节点调用该函数性能：内存需求少—如分支因子=b/最大深度=m的形状空间深度优先搜索只需求存储bm+1个节点(比较广度优先O(bd+1))不是完备的/不是最优的最坏情况下时间复杂性也很高O(bm)第2章搜索技术31深度有限搜索深度优先搜索的无边境问题可以经过提供一个预先设定的深度限制l来处理深度=l的节点当作无后继节点对待虽然处理了无限途径问题，但假设l<d那么找不到解假设选择d>l那么深度优先搜索也不是最优的时间复杂度O(bl)空间复杂度O(bl)深度优先搜索可看作是一种特例即l=∞第2章搜索技术32非递归的深度有限搜索算法functionDepth-Limited-Search(problem,fringe,limit)returnsolution/failure/cutoff fringe←Insert(Make-Node(Initial-State[problem]),fringe) (mode=LIFO) dowhile(1) iffringe=Emptythenreturnfailure node←Remove-First(fringe) ifState[node]=Goalthenreturn Solution(node) elseifDepth[node]=limitthenreturncutoff elsefringe←Insert-All(Expend (node,problem),fringe)第2章搜索技术33搜索步数的限制上面算法中能够有两类失败cutoff表示到达了有限深度而无解failure表示普通的前往值无解有时深度有限搜索基于问题本身的知识，如形状空间的直径即问题求解的最大步数但对于大多数问题，不到问题处理时是无法知道求解步数的限制第2章搜索技术342.2.3叠代深化深度优先搜索假设每次改动限制深度，多次调用深度有限搜索算法，就得到了叠代深化深度优先搜索算法其深度限制依次为0/1/2…这样，当搜索到达最浅的目的节点深度时就可以发现目的节点这种搜索结合了广度优先和深度优先两种算法的优点(算法见p63)分支因子有限时是完备的/途径耗散是节点深度的非递增函数时是最优的空间需求为O(bd)/时间复杂性为O(bd)第2章搜索技术35形状的生成叠代深化搜索中由于多次反复搜索，因此部分形状被多次生成，看起来很浪费但是由于在分支因子比较平衡的搜索树中，多数节点都在最底层(即叶子节点)，所以上层节点的多次生成影响不是很大/与广度优先搜索相比，效率还是更高普通来讲，当搜索空间很大而解的深度未知时，叠代深化搜索是一个首选的无信息搜索方法第2章搜索技术362.2.4无信息搜索战略比较第2章搜索技术评价标准广度优先代价一致深度优先深度有限叠代深入双向搜索是否完备时间空间是否最优是A是A/B否否是A是A/D

O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)是C是否否是C是C/D关于A/B/C/D的解释：A—假设b有限那么是完备的/B—单步耗散≥e那么是完备的/C—假设单步耗散都是一样的那么是最优的/D—两个方向上都运用广度优先搜索372.2.5图搜索算法曾经看到搜索过程中会出现反复的形状扩展，应该防止/假设算法不检测反复形状的话，有能够使一个本来可解的问题变为不可解检测就是把要扩展的节点与已扩展的节点进展比较，把遇到的一样形状去掉所以要记录曾经扩展的节点—引入两个表—存储已扩展的节点closed表和未扩展的节点open表(即前述fringe)新算法称为图搜索算法第2章搜索技术38图搜索算法第2章搜索技术functionGraph-Search(problem,fringe)returnsolutionorfailure closed←emptyset fringe←Insert(Make-Node(Initial-State[problem]),fringe) dowhile(1) iffringe=Emptythenreturnfailure node←Remove-First(fringe) ifState[node]=GoalthenreturnSolution(node) ifState[node]!CLOSEDthen addState[node]toclosed fringe←Insert-All(Expend(node,problem),fringe)39图搜索算法的性能由树到图：存在不同分支节点的合并图搜索算法与树搜索算法比较：只是添加了对展开节点的判别，因此由不同的待扩展节点陈列方式而构成的搜索战略(如广度优先和深度优先)的性能依然同树搜索算法对于含很多反复形状的问题，其搜索效率比树搜索算法有效很多讨论参见p67第2章搜索技术40例子：“农夫过河〞问题搜索农夫过河问题用向量<人,狼,羊,白菜>表示在河岸两边的情况0表示此岸/1表示此岸过河规那么有8条(隐含了约束条件)1(0,*,*,*)→(1,*,*,*)/2(0,0,*,*)→(1,1,*,*) 3(0,*,0,*)→(1,*,1,*)/4(0,*,*,0)→(1,*,*,1) 5(1,*,*,*)→(0,*,*,*)/6(1,1,*,*)→(0,0,*,*)7(1,*,1,*)→(0,*,0,*)/8(1,*,*,1)→(0,*,*,0) *=0/1表示恣意岸边但必需一样第2章搜索技术41“农夫过河〞—广度优先搜索第2章搜索技术000010101100×00101110010011010101111110110001closed表<0000><1010><0010><1110><1011><0100><0001><1101>所用规那么序列3/5/4/7/2所用规那么序列3/5/2/7/4所用规那么序列3/5/4/7/2/5/3所用规那么序列3/5/2/7/4/5/342“农夫过河〞—深度优先搜索第2章搜索技术000010101100×001011100100110101011111closed表<0000><1010><0010><1110><0100><1101>所用规那么序列3/5/2/7/4所用规那么序列3/5/2/7/4/5/3只运用一个搜索分支/所扩展的第一个节点是最新节点432.3启发式搜索战略

2.3.1贪婪最正确优先搜索

2.3.2A*搜索

2.3.3启发函数

2.3.4联机搜索第2章搜索技术44启发式搜索通用算法启发式搜索也称有信息搜索，其通用算法称为最正确优先搜索(Best-First-Search)最正确优先搜索基于评价函数扩展节点—按照间隔目的最短的评价值来扩展并不是真正的最正确—只是表现得最正确/近似最正确算法的关键要素是启发函数(Heuristicfunction)，记为f(n)/f(n)=从节点n到目的节点的最低耗散途径的耗散估计值启发函数引导搜索两种方式—贪婪最正确优先搜索/A*搜索(A*算法)第2章搜索技术452.3.1贪婪最正确优先搜索贪婪最正确优先搜索的评价函数f(n)=h(n)在贪婪最正确优先搜索中总是选择当前离目的最近(最小代价)的节点进展扩展(搜索)部分最正确未必全局最正确—不是最优的(下例)运用贪婪最正确优先搜索算法搜索从Arad到首都的行车最短道路Arad的下一站有3个城市S(253)/T(329)/Z(374)→扩展Sibiu有3个城市F(176)/O(380)/R(193)→扩展Fagaras直接可到目的地然而实践不是最优的：S→F→B实践全长310/S→RV→P→B实践全长278，多了32km第2章搜索技术46问题实例—Romania公路图第2章搜索技术47问题实例(1)第2章搜索技术寻觅从Arad到首都的行车最短道路评价函数f(n)=h(n)直线间隔启发式hSLD与实践间隔相关但需另外给出，见下表Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Dobreta242Pitesti100Eforie161RimnicuVilcea193Fagaras176Sibiu253Giurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind37448问题实例(2)第2章搜索技术启发函数h(n)最小化会对错误的起点比较敏感例子：地图中Iasi到Fagaras的行车道路(走入死路的能够)需求仔细检查反复形状，否那么能够永远找不到解与深度优先搜索类似，非最优、非完备最坏情况下时空复杂度都是O(bm)/m为最大搜索深度492.3.2A*搜索A*搜索的评价函数为f(n)=g(h)+h(n)g(n)是从初始节点到该节点n的途径耗散h(n)是从节点n到目的节点的最低耗散途径的估计耗散值，称为启发式或启发函数因此，f(n)=经过节点n、具有最低耗散值的解的估计耗散找到g(n)+h(n)值最小的节点当然是合理的(参见书中p79图4.3对于地图的搜索)假设启发函数h(n)满足一定条件，那么A*搜索是完备的和最优的第2章搜索技术50搜索算法的可采用性[定义]搜索算法的可采用性(可采用性)(Hart,Nilsson,Raphel,1968)假设形状空间中的目的形状存在，并且从初始形状到目的形状有一条通路，而搜索算法一定能在有限步内终止并找到一个最优解(代价最低)，那么这个形状空间搜索算法称为可采用的对于A*搜索来说，运用树搜索算法(Tree-Search)，那么它是可采用的假设对启发函数h(n)作一定限制，那么运用图搜索算法(Graph-Search)也是可采用的第2章搜索技术51可采用的启发函数算法的可采用性取决于启发函数的可采用性启发函数h(n)是可采用的—h(n)从来不会过高地估计到达目的的耗散值此即—h(n)满足h(n)≤h*(n)，h*(n)是从当前节点n到达目的的最低耗散值此即—f(n)永远不会高估经过节点n的解的实践耗散—f(n)≤f*(n)，所以是最优解假设h(n)是可采用的，那么运用Tree-Search的A*算法是可采用的(最优的)本人尝试证明，参考附录证明过程第2章搜索技术52A*搜索的Tree-Search算法functionTree-Search(problem,fringe)returnsolutionorfailure Selecth(n) Make-Node(Initial-State[problem]&gettheirf(n) Insert(nodes,fringe) Sort(fringe,f(n)) dowhile(1) iffringe=Emptythenreturnfailure node←Remove-First(fringe) ifState[node]=GoalthenreturnSolution(node) Expend(node,problem)&gettheirf(n) Insert(nodes,fringe) Sort(fringe,f(n))第2章搜索技术53A*搜索的Graph-Search算法假设A*搜索运用图搜索算法，那么A*必然前往最优解的结论就不成立—缘由是假设最优途径不是第一个生成的，能够由于有反复形状而被丢弃处理方案：1)修正Graph-Search算法使得可以进展比较，只丢弃耗散值大的途径2)保证到达任何反复形状的最优途径总是第一条被跟随的途径—要求h(n)坚持一致性(单调性)算法—请自行给出第2章搜索技术54h(n)的一致性(1)[定义]启发函数的一致性—假设对于每个节点n和经过恣意行动a生成n的每个后继节点n’，从节点n到达目的节点的估计耗散值h(n)不大于从n到n’的单步耗散与从n’到目的节点的估计耗散值之和，那么h(n)称为一致的此即h(n)≤c(n,n’,a)+h(n’)/是三角不等式的某种方式每个一致的启发函数都是可采用的证明要点：h(n)≤c(n,n’,a)+h(n’),h(n)≤c*(n,n’,a)+h(n’)可得h(n)–h*(n)≤h(n’)–h*(n’)目的节点h(T)=h*(T)=0回退可得恣意节点h(n)≤h*(n)第2章搜索技术55h(n)的一致性(2)通常我们选择的启发函数h(n)都满足一致性要求(因此必定是可采用的)关于一致性的结论：假设h(n)是一致的，那么运用Graph-Search的A*算法是最优的附录证明似乎没有利用此条件假设h(n)是一致的，那么沿着任何途径的f(n)值是非递减的(由一致性定义可得)f(n)耗散值沿着任何途径都是非递减的结论允许在形状空间中画出等值线(见以下图)第2章搜索技术56道路里程的等值线第2章搜索技术ZTLMDCGUONIVHE420A380BFPRS40057A*搜索节点的扩展A*搜索由初始节点出发开场搜索，以同心带状增长f(n)耗散值的方式扩展节点假设h(n)=0那么为代价一致搜索(只按g(n)值排序)那么同心带为“圆型〞，运用启发函数那么同心带向目的节点方向拉伸假设C*是最优解途径的耗散值，那么有以下结论：A*算法扩展一切f(n)≤C*的节点A*算法在到达目的节点之前能够会扩展一些正益处于“目的等值线〞上的节点A*算法不扩展f(n)>C*的节点(均被剪枝)第2章搜索技术58A*算法的性质(1)A*算法是完备的—假设解存在，就一定能找到/由于找到解只需有限步A*算法是最优的—即可采用的(一个普遍采用的证明见附录)A*算法对于任何给定的启发函数都是效率最优的/没有任何其他算法扩展的节点少于A*算法但是，A*算法对于多数问题来说，搜索空间处于目的等值线内的节点数量是求解途径长度的指数级第2章搜索技术59A*算法的性质(2)假设要求不以指数级增长，那么启发函数需求满足条件对于几乎一切的启发函数来说，偏向至少都是与途径耗散成正比的，而不是途径耗散的对数/所以，在实践运用中，往往不是坚持找到最优解，而是采用以下两种方式：运用A*算法的变种算法快速找到非最优解设计准确而非严厉可采用的启发函数第2章搜索技术60A*算法在空间方面的改良A*算法在内存中保管一切生成的节点，耗费极大—因此对于许多大规模问题时不适用的A*算法要减少对内存的需求—改良递归最正确优先搜索RBFS—模拟规范的最正确优先搜索的递归算法，只是用线性存储空间假设h(n)是可采用的，那么RBFS最优MA*(存储限制A*)和SMA*(简化的MA*)—充分利用可用的内存SMA*的思想—当内存放满时，就丢弃最差的一个子节点而参与新节点假设任何最优解是可到达的，那么SMA*是最优的第2章搜索技术612.3.3启发函数A*搜索的关键就是设计可采用的或者一致的(单调的)启发函数如何评价启发函数/如何设计启发函数例子—八数码问题关于八数码问题的一些数据：随机产生的八数码游戏的平均解的步数=22分支因子约为3穷举搜索(盲目搜索)思索的形状个数322≈3.1*1010实践可到达的不同形状个数9!/2=181440第2章搜索技术62八数码问题的启发函数启发函数的中心—决不高估到达目的的步数/对于八数码问题的常用候选：h1(n)=不在位棋子数—这是一个可采用的启发函数，由于要把“不在位〞的棋子都挪动到正确位置上，每个错位的棋子至少要挪动一次/所以有h1(n)≤h*(n)h2(n)=一切棋子到达其目的位置的间隔和—计算程度间隔(曼哈顿间隔)/该函数也是可采用的，由于到达其目的位置至少要挪动这些间隔长度第2章搜索技术63启发函数准确度对算法性能的影响描写启发函数质量的一个度量是有效分支因子b*b*是深度为d的一致搜索树为了可以包括N(生成的总节点数)+1个节点所必需的分支因子N+1=1+b*+(b*)2+……+(b*)d例如：52个节点在第5层找到解，那么b*=1.92有效分支因子可以根据问题实例发生变化，但是在足够难的问题中是稳定的/因此小规模实验中测得b*值可以为启发函数的总体有效性提供指点第2章搜索技术64八数码问题启发函数的比较良好设计的启发函数使b*值接近1，允许对大规模的问题进展求解启发函数越接近于真实最优解的值，那么相应的搜索算法效率越高/显然此时有—假设h1(n)≤h2(n)，那么h2(n)优于h1(n)(此时h2(n)信息量比h1(n)多)p85页给出了八数码问题的启发函数h1/h2的比较数据“优于〞的含义—运用h2的算法不会比运用h1的算法扩展更多的节点第2章搜索技术65如何设计启发函数A*搜索的关键如何找到是一个适宜的启发函数寻觅战略：从松弛问题中获得—松弛问题的最优解的耗散是原问题的一个可采用的启发函数从给定问题子问题的解耗散中获得—建立方式数据库，存储每个能够子问题实例从阅历中学习—运用归纳学习算法，运用相关形状特征来预测第2章搜索技术66松弛问题最优解作为启发函数松弛问题—降低了行动限制的问题松弛问题的最优解耗散是原问题的一个可采用的启发函数根据定义，原始问题的最优解也是该松弛问题的解，其耗散不低于松弛问题的最优解松弛问题的最优解是确切耗散，一定满足三角不等式，因此是单调的，所以作为启发函数一定是可采用的假设问题定义经过方式化言语描画，那么自动地构造