人工智能原理之搜索技术.pptx
- 文档编号:15120943
- 上传时间:2023-07-01
- 格式:PPTX
- 页数:77
- 大小:574.07KB
人工智能原理之搜索技术.pptx
《人工智能原理之搜索技术.pptx》由会员分享,可在线阅读,更多相关《人工智能原理之搜索技术.pptx(77页珍藏版)》请在冰点文库上搜索。
人工智能原理第2章搜索技术(上),1,本章内容2.1搜索与问题求解2.2无信息搜索策略2.3启发式搜索策略2.4局部搜索算法2.5约束满足问题2.6博弈搜索参考书目附录A*算法可采纳性的证明,第2章搜索技术,2,2.1搜索与问题求解2.1.1问题与问题的解2.1.2问题实例2.1.3搜索策略,第2章搜索技术,3,搜索与问题求解,问题求解过程是搜索答案(目标)的过程/所以问题求解技术也叫搜索技术通过对状态空间的搜索而求解问题的技术问题求解智能体是一种基于目标的智能体在寻找到达目标的过程中,当智能体面对多个未知的选项时,首先检验各个不同的导致已知评价的状态的可能行动序列,然后选择最佳序列这个过程就是搜索,第2章搜索技术,4,2.1.1问题与问题的解,问题可以形式化地定义为4个组成部分智能体的初始状态(即搜索的开始)后继函数智能体采取的可能行动的描述,通常为/初始状态和后继函数隐含地定义了问题的状态空间/状态空间中的一条路径是通过行动序列连接起来的一个状态序列目标测试检查给定的状态是不是目标路径耗散函数每条路径都有一个数值化的耗散值,反映了性能度量/求解问题的代价,第2章搜索技术,5,问题的解,问题的解就是初始状态到目标状态的路径解的优劣由路径耗散函数量度(代价)最优解就是路径耗散函数值最小的路径上述解题过程把解决一个问题的过程描述出来,称之为解题知识的过程性表示过程性知识与陈述性知识相对搜索过程解题的特点没有直接的方法(公式)可以求解,而是一步一步的探索,第2章搜索技术,6,状态空间,数据基:
代表了所要解决的问题,有初始状态,可能有目标状态也可能没有状态空间:
在解题过程中的每一时刻,数据基都处于一定的状态,数据基所有可能状态的集合称为状态空间有向图:
若把每个状态看成一个节点,则整个状态空间是一个有向图/该图不一定全连通,即从某些状态不一定能到达另外一些状态,第2章搜索技术,7,问题的可解性,可解的:
在每个连通部分,每个弧代表一个运算符,将状态改变/如果从代表初始状态的节点出发,有一条路径通向目标状态,则称此目标状态所代表的问题在当前初始状态下是可解的搜索空间:
在解题过程中达到过的所有状态的集合,称为搜索空间不同于状态空间,搜索空间只是其中一部分状态空间和搜索空间都属于过程性知识表示,第2章搜索技术,8,2.1.2问题实例,玩具问题八数码游戏(九宫图)河内塔八皇后问题真空吸尘器世界现实问题旅行商问题超大规模集成电路的布局自动装配排序/蛋白质设计互联网搜索,第2章搜索技术,9,八数码游戏,八数码游戏:
1-8数字(棋子)/9个方格(棋盘格)/1个空格可用如下形式的规则来表示数字通过空格进行移动:
共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,1,2,1,3,1,1,1,2,3,1,1,3,2,3,3,2,1,2,2,3,1,2,2,1,3,2,1,3,3,2,3,3,3,1,2,1,1,2,2,1,2,3,1,3,3,2,2,3,2,1,3,1,1,18,求解过程树搜索,求解问题的过程使用搜索树形式每个状态对应搜索树中一个节点根节点对应于初始状态每次从搜索树的上层节点出发,根据约束条件进入下一个可能的状态,即展开新的一层树节点节点扩展节点展开的顺序即代表了不同的搜索策略当展开的节点为目标状态时,就找到了问题的一个解,第2章搜索技术,19,2.1.3搜索策略,研究搜索过程考虑的若干问题
(1)有限搜索还是无限搜索
(2)已知目标还是未知目标(3)目标或目标+路径(4)有约束还是无约束(5)数据驱动(向前搜索)还是目标驱动(6)单向搜索还是双向搜索,第2章搜索技术,20,搜索的分类,搜索过程的分类:
状态空间搜索(图搜索方式),问题空间搜索(层次方法),博弈空间搜索无信息搜索与启发式搜索启发式:
利用中间信息改进控制策略启发式:
(1)任何有助于找到问题的解,但不能保证找到解的方法是启发式方法
(2)有助于加速求解过程和找到较优解的方法是启发式方法启发式也叫启发函数,第2章搜索技术,21,搜索算法的性能,4种途径来评价搜索算法的性能完备性当问题有解时,算法是否保证找到一个解最优性算法是否能找到一个最优解(路径耗散函数值最小的路径)时间复杂性找到一个解需要花费多少时间空间复杂性在搜索过程中需要占用多少内存,第2章搜索技术,22,性能量度,时空复杂性的量度由状态空间图的大小来衡量/相关度量如下:
分支因子b(每次展开的平均节点个数)目标节点的深度d路径的最大长度m搜索深度限制l搜索耗散,第2章搜索技术,23,2.2无信息搜索策略2.2.1广度优先搜索2.2.2深度优先搜索和深度有限搜索2.2.3叠代深入深度优先搜索2.2.4无信息搜索策略性能比较2.2.5图搜索算法,第2章搜索技术,24,盲目搜索策略,无信息搜索也称盲目搜索:
没有任何附加信息,只有生成后继和区分目标与非目标状态有5种盲目搜索策略广度优先搜索代价一致搜索深度优先搜索深度有限搜索迭代深入深度优先搜索,第2章搜索技术,25,2.2.1广度优先搜索,广度优先搜索过程:
首先扩展根节点接着扩展根节点的所有后继节点然后再扩展后继节点的后继,依此类推在下一层任何节点扩展之前搜索树上的本层深度的所有节点都已经被扩展广度优先搜索可以调用树搜索算法(Tree-Search)实现其参数fringe(边缘/扩展分支)为先进先出队列FIFO,第2章搜索技术,26,树搜索算法
(1),functionTree-Search(problem,fringe)returnsolution/failure(initialfringe=empty,mode=FIFO)fringeInsert(Make-Node(Initial-Stateproblem),fringe)dowhile
(1)iffringe=EmptythenreturnfailurenodeRemove-First(fringe)ifStatenode=GoalthenreturnSolution(node)fringeInsert-All(Expend(node,problem),fringe),第2章搜索技术,27,树搜索算法
(2),关键在于如何扩展节点functionExpend(node,problem)returnsetofnodessuccessorstheemptysetforeachinSuccessor-Findproblem(Statenode)dosnewNode/StatesresultParent-Nodes=node/Actions=actionPath-Costs=Path-Costnode+Step-Costnode,action,sDepthsDepthnode+1addstosuccessorsreturnsuccessors,第2章搜索技术,28,广度优先搜索的性能,在上述算法中,广度优先搜索以Tree-Search(problem,FIFO-Queue)调用树搜索算法从4种度量来评价广度优先搜索:
完备性总能找到一个解如果每步扩展的耗散相同时,广度优先搜索能找到最优解内存消耗是比执行时间消耗更大的问题指数级的时间消耗(空间和时间消耗的例子参见p60图3.11),第2章搜索技术,29,2.2.2深度优先搜索和深度有限搜索,深度优先搜索过程:
总是扩展搜索树的当前扩展分支(边缘)中最深的节点搜索直接伸展到搜索树的最深层,直到那里的节点没有后继节点那些没有后继节点的节点扩展完毕就从边缘中去掉然后搜索算法回退下一个还有未扩展后继节点的上层节点继续扩展搜索算法参见深度有限搜索算法(l=),第2章搜索技术,30,深度优先搜索的性能,深度优先搜索通过后进先出队列LIFO(栈)调用Tree-Search实现/通常使用递归函数实现,依次对当前节点的子节点调用该函数性能:
内存需求少如分支因子=b/最大深度=m的状态空间深度优先搜索只需要存储bm+1个节点(比较广度优先O(bd+1)不是完备的/不是最优的最坏情况下时间复杂性也很高O(bm),第2章搜索技术,31,深度有限搜索,深度优先搜索的无边界问题可以通过提供一个预先设定的深度限制l来解决深度=l的节点当作无后继节点看待虽然解决了无限路径问题,但如果ll则深度优先搜索也不是最优的时间复杂度O(bl)空间复杂度O(bl)深度优先搜索可看作是一种特例即l=,第2章搜索技术,32,非递归的深度有限搜索算法,functionDepth-Limited-Search(problem,fringe,limit)returnsolution/failure/cutofffringeInsert(Make-Node(Initial-Stateproblem),fringe)(mode=LIFO)dowhile
(1)iffringe=EmptythenreturnfailurenodeRemove-First(fringe)ifStatenode=GoalthenreturnSolution(node)elseifDepthnode=limitthenreturncutoffelsefringeInsert-All(Expend(node,problem),fringe),第2章搜索技术,33,搜索步数的限制,上面算法中可能有两类失败cutoff表示到达了有限深度而无解failure表示一般的返回值无解有时深度有限搜索基于问题本身的知识,如状态空间的直径即问题求解的最大步数但对于大多数问题,不到问题解决时是无法知道求解步数的限制,第2章搜索技术,34,2.2.3叠代深入深度优先搜索,如果每次改变限制深度,多次调用深度有限搜索算法,就得到了叠代深入深度优先搜索算法其深度限制依次为0/1/2这样,当搜索到达最浅的目标节点深度时就可以发现目标节点这种搜索结合了广度优先和深度优先两种算法的优点(算法见p63)分支因子有限时是完备的/路径耗散是节点深度的非递增函数时是最优的空间需求为O(bd)/时间复杂性为O(bd),第2章搜索技术,35,状态的生成,叠代深入搜索中因为多次重复搜索,因此部分状态被多次生成,看起来很浪费但是因为在分支因子比较平衡的搜索树中,多数节点都在最底层(即叶子节点),所以上层节点的多次生成影响不是很大/与广度优先搜索相比,效率还是更高一般来讲,当搜索空间很大而解的深度未知时,叠代深入搜索是一个首选的无信息搜索方法,第2章搜索技术,36,2.2.4无信息搜索策略比较,第2章搜索技术,关于A/B/C/D的解释:
A如果b有限则是完备的/B单步耗散e则是完备的/C如果单步耗散都是相同的则是最优的/D两个方向上都使用广度优先搜索,37,2.2.5图搜索算法,已经看到搜索过程中会出现重复的状态扩展,应该避免/如果算法不检测重复状态的话,有可能使一个本来可解的问题变为不可解检测就是把要扩展的节点与已扩展的节点进行比较,把遇到的相同状态去掉所以要记录已经扩展的节点引入两个表存储已扩展的节点closed表和未扩展的节点open表(即前述fringe)新算法称为图搜索算法,第2章搜索技术,38,图搜索算法,第2章搜索技术,functionGraph-Search(problem,fringe)returnsolutionorfailureclosedemptysetfringeInsert(Make-Node(Initial-Stateproblem),fringe)dowhile
(1)iffringe=EmptythenreturnfailurenodeRemove-First(fringe)ifStatenode=GoalthenreturnSolution(node)ifStatenode!
CLOSEDthenaddStatenodetoclosedfringeInsert-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章搜索技术,0000,1010,1100,0010,1110,0100,1101,0101,1111,1011,0001,closed表,所用规则序列3/5/4/7/2,所用规则序列3/5/2/7/4,所用规则序列3/5/4/7/2/5/3,所用规则序列3/5/2/7/4/5/3,42,“农夫过河”深度优先搜索,第2章搜索技术,0000,1010,1100,0010,1110,0100,1101,0101,1111,closed表,所用规则序列3/5/2/7/4,所用规则序列3/5/2/7/4/5/3,只使用一个搜索分支/所扩展的第一个节点是最新节点,43,2.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章搜索技术,45,2.3.1贪婪最佳优先搜索,贪婪最佳优先搜索的评价函数f(n)=h(n)在贪婪最佳优先搜索中总是选择当前离目标最近(最小代价)的节点进行扩展(搜索)局部最佳未必全局最佳不是最优的(下例)使用贪婪最佳优先搜索算法搜索从Arad到首都的行车最短路线Arad的下一站有3个城市S(253)/T(329)/Z(374)扩展Sibiu有3个城市F(176)/O(380)/R(193)扩展Fagaras直接可到目的地然而实际不是最优的:
SFB实际全长310/SRVPB实际全长278,多了32km,第2章搜索技术,46,问题实例Romania公路图,第2章搜索技术,47,问题实例
(1),第2章搜索技术,寻找从Arad到首都的行车最短路线评价函数f(n)=h(n)直线距离启发式hSLD与实际距离相关但需另外给出,见下表,48,问题实例
(2),第2章搜索技术,启发函数h(n)最小化会对错误的起点比较敏感例子:
地图中Iasi到Fagaras的行车路线(走入死路的可能)需要仔细检查重复状态,否则可能永远找不到解与深度优先搜索类似,非最优、非完备最坏情况下时空复杂度都是O(bm)/m为最大搜索深度,49,2.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章搜索技术,52,A*搜索的Tree-Search算法,functionTree-Search(problem,fringe)returnsolutionorfailureSelecth(n)Make-Node(Initial-Stateproblem&gettheirf(n)Insert(nodes,fringe)Sort(fringe,f(n)dowhile
(1)iffringe=EmptythenreturnfailurenodeRemove-First(fringe)ifStatenode=GoalthenreturnSolution(node)Expend(node,problem)&gettheirf(n)Insert(nodes,fringe)Sort(fringe,f(n),第2章搜索技术,53,A*搜索的Graph-Search算法,如果A*搜索使用图搜索算法,则A*必然返回最优解的结论就不成立原因是如果最优路径不是第一个生成的,可能因为有重复状态而被丢弃解决方案:
1)修改Graph-Search算法使得能够进行比较,只丢弃耗散值大的路径2)保证到达任何重复状态的最优路径总是第一条被追随的路径要求h(n)保持一致性(单调性)算法请自行给出,第2章搜索技术,54,h(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章搜索技术,55,h(n)的一致性
(2),通常我们选择的启发函数h(n)都满足一致性要求(因而必定是可采纳的)关于一致性的结论:
如果h(n)是一致的,那么使用Graph-Search的A*算法是最优的附录证明似乎没有利用此条件如果h(n)是一致的,那么沿着任何路径的f(n)值是非递减的(由一致性定义可得)f(n)耗散值沿着任何路径都是非递减的结论允许在状态空间中画出等值线(见下图),第2章搜索技术,56,道路里程的等值线,第2章搜索技术,57,A*搜索节点的扩展,A*搜索由初始节点出发开始搜索,以同心带状增长f(n)耗散值的方式扩展节点如果h(n)=0则为代价一致搜索(只按g(n)值排序)则同心带为“圆型”,使用启发函数则同心带向目标节点方向拉伸如果C*是最优解路径的耗散值,则有以下结论:
A*算法扩展所有f(n)C*的节点A*算法在到达目标节点之前可能会扩展一些正好处于“目标等值线”上的节点A*算法不扩展f(n)C*的节点(均被剪枝),第2章搜索技术,58,A*算法的性质
(1),A*算法是完备的如果解存在,就一定能找到/因为找到解只要有限步A*算法是最优的即可采纳的(一个普遍采用的证明见附录)A*算法对于任何给定的启发函数都是效率最优的/没有任何其他算法扩展的节点少于A*算法但是,A*算法对于多数问题来说,搜索空间处于目标等值线内的节点数量是求解路径长度的指数级,第2章搜索技术,59,A*算法的性质
(2),如果要求不以指数级增长,则启发函数需要满足条件对于几乎所有的启发函数来说,偏差至少都是与路径耗散成正比的,而不是路径耗散的对数/所以,在实际应用中,往往不是坚持找到最优解,而是采用以下两种方式:
使用A*算法的变种算法快速找到非最优解设计准确而非严格可采纳的启发函数,第2章搜索技术,60,A*算法在空间方面的改进,A*算法在内存中保留所有生成的节点,消耗极大因而对于许多大规模问题时不实用的A*算法要减少对内存的需求改进递归最佳优先搜索RBFS模仿标准的最佳优先搜索的递归算法,只是用线性存储空间如果h(n)是可采纳的,则RBFS最优MA*(存储限制A*)和SMA*(简化的MA*)充分利用可用的内存SMA*的思想当内存放满时,就丢弃最差的一个子节点而加入新节点如果任何最优解是可到达的,则SMA*是最优的,第2章搜索技术,61,2.3.3启发函数,A*搜索的关键就是设计可采纳的或者一致的(单调的)启发函数如何评价启发函数/如何设计启发函数例子八数码问题关于八数码问题的一些数据:
随机产生的八数码游戏的平均解的步数=22分支因子约为3穷举搜索(盲目搜索)考虑的状态个数32
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 原理 搜索 技术