人工智能原理之搜索技术

人工智能原理

第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)关键在于如何扩展节点function

Expend(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松弛问题最优解作为启发函数松弛问题—降低了行动限制的问题松弛问题的最优解耗散是原问题的一个可采纳的启发函数根据定义，原始问题的最优解也是该松弛问题的解，其耗散不低于松弛问题的最优解松弛问题的最优解是确切耗散，一定满足三角不等式，因而是单调的，所以作为启发函数一定是可采纳的如果问题定义通过形式化语言描述，则自动地构造其松弛问题是可能的/例子—八数码问题第2章搜索技术67子问题的解耗散作为启发函数子问题的最优解耗散是完整问题的耗散下界建立模式数据库—存储每个可能子问题实例的精确解耗散从目标状态向后搜索并记录下每个子问题模式的耗散，存储于数据库搜索中遇到的每个完整状态通过在数据库中查找出相应子问题布局而设计出一个可采纳的启发函数对于八数码问题，这样的启发函数要比曼哈顿距离精确得多(具体数值见p87)第2章搜索技术68从经验中学习启发函数从实例中学习—每个实例包含了解路径上的各状态及其到达解的耗散每个最优解实例提供了可学习h(n)的实例收集实际解消耗的统计数据，以此产生可预测其他状态解消耗的启发函数h(n)使用归纳学习方法八数码问题的讨论(p87)第2章搜索技术69A*搜索的例子(1)积木块移动游戏初始状态：目标状态：移动规则：

(1)积木移到空格/代价=1 (2)积木跨越1个积木移到空格/代价=1 (3)积木跨越2个积木移到空格/代价=2第2章搜索技术70A*搜索的例子(2)A*搜索：至少代价=每个W左边B的个数(B到W右边的必须跨越W的代价)令h(n)=至少代价，则h(n)≤h*(n)且满足单调性

h(ni)≤h(ni+1)+g(ni+1)-g(ni)(实际是=)g(n)=到达当前状态实际付出的代价搜索过程中括号里的数字分别为h/g值第2章搜索技术71A*搜索的例子(3)第2章搜索技术722.3.4

联机搜索脱机搜索—不需感知，只要计算例子：简单游戏，通过有限的规则作用即可推算出目标所在联机搜索—必须通过行动/观察与计算交叉进行才能决定下一步搜索两种情况：环境未知—只有行动才能得知如何正确走向目标/环境空间过大—虽然理论上已知，但是实际不可计算(如棋类比赛)第2章搜索技术73例子：迷宫问题第2章搜索技术GS321123

如左图所示，联机搜索问题只能通过行动来解决，因为障碍是不能事先预知的智能体初始位置在S，其已知信息为：ACTION(s)—状态S下的行动列表c(s,a,s’)—通过行动a从s状态到达s’状态

Goal-Test(s)/G目标位置智能体可使用曼哈顿距离启发式74竞争率(1)代价—智能体实际走过的路经总耗散理想耗散—没有无用搜索步骤的走过路径耗散/也就是应该走过路径的耗散竞争率—代价÷理想耗散该值要尽可能地小第2章搜索技术75竞争率(2)影响竞争率的因素，使其无穷大行动不可逆—进入一个不可到达目标的状态又不可回溯没有算法能够在所有的状态空间中避免死路(p98图4.19a)因此，通常需要假设状态空间是可安全探索的—具有可逆的状态空间/从每个可达状态出发都有可达的目标状态不过，在可逆状态空间中，因为对手的存在，也会出现无界竞争率的情况(p98图4.19b)第2章搜索技术76联机搜索智能体联机搜索智能体需要行动和感知，然后扩展当前状态的环境地图区别：联机—规划与行动交叉/脱机—只要规划例子：A*搜索在不同子空间节点的跳跃式扩展，模拟而非实际行动/联机算法只扩展目前实际占据的节点—采用深度优先搜索联机搜索必须维护一个回溯表第2章搜索技术77演讲完毕，谢谢观看！附录资料：人工智能简介​AboutTeachingPlan基本要求：人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支，是目前迅速发展的一门新兴学科，新思想新方法层出不穷。其基本思想是利用机器来模仿和执行人脑的功能，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。对于培养学生计算机技术的应用能力，开阔思路和视野，有重要意义。

​AboutTeachingPlan因此，要求学生掌握知识表示和问题求解的几种常用方法，尤其是不确定性推理；掌握机器学习基本概念，了解几种机器学习方法尤其是神经网络学习方法；掌握专家系统的概念，了解专家系统设计方法，掌握一些智能控制方法，了解国内外人工智能研究尤其是机器人的最新进展；具有一定的人工智能编程设计能力（利用Lisp或Prolog语言）。​AboutTeachingPlan课程内容以及学时分配人工智能引论(1) 人工智能概念及与计算机的关系，研究途径、内容和应用领域概况介绍，其他最新材料。符号主义、连接主义、行为主义三大流派人工智能数学基础(1)知识表示方法（2） 状态空间法、问题归约法，谓词逻辑法、产生式表示法（动物识别系统）；CLIPS语言；语义网络法、框架法（这是结构化表示）；剧本、过程、Petri网、面向对象的表示。​AboutTeachingPlan 搜索技术和策略（3-4）状态空间法，盲目搜索和启发式搜索，A*算法；海伯伦理论、消解原理和策略；与\或形推理和搜索策略；其他求解技术。 不确定推理技术（3-4）主观Bayes理论；可信度方法和证据理论；系统组织技术；非单调推理；Rete快速算法；模糊推理技术；基于语义网络和框架不确定推理； 专家系统（2）专家系统概念、结构和知识获取；黑板模型、知识组织、管理及系统建造和开发工具；专家系统举例及编程。

人工智能程序设计（1）人工智能语言基本机制：LISP和PROLOG。​AboutTeachingPlan 模式识别导论（3）模式识别专题：概率模式识别。模式识别专题：结构模式识别 机器学习（1）：机械,解释经验,事例,归纳,概念,类比学习等；统计,结构,模糊模式识别。 专题讲座（3次） 1)神经网络基本理论和应用 (史奎凡课程：安排于人工智能理论与应用课程内)； 2)智能体（Agent）； 3)自然语言处理； 4)智能控制和机器人科学 智能控制的结构理论和研究领域，智能控制系统及应用示例；机器人规划、机器视觉和自然语言理解等。​AboutTeachingPlan 实践：1) 搜索技术和策略2) 不确定推理技术3) 专家系统：动物识别系统4) 模式识别技术5) 调研： 搜索技术和策略、不确定推理技术、统计模式识别、机器学习等四个领域进展报告。​ChapterOne:BriefIntroductiontoArtificialIntelligence1.WhatisAI?人工智能（ArtificialIntelligence,AI）是当前科学技发展的一门前沿学科，同时也是一门新思想，新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。它是在计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基础发展起来的，因此又可把它看作是一门综合性的边缘学科。它的出现及所取得的成就引起了人们的高度重视,并取得了很高的评价。有的人把它与空间技术，原子能技术一起并誉为20世纪的三大科学技术成就。​Intelligence智能是知识与智力的总合。 知识——智能行为的基础； 智力——获取知识并运用知识求解问题的能力。智能具有以下特征：(1)具有感知能力——指人们通过视觉、听觉、触觉、味觉、嗅觉等感觉器官感知外部世界的能力；(2)具有记忆与思维的能力——这是人脑最重要的功能，亦是人之所以有智能的根本原因；(3)具有学习能力及自适应能力；(4)具有行为能力。ArtificialIntelligence人工智能——计算机科学的一个分支，是智能计算机系统，即人类智慧在机器上的模拟，或者说是人们使机器具有类似于人的智慧（对语言能理解、能学习、能推理）。​2.BriefHistoryofAI (1) 孕育（1956年前）古希腊的Aristotle（亚里士多德）（前384-322），给出了形式逻辑的基本规律。英国的哲学家、自然科学家Bacon（培根）（1561-1626），系统地给出了归纳法。“知识就是力量”德国数学家、哲学家Leibnitz（布莱尼茨）（1646-1716）。提出了关于数理逻辑的思想，把形式逻辑符号化，从而能对人的思维进行运算和推理。做出了能做四则运算的手摇计算机英国数学家、逻辑学家Boole（布尔）（1815-1864）实现了布莱尼茨的思维符号化和数学化的思想，提出了一种崭新的代数系统——布尔代数。​美籍奥地利数理逻辑学家Godel（哥德尔）（1906-1978），证明了一阶谓词的完备性定；任何包含初等数论的形式系统，如果它是无矛盾的，那么一定是不完备的。意义在于，人的思维形式化和机械化的某种极限，在理论上证明了有些事是做不到的。英国数学家Turing(图灵)（1912-1954）,1936年提出了一种理想计算机的数学模型（图灵机），1950年提出了图灵试验，发表了“计算机与智能”的论文。图灵奖。美国数学家Mauchly，1946发明了电子数字计算机ENIAC美国神经生理学家McCulloch，建立了第一个神经网络数学模型。美国数学家Shannon（香农）,1948年发表了《通讯的数学理论》，代表了“信息论”的诞生。​ (2) 形成（1956-1969）1956年提出了“ArtificialIntelligence（人工智能）”1956年夏由麻省理工学院的J.McCarthy、M.L.Minsky,IBM公司信息研究中心的N.Rochester,贝尔实验室的C.E.Shannon共同发起，邀请了Moore,Samuel,Selfridge,Solomonff,Simon,Newell等人，10位数学家、信息学家、心理学家、神经生理学家、计算机科学家，在Dartmouth大学召开了一次关于机器智能的研讨会，会上McCarthy提议正式采用了ArtificialIntelligence（人工智能）这一术语。这次会议，标志着人工智能作为一门新兴学科正式诞生了。 McCarthy（麦卡锡）——人工智能之父。这次会议之后的10年间，人工智能的研究取得了许多引人瞩目的成就.机器学习方面：塞缪尔于1956年研制出了跳棋程序，该程序能从棋谱中学习，也能从下棋实践中提高棋艺；​在定理证明方面：王浩于1958年在IBM机上证明了《数学原理》中有关命题演算的全部定理（220条），还证明了谓词演算中150条定理85%；1965年，鲁宾逊（Robinson）提出了消解原理；在模式识别方面：1959年塞尔夫里奇推出了一个模式识别程序；1965年罗伯特（Robert）编制出可辨别积木构造的程序；在问题求解方面：1960年纽厄尔等人通过心理学试验总结出了人们求解问题的思维规律，编制了通用问题求解程序GPS,可以用来求解11种不同类型的问题；在专家系统方面：斯坦福大学的费根鲍姆（E.A.Feigenbaum）自1965年开始进行专家系统DENDRAL（化学分析专家系统），1968年完成并投入使用；在人工智能语言方面：1960年McCarthy等人建立了人工智能程序设计语言Lisp，该语言至今仍是建造智能系统的重要工具；1969年成立了国际人工智能联合会议（InternationalJointConferencesOnArtificialIntelligence）​ (3) 发展（1970年以后）70年代，开始从理论走向实践，解决一些实际问题。同时很快就发现问题：归结法费时、下棋赢不了全国冠军、机器翻译一团糟。以Feigenbaum为首的一批年轻科学家改变了战略思想，1977年提出知识工程的概念，以知识为基础的专家咨询系统开始广泛的应用。著名专家系统的有：DENDRAL化学分析专家系统（斯坦福大学1968）MACSYMA符号数学专家系统（麻省理工1971）MYCIN诊断和治疗细菌感染性血液病的专家咨询系统（斯坦福大学1973）CASNET(CausalASsciationalNetwork)诊断和治疗青光眼的专家咨询系统（拉特格尔斯（Rutgers）大学70年代中）CADUCEUS(原名INTERNIST)医疗咨询系统（匹兹堡大学）；HEARSAYI和II语音理解系统（卡内基-梅隆大学）PROSPECTOR地质勘探专家系统（斯坦福大学1976）XCON计算机配置专家系统（卡内基-梅隆大学1978）​•80年代，人工智能发展达到阶段性的顶峰。•87,89年世界大会有６－７千人参加。硬件公司有上千个。并进行Lisp硬件、Lisp机的研究。•在专家系统及其工具越来越商品化的过程中,国际软件市场上形成了一门旨在生产和加工知识的新产业——知识产业。应该说，知识工程和专家系统是近十余年来人工智能研究中最有成就的分支之一。•同年代，1986年Rumlhart领导的并行分布处理研究小组提出了神经元网络的反向传播学习算法，解决了神经网络的根本问题之一。从此，神经网络的研究进入新的高潮。•90年代，计算机发展趋势为小型化、并行化、网络化、智能化。•人工智能技术逐渐与数据库、多媒体等主流技术相结合，并融合在主流技术之中，旨在使计算机更聪明、更有效、与人更接近。•日本政府于1992年结束了为期十年的称为“知识信息处理体统”的第五代计算机系统研究开发计划。并开始了为期十年的实况计算（RealWordComputing）计划。​3.ResearchObjectsandMainContents

