人工智能原理-搜索技术

《人工智能原理-搜索技术》由会员分享，可在线阅读，更多相关《人工智能原理-搜索技术（77页珍藏版）》请在金锄头文库上搜索。

1、人工智能原理人工智能原理第第2 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、程中，当智能体面对多 个未知的选项时，首先检验各个不同的导致 已知评价的状态的可能行动序列，然后选择 最佳序列这个过程就是搜索第2章 搜索技术42.1.1 2.1.1 问题问题问题问题 与与问题问题问题问题 的解的解 问题可以形式化地定义为4个组成部分 智能体的初始状态(即搜索的开始) 后继函数智能体采取的可能行动的描述， 通常为 / 初始状态和后 继函数隐含地定义了问题的状态空间 / 状 态空间中的一条路径是通过行动序列连接起 来的一个状态序列 目标测试检查给定的状态是不是目标 路径耗散函数每条路径都有一个数值化的 耗散值，反映了性能度量 / 求解问题的代 价第2章 搜索技术5问题问题问题问

3、题 的解的解 问题的解就是初始状态到目标状态的路 径 解的优劣由路径耗散函数量度(代价) 最优解就是路径耗散函数值最小的路径 上述解题过程把解决一个问题的过程描 述出来，称之为解题知识的过程性表示 过程性知识与陈述性知识相对 搜索过程解题的特点没有直接的方法( 公式)可以求解，而是一步一步的探索第2章 搜索技术6状状态态态态空空间间间间 数据基：代表了所要解决的问题，有初 始状态，可能有目标状态也可能没有 状态空间：在解题过程中的每一时刻， 数据基都处于一定的状态，数据基所有 可能状态的集合称为状态空间 有向图：若把每个状态看成一个节点， 则整个状态空间是一个有向图 / 该图不 一定全连通，即

4、从某些状态不一定能到 达另外一些状态第2章 搜索技术7问题问题问题问题 的可解性的可解性 可解的：在每个连通部分，每个弧代表 一个运算符，将状态改变 / 如果从代表 初始状态的节点出发，有一条路径通向 目标状态，则称此目标状态所代表的问 题在当前初始状态下是可解的 搜索空间：在解题过程中达到过的所有 状态的集合，称为搜索空间 不同于状态空间，搜索空间只是其中一部分 状态空间和搜索空间都属于过程性知识表示第2章 搜索技术82.1.2 2.1.2 问题实问题实问题实问题实 例例 玩具问题 八数码游戏(九宫图) 河内塔 八皇后问题 真空吸尘器世界 现实问题 旅行商问题 超大规模集成电路的布局 自动装

5、配排序 / 蛋白质设计 互联网搜索第2章 搜索技术9八数八数码码码码游游戏戏戏戏 八数码游戏：1-8数字(棋子)/9个方格(棋盘格 )/1个空格 可用如下形式的规则来表示数字通过空格进行 移动： 共24条规则=4角*2+4边*3+1中间*4 搜索顺序举例：(1)优先移动行数小的棋子(数字)(2)同一行中优先移动列数大的棋子 约束规则：不使离开既定位置的数字数增加第2章 搜索技术10八数八数码码码码游游戏戏戏戏的搜索的搜索树树树树第2章 搜索技术既定位置=终态11八数八数码码码码问题问题问题问题 形式化形式化 初始状态 初始状态向量规定向量中各分量对应的位 置，各位置上的初始数字 后继函数 移动

6、规则按照某条规则移动数字，将得到 的新向量 目标测试 新向量是否是目标状态(也是向量形式) 路径耗散函数 每次移动代价为1第2章 搜索技术12河内塔河内塔(1)(1) 河内塔问题：n个大小不等的圆盘从一个 柱子移到另一个柱子，共有3个柱子(n阶 河内塔问题) 约束：从第1根柱子移动到第3根柱子上 去，利用第2根柱子 / 每次移动1个盘子 ，且移动过程必须是小盘落大盘 描述：设每个状态为(a1, a2, a3, , an), ai=1, 2, 3表示第i个盘子在第1/2/3根柱 子上第2章 搜索技术13河内塔河内塔(2)(2) 递归定义：(a1, a2, a3, , an)为n阶河 内塔的状态集

