《人工智能原理77精编版》由会员分享，可在线阅读，更多相关《人工智能原理77精编版（78页珍藏版）》请在金锄头文库上搜索。
1、人工智能原理第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、行动序列，然后选择最佳序列这个过程就是搜索,第2章 搜索技术,4,2.1.1 问题与问题的解,问题可以形式化地定义为4个组成部分 智能体的初始状态(即搜索的开始) 后继函数智能体采取的可能行动的描述，通常为 / 初始状态和后继函数隐含地定义了问题的状态空间 / 状态空间中的一条路径是通过行动序列连接起来的一个状态序列 目标测试检查给定的状态是不是目标 路径耗散函数每条路径都有一个数值化的耗散值，反映了性能度量 / 求解问题的代价,第2章 搜索技术,5,问题的解,问题的解就是初始状态到目标状态的路径 解的优劣由路径耗散函数量度(代价) 最优解就是路径耗散函数值最小的路径 上述解题过程把解决一个问
3、题的过程描述出来，称之为解题知识的过程性表示 过程性知识与陈述性知识相对 搜索过程解题的特点没有直接的方法(公式)可以求解，而是一步一步的探索,第2章 搜索技术,6,状态空间,数据基：代表了所要解决的问题，有初始状态，可能有目标状态也可能没有 状态空间：在解题过程中的每一时刻，数据基都处于一定的状态，数据基所有可能状态的集合称为状态空间 有向图：若把每个状态看成一个节点，则整个状态空间是一个有向图 / 该图不一定全连通，即从某些状态不一定能到达另外一些状态,第2章 搜索技术,7,问题的可解性,可解的：在每个连通部分，每个弧代表一个运算符，将状态改变 / 如果从代表初始状态的节点出发，有一条路径
4、通向目标状态，则称此目标状态所代表的问题在当前初始状态下是可解的 搜索空间：在解题过程中达到过的所有状态的集合，称为搜索空间 不同于状态空间，搜索空间只是其中一部分 状态空间和搜索空间都属于过程性知识表示,第2章 搜索技术,8,2.1.2 问题实例,玩具问题 八数码游戏(九宫图) 河内塔 八皇后问题 真空吸尘器世界 现实问题 旅行商问题 超大规模集成电路的布局 自动装配排序 / 蛋白质设计 互联网搜索,第2章 搜索技术,9,八数码游戏,八数码游戏：1-8数字(棋子)/9个方格(棋盘格)/1个空格 可用如下形式的规则来表示数字通过空格进行移动： 共24条规则=4角*2+4边*3+1中间*4 搜索
5、顺序举例： (1)优先移动行数小的棋子(数字) (2)同一行中优先移动列数大的棋子 约束规则：不使离开既定位置的数字数增加,第2章 搜索技术,10,八数码游戏的搜索树,第2章 搜索技术,既定位置=终态,11,八数码问题形式化,初始状态 初始状态向量规定向量中各分量对应的位置，各位置上的初始数字 后继函数 移动规则按照某条规则移动数字，将得到的新向量 目标测试 新向量是否是目标状态(也是向量形式) 路径耗散函数 每次移动代价为1,第2章 搜索技术,12,河内塔(1),河内塔问题：n个大小不等的圆盘从一个柱子移到另一个柱子，共有3个柱子(n阶河内塔问题) 约束：从第1根柱子移动到第3根柱子上去，利
6、用第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章
7、搜索技术,15,河内塔问题形式化,初始状态 初始状态向量规定向量中各分量对应所有n个盘子，位置上数字代表3个柱子之一 后继函数 移动规则依据约束条件给出的各状态的后继状态 目标测试 新向量是否是目标状态(也是向量形式) 路径耗散函数 每移动一个盘子的代价为1,第2章 搜索技术,16,河内塔问题求解,求最短路径问题：状态图中从三角形1个顶点走到另一个顶点 结论： (1)如果初始状态或目标状态在三角形顶点上，则最短路径唯一； (2)对于任意2个状态，最短求解路径至多为2条。(中国某大学研究生证明) 求解过程对状态空间的搜索以2阶河内塔为例,第2章 搜索技术,17,河内塔问题的搜索树,第2章 搜索技
8、术,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)有限搜索还是无限搜
9、索 (2)已知目标还是未知目标 (3)目标或目标+路径 (4)有约束还是无约束 (5)数据驱动(向前搜索)还是目标驱动 (6)单向搜索还是双向搜索,第2章 搜索技术,20,搜索的分类,搜索过程的分类：状态空间搜索(图搜索方式)，问题空间搜索(层次方法)，博弈空间搜索 无信息搜索与启发式搜索 启发式：利用中间信息改进控制策略 启发式：(1)任何有助于找到问题的解，但不能保证找到解的方法是启发式方法 (2)有助于加速求解过程和找到较优解的方法是启发式方法 启发式也叫启发函数,第2章 搜索技术,21,搜索算法的性能,4种途径来评价搜索算法的性能 完备性当问题有解时，算法是否保证找到一个解 最优性算法
10、是否能找到一个最优解(路径耗散函数值最小的路径) 时间复杂性找到一个解需要花费多少时间 空间复杂性在搜索过程中需要占用多少内存,第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,盲目搜索策略,无信息搜索也称盲目搜索：没有任何
11、附加信息，只有生成后继和区分目标与非目标状态 有5种盲目搜索策略 广度优先搜索 代价一致搜索 深度优先搜索 深度有限搜索 迭代深入深度优先搜索,第2章 搜索技术,25,2.2.1 广度优先搜索,广度优先搜索过程： 首先扩展根节点 接着扩展根节点的所有后继节点 然后再扩展后继节点的后继，依此类推 在下一层任何节点扩展之前搜索树上的本层深度的所有节点都已经被扩展 广度优先搜索可以调用树搜索算法(Tree-Search)实现 其参数fringe(边缘/扩展分支)为先进先出队列FIFO,第2章 搜索技术,26,树搜索算法(1),function Tree-Search(problem,fringe)
12、return solution /failure(initial fringe=empty, mode=FIFO) fringeInsert(Make-Node(Initial-Stateproblem),fringe) do while(1) if fringe=Empty then return failure nodeRemove-First(fringe) if Statenode=Goal then return Solution(node) fringeInsert-All(Expend(node,problem), fringe),第2章 搜索技术,27,树搜索算法(2),关键在
13、于如何扩展节点 function Expend(node,problem) return set of nodes successorsthe empty set for each in Successor-Findproblem (Statenode) do snew Node / Statesresult Parent-Nodes=node / Actions=action Path-Costs=Path-Costnode+Step-Costnode, action,s DepthsDepthnode+1 add s to successors return successors,第2章
14、搜索技术,28,广度优先搜索的性能,在上述算法中，广度优先搜索以Tree-Search(problem,FIFO-Queue)调用树搜索算法 从4种度量来评价广度优先搜索： 完备性总能找到一个解 如果每步扩展的耗散相同时，广度优先搜索能找到最优解 内存消耗是比执行时间消耗更大的问题 指数级的时间消耗(空间和时间消耗的例子参见p60图3.11),第2章 搜索技术,29,2.2.2 深度优先搜索和深度有限搜索,深度优先搜索过程： 总是扩展搜索树的当前扩展分支(边缘)中最深的节点 搜索直接伸展到搜索树的最深层，直到那里的节点没有后继节点 那些没有后继节点的节点扩展完毕就从边缘中去掉 然后搜索算法回退
15、下一个还有未扩展后继节点的上层节点继续扩展 搜索算法参见深度有限搜索算法(l=),第2章 搜索技术,30,深度优先搜索的性能,深度优先搜索通过后进先出队列LIFO(栈)调用Tree-Search实现 / 通常使用递归函数实现，依次对当前节点的子节点调用该函数 性能： 内存需求少如分支因子=b/最大深度=m的状态空间深度优先搜索只需要存储bm+1个节点(比较广度优先O(bd+1) 不是完备的 / 不是最优的 最坏情况下时间复杂性也很高O(bm),第2章 搜索技术,31,深度有限搜索,深度优先搜索的无边界问题可以通过提供一个预先设定的深度限制l来解决 深度=l的节点当作无后继节点看待 虽然解决了无
16、限路径问题，但如果ll则深度优先搜索也不是最优的 时间复杂度O(bl) 空间复杂度O(bl) 深度优先搜索可看作是一种特例即l=,第2章 搜索技术,32,非递归的深度有限搜索算法,function Depth-Limited-Search(problem,fringe,limit) return solution/failure/cutoff fringeInsert(Make-Node(Initial-Stateproblem),fringe)(mode=LIFO) do while(1) if fringe=Empty then return failure nodeRemove-First(fringe) if Statenode=Goal then return Solution(node) else if Depthnode=limit then return cutoff else fringeInsert-All(Expend(node, problem), fringe),第2章 搜索技术,33,搜索步数的限制,上面算法中可能有两类失败