(1)人工智能的研究目标

人工智能的长期研究目标：构造智能计算机。

人工智能的近期研究目标：使现有的电子计算机更聪明，更有用，使它不仅能做一般的数值计算及非数值信息的数据处理，而且能运用知识处理问题，能模拟人类的部分智能行为。​(2)人工智能研究的基本内容

1.机器感知以机器视觉与机器听觉为主。机器感知是机器获取外部信息的基本途径，是使机器具有智能不可或缺的组成部分，对此人工智能中已形成两个专门的研究领域——

模式识别和自然语言理解。2.机器思维指通过感知的外部信息及机器内部的各种工作信息进行有目的的处理。主要开展以下几方面的研究：(1)知识表示(2)知识的组织，累计，管理技术(3)知识的推理(4)各种启发式搜索及控制策略(5)神经网络，人脑的结构及其工作原理​3.机器学习

使计算能自动获取知识，能直接向书本学习，能通过与人谈话学习，能通过对环境的观察学习，并能在实践中自我完善。4.机器行为机器行为主要指计算机的表达能力，即“说”、“写”、“画”等，对智能机器人，还应该有人的四肢功能，即能走路，能取物，能操作等。5.智能系统及智能计算机的构造技术​4.ResearchObjectsandMainContents人工智能面世以来，其研究途径存在两种不同的观点：以符号处理为核心的方法——主张通过运用计算机科学的方法进行研究，实现人工智能在计算机的模拟。以网络连接为主的连接机制方法——主张用生物学的方法进行研究，搞清楚人类智能的本质。(1)以符号处理为核心的方法该方法起源于纽厄尔等人的通用问题求解系统（GPS），用于模拟人类求解问题的心理过程，逐渐形成为物理符号系统，这种方法认为： 人类研究的目标是实现机器智能，而计算机自身具有符号处理能力，这种能力本身就蕴含着演绎推理的内涵，因而可通过运行相