7、合，则(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个柱子之一 后继函数 移动规则依据约束条件给出的各状态的后 继状态 目标测试 新向量是否是目标状态(也是向量形式) 路径耗散函数

8、每移动一个盘子的代价为1第2章 搜索技术16河内塔河内塔问题问题问题问题 求解求解 求最短路径问题：状态图中从三角形1个 顶点走到另一个顶点 结论： (1)如果初始状态或目标状态在三角形顶点上 ，则最短路径唯一； (2)对于任意2个状态，最短求解路径至多为2 条。(中国某大学研究生证明) 求解过程对状态空间的搜索以2阶河 内塔为例第2章 搜索技术17河内塔河内塔问题问题问题问题 的搜索的搜索树树树树第2章 搜索技术1,12,13,11,12,31,13,23,32,12,2 3,12,21,32,13,32,33,31,21,1 2,21,23,13,3 2,23,21,31,1 18求解求解

9、过过过过程程树树树树搜索搜索 求解问题的过程使用搜索树形式 每个状态对应搜索树中一个节点搜索树中一个节点 根节点对应于初始状态 每次从搜索树的上层节点出发，根据约束条 件进入下一个可能的状态，即展开新的一层 树节点节点扩展 节点展开的顺序即代表了不同的搜索策略 当展开的节点为目标状态时，就找到了问题 的一个解第2章 搜索技术192.1.3 2.1.3 搜索策略搜索策略 研究搜索过程考虑的若干问题 (1)有限搜索还是无限搜索 (2)已知目标还是未知目标 (3)目标或目标+路径 (4)有约束还是无约束 (5)数据驱动(向前搜索)还是目标驱动 (6)单向搜索还是双向搜索第2章 搜索技术20搜索的分搜

10、索的分类类类类 搜索过程的分类：状态空间搜索(图搜索 方式)，问题空间搜索(层次方法)，博弈 空间搜索 无信息搜索与启发式搜索 启发式：利用中间信息改进控制策略 启发式：(1)任何有助于找到问题的解，但 不能保证找到解的方法是启发式方法 (2)有助于加速求解过程和找到较优解的方 法是启发式方法 启发式也叫启发函数第2章 搜索技术21搜索算法的性能搜索算法的性能 4种途径来评价搜索算法的性能 完备性当问题有解时，算法是否保证找到 一个解 最优性算法是否能找到一个最优解(路径 耗散函数值最小的路径) 时间复杂性找到一个解需要花费多少时间 空间复杂性在搜索过程中需要占用多少内 存第2章 搜索技术22

11、性能量度性能量度 时空复杂性的量度由状态空间图的大 小来衡量 / 相关度量如下： 分支因子 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种盲目搜索策略 广度优先搜索 代价一致搜索 深度优先搜索 深度有限搜索 迭代深

12、入深度优先搜索第2章 搜索技术252.2.1 2.2.1 广度广度优优优优先搜索先搜索 广度优先搜索过程： 首先扩展根节点 接着扩展根节点的所有后继节点 然后再扩展后继节点的后继，依此类推 在下一层任何节点扩展之前搜索树上的本层 深度的所有节点都已经被扩展 广度优先搜索可以调用树搜索算法(Tree- Search)实现 其参数fringe(边缘/扩展分支)为先进先出队 列FIFO第2章 搜索技术26树树树树搜索算法搜索算法(1)(1)function Tree-Search(problem,fringe) return solution /failure(initial fringe=empt

13、y, 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)(2) 关键在于如何扩展节点 function Expend(node,problem

14、) 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章 搜索技术28广度广度优优优优先搜索的性能先搜索的性能 在上述算法中，广

15、度优先搜索以Tree- Search(problem,FIFO-Queue)调用树搜 索算法 从4种度量来评价广度优先搜索： 完备性总能找到一个解 如果每步扩展的耗散相同时，广度优先搜索 能找到最优解 内存消耗是比执行时间消耗更大的问题 指数级的时间消耗(空间和时间消耗的例子 参见p60图3.11)第2章 搜索技术292.2.2 2.2.2 深度深度优优优优先搜索和深度有限搜索先搜索和深度有限搜索 深度优先搜索过程： 总是扩展搜索树的当前扩展分支(边缘)中最 深的节点 搜索直接伸展到搜索树的最深层，直到那里 的节点没有后继节点 那些没有后继节点的节点扩展完毕就从边缘 中去掉 然后搜索算法回退下一个还有未扩展后继节 点的上层节点继续扩展 搜索算法参见深度有限搜索算法(l=)第2章 搜索技术30深度深度优优优优先搜索的性能先搜索的性能 深度优先搜索通过后进先出队列LIFO(栈 )调用Tree-Search实现 / 通常使用递归函 数实现，依次对当前节点的子节点调用 该函数 性能： 内存需求少如分支因子=b/最大深度=m的 状态空间深度优先搜索只需要存储bm+1个 节点(比较广度优先O(bd+1)