人工智能原理77

人工智能原理第2章搜索技术（上）本章内容2.1搜索与问题求解2.2无信息搜索策略2.3启发式搜索策略2.4局部搜索算法2.5约束满足问题2.6博弈搜索参考书目附录A*算法可采纳性的证明第2章搜索技术2.1搜索与问题求解2.1.1问题与问题的解2.1.2问题实例2.1.3搜索策略第2章搜索技术4搜索与问题求解•问题求解过程是搜索答案(目标)的过程/所以问题求解技术也叫搜索技术—通过对状态空间的搜索而求解问题的技术•问题求解智能体是一种基于目标的智能体•在寻找到达目标的过程中，当智能体面对多个未知的选项时，首先检验各个不同的导致已知评价的状态的可能行动序列，然后选择最佳序列—这个过程就是搜索第2章搜索技术52.1.1问题与问题的解•问题可以形式化地定义为4个组成部分•智能体的初始状态(即搜索的开始)•后继函数—智能体采取的可能行动的描述，通常为行动，后继状态/初始状态和后继函数隐含地定义了问题的状态空间/状态空间中的一条路径是通过行动序列连接起来的一个状态序列•目标测试—检查给定的状态是不是目标•路径耗散函数—每条路径都有一个数值化的耗散值，反映了性能度量/求解问题的代价第2章搜索技术6问题的解•问题的解就是初始状态到目标状态的路径•解的优劣由路径耗散函数量度(代价)•最优解就是路径耗散函数值最小的路径•上述解题过程把解决一个问题的过程描述出来，称之为解题知识的过程性表示•过程性知识与陈述性知识相对•搜索过程解题的特点—没有直接的方法(公式)可以求解，而是一步一步的探索第2章搜索技术7状态空间•数据基：代表了所要解决的问题，有初始状态，可能有目标状态也可能没有•状态空间：在解题过程中的每一时刻，数据基都处于一定的状态，数据基所有可能状态的集合称为状态空间•有向图：若把每个状态看成一个节点，则整个状态空间是一个有向图/该图不一定全连通，即从某些状态不一定能到达另外一些状态第2章搜索技术8问题的可解性•可解的：在每个连通部分，每个弧代表一个运算符，将状态改变/如果从代表初始状态的节点出发，有一条路径通向目标状态，则称此目标状态所代表的问题在当前初始状态下是可解的•搜索空间：在解题过程中达到过的所有状态的集合，称为搜索空间•不同于状态空间，搜索空间只是其中一部分•状态空间和搜索空间都属于过程性知识表示第2章搜索技术92.1.2问题实例•玩具问题•八数码游戏(九宫图)•河内塔•八皇后问题•真空吸尘器世界•现实问题•旅行商问题•超大规模集成电路的布局•自动装配排序/蛋白质设计•互联网搜索第2章搜索技术10八数码游戏•八数码游戏：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章搜索技术11八数码游戏的搜索树第2章搜索技术Begin******End*1524367812453678152436781524736815243678124536781245367815432678152438671234567841253678154326781524386712345678412536784126537813542678既定位置=终态12八数码问题形式化•初始状态•初始状态向量—规定向量中各分量对应的位置，各位置上的初始数字•后继函数•移动规则—按照某条规则移动数字，将得到的新向量•目标测试•新向量是否是目标状态(也是向量形式)•路径耗散函数•每次移动代价为1第2章搜索技术13河内塔(1)•河内塔问题：n个大小不等的圆盘从一个柱子移到另一个柱子，共有3个柱子(n阶河内塔问题)•约束：从第1根柱子移动到第3根柱子上去，利用第2根柱子/每次移动1个盘子，且移动过程必须是小盘落大盘•描述：设每个状态为(a1,a2,a3,…,an),ai=1,2,3—表示第i个盘子在第1/2/3根柱子上第2章搜索技术14河内塔(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章搜索技术15河内塔问题图解第2章搜索技术(3,3,2)(2,3,2)(1,3,2)(2,1,2)(2,3,2)(1,1,2)(3,1,2)(3,2,2)(2,2,2)(1,1,1)(3,1,1)(3,2,1)(2,2,1)(1,2,1)(2,2,3)(1,2,3)(1,3,3)(3,3,3)(2,3,3)(2,1,3)(1,1,3)(3,3,1)(1,3,1)(2,1,1)(2,3,1)(3,1)(2,1)(3,2)(2,3)(2,2)(1,2)(1,3)(3,3)(1)(1,1)(2)(3)16河内塔问题形式化•初始状态•初始状态向量—规定向量中各分量对应所有n个盘子，位置上数字代表3个柱子之一•后继函数•移动规则—依据约束条件给出的各状态的后继状态•目标测试•新向量是否是目标状态(也是向量形式)•路径耗散函数•每移动一个盘子的代价为1第2章搜索技术17河内塔问题求解•求最短路径问题：状态图中从三角形1个顶点走到另一个顶点•结论：(1)如果初始状态或目标状态在三角形顶点上，则最短路径唯一；(2)对于任意2个状态，最短求解路径至多为2条。(中国某大学研究生证明)•求解过程—对状态空间的搜索—以2阶河内塔为例第2章搜索技术18河内塔问题的搜索树第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××√19求解过程—树搜索•求解问题的过程使用搜索树形式•每个状态对应搜索树中一个节点•根节点对应于初始状态•每次从搜索树的上层节点出发，根据约束条件进入下一个可能的状态，即展开新的一层树节点—节点扩展•节点展开的顺序即代表了不同的搜索策略•当展开的节点为目标状态时，就找到了问题的一个解第2章搜索技术202.1.3搜索策略•研究搜索过程考虑的若干问题(1)有限搜索还是无限搜索(2)已知目标还是未知目标(3)目标或目标+路径(4)有约束还是无约束(5)数据驱动(向前搜索)还是目标驱动(6)单向搜索还是双向搜索第2章搜索技术21搜索的分类•搜索过程的分类：状态空间搜索(图搜索方式)，问题空间搜索(层次方法)，博弈空间搜索•无信息搜索与启发式搜索•启发式：利用中间信息改进控制策略•启发式：(1)任何有助于找到问题的解，但不能保证找到解的方法是启发式方法•(2)有助于加速求解过程和找到较优解的方法是启发式方法•启发式也叫启发函数第2章搜索技术22搜索算法的性能•4种途径来评价搜索算法的性能•完备性—当问题有解时，算法是否保证找到一个解•最优性—算法是否能找到一个最优解(路径耗散函数值最小的路径)•时间复杂性—找到一个解需要花费多少时间•空间复杂性—在搜索过程中需要占用多少内存第2章搜索技术23性能量度•时空复杂性的量度—由状态空间图的大小来衡量/相关度量如下：•分支因子b(每次展开的平均节点个数)•目标节点的深度d•路径的最大长度m•搜索深度限制l•搜索耗散第2章搜索技术2.2无信息搜索策略2.2.1广度优先搜索2.2.2深度优先搜索和深度有限搜索2.2.3叠代深入深度优先搜索2.2.4无信息搜索策略性能比较2.2.5图搜索算法第2章搜索技术25盲目搜索策略•无信息搜索也称盲目搜索：没有任何附加信息，只有生成后继和区分目标与非目标状态•有5种盲目搜索策略•广度优先搜索•代价一致搜索•深度优先搜索•深度有限搜索•迭代深入深度优先搜索第2章搜索技术262.2.1广度优先搜索•广度优先搜索过程：•首先扩展根节点•接着扩展根节点的所有后继节点•然后再扩展后继节点的后继，依此类推•在下一层任何节点扩展之前搜索树上的本层深度的所有节点都已经被扩展•广度优先搜索可以调用树搜索算法(Tree-Search)实现•其参数fringe(边缘/扩展分支)为先进先出队列FIFO第2章搜索技术27树搜索算法(1)functionTree-Search(problem,fringe)returnsolution/failure(initialfringe=empty,mode=FIFO)fringe←Insert(Make-Node(Initial-State[problem]),fringe)dowhile(1)iffringe=Emptythenreturnfailurenode←Remove-First(fringe)ifState[node]=GoalthenreturnSolution(node)fringe←Insert-All(Expend(node,problem),fringe)第2章搜索技术28树搜索算法(2)•关键在于如何扩展节点functionExpend(node,problem)returnsetofnodessuccessors←theemptysetforeachaction,resultinSuccessor-Find[problem](State[node])dos←newNode/State[s]←resultParent-Node[s]=node/Action[s]=actionPath-Cost[s]=Path-Cost[node]+Step-Cost[node,action,s]Depth[s]←Depth[node]+1addstosuccessorsreturnsuccessors第2章搜索技术29广度优先搜索的性能•在上述算法中，广度优先搜索以Tree-Search(problem,FIFO-Queue)调用树搜索算法•从4种度量来评价广度优先搜索：•完备性—总能找到一个解•如果每步扩展的耗散相同时，广度优先搜索能找到最优解•内存消耗是比执行时间消耗更大的问题•指数级的时间消耗(空间和时间消耗的例子参见p60图3.11)第2章搜索技术302.2.2深度优先搜索和深度有限搜索•深度优先搜索过程：•总是扩展搜索树的当前扩展分支(边缘)中最深的节点•搜索直接伸展到搜索树的最深层，直到那里的节点没有后继节点•那些没有后继节点的节点扩展完毕就从边缘中去掉•然后搜索算法回退下一个还有未扩展后继节点的上层节点继续扩展•搜索算法参见深度有限搜索算法(l=∞)第2章搜索技术31深度优先搜索的性能•深度优先搜索通过后进先出队列LIFO(栈)调用Tree-Search实现/通常使用递归函数实现，依次对当前节点的子节点调用该函数•性能：•内存需求少—如分支因子=b/最大深度=m的状态空间深度优先搜索只需要存储bm+1个节点(比较广度优先O(bd+1))•不是完备的/不是最优的•最坏情况下时间复杂性也很高O(bm)第2章搜索技术32深度有限搜索•深度优先搜索的无边界问题可以通过提供一个预先设定的深度限制l来解决•深度=l的节点当作无后继节点看待•虽然解决了无限路径问题，但如果ld则找不到解•如果选择dl则深度优先搜索也不是最优的•时间复杂度O(bl)•空间复杂度O(bl)•深度优先搜索可看作是一种特例即l=∞第2章搜索技术33非递归的深度有限搜索算法functionDepth-Limited-Search(problem,fringe,limit)returnsolution/failure/cutofffringe←Insert(Make-Node(Initial-State[problem]),fringe)(mode=LIFO)dowhile(