人工智能第3章通过搜索进行问题的求解.ppt

PPT模板下载 第三章通过搜索进行问题的求解 3 1问题求解Agent3 2问题实例3 3通过搜索求解3 4无信息搜索策略3 5有信息 启发式 的搜索策略3 6本章小结 目录 要进行问题求解 首先要讨论的是对问题以及其解的精确定义 我们将通过一些实例来说明如何去描述一个问题及其解 搜索 是指从问题出发寻找解的过程 问题求解 PPT模板下载 3 1问题求解Agent 例子 罗马尼亚Agent在罗马尼亚城市Arad度假 假设她有张第二天飞往Bucharest的机票 而且是不能退票 目标 前往Bucharest任务 找到能够使它到达目标的动作序列Q 决策所要考虑的行动和状态的种类 a 在开车从一个主要城镇到另一个城镇的层次上考虑行动 Agent设计三个步骤 形式化 搜索 执行 形式化 执行 搜索 行动序列 问题的解 PPT模板下载 3 1问题求解Agent 问题的形式化定义可以用五部分形式化描述初始状态 智能体的起始状态对Agent可能行动的描述 给定一个特殊状态s ACTION s 返回状态s下可以执行的动作集合 如 In Arad 可应用行动为 Go S Go T Go Z 对每个动作的描述 转移模型 RESULT s a 表示 状态s下执行行动a后达到状态 目标测试 确定给定的状态是不是目标状态路径耗散 为每条路径分配一个数值化的耗散值问题的解 从初始状态到目标状态的路径最优解 路径耗散最小的解 PPT模板下载 3 1问题求解Agent 环境特性静态的 完成问题形式化和求解的时候不在考虑环境可能的变化确定性的 问题的解是行动的单一序列 在问题求解的过程中感知信息不起作用可观察的 PPT模板下载 3 1问题求解Agent 罗马尼亚城镇地图 PPT模板下载 3 1问题求解Agent 问题的解解释从初始值到目标状态的路径解的质量由路径耗散函数值最小的解 PPT模板下载 3 2问题实例 玩具问题状态 8个可能的状态 PPT模板下载 3 2问题实例 玩具问题状态 由Agent位置和灰尘位置确定初始状态 任何形态都可能被设计为初始 后续函数 用来产生通过左移 右移 吸尘能够到达的合法状态目标测试 用来检测是否所有的方格都干净路径耗散 假设每一步的耗散值为1 PPT模板下载 3 2问题实例 玩具问题 PPT模板下载 3 2问题实例 八角数码的游戏状态 8个棋子以及空格在9格棋盘初始 任意状态都可以作为初始 但要达到一特定的目标态 只有一半的状态可以作为起点 后继函数 产生4个行动 上 下 左 右 可以到达合法状态目标测试 用来检测是否匹配右图 路径耗散 每一步耗散值1 PPT模板下载 3 2问题实例 八皇后问题皇后可以攻击和她在同一行 同一列 同一斜对角线的任何棋子 有专用的算法 这里是搜索的测试用例分为两类 增量形式化 每次行动添加一个皇后到状态中去 完整状态形式化 8个皇后都在棋盘上并且不断移动 状态 0 8个皇后任意摆放都是一个状态初始状态 空棋盘后续函数 将增加皇后的棋盘返回目标测试 8个皇后都在棋盘上 并且无法相互攻击 PPT模板下载 3 2问题实例 现实世界寻径问题旅游时面临飞机航行问题状态 位置和当前时间初始状态 用户在咨询时确定后续函数 乘坐的航班 飞行时间 候机时间 状态目标测试 是否在预定时间到达目的地路径耗散 等待时间 飞行时间 座位的质量 费用 旅行商问题等等 PPT模板下载 3 3通过搜索求解 搜索树在对问题进行格式化之后 我们现在需要对问题求解 第一步 检测该节点是不是否为目标状态 如In Arad 选择各种行动 生成一个状态集 In Sibiu In T In Z 接着从其中选择一个考虑 等发现不能求解在选择其他的 PPT模板下载 3 3通过搜索求解 搜索树 PPT模板下载 3 3通过搜索求解 搜索树你会发现有回路产生 回路是冗余的特殊情况 有些问题的冗余是无法避免 所以要避免探索的冗余就是记住曾经走过的路 探索集 记录每一个以探索的节点 PPT模板下载 3 3通过搜索求解 搜索算法基础一个状态空间可以有无数条路径 即搜索树可有无数个节点 例如 从Arad到Sibiu的路径可包括重复出现的节点 节点的数据结构 State 状态空间 Parent Node 搜索树中产生节点的节点 父节点 Action 父节点生成节点是所采取的行动 Path Cost 从初始状态到达该节点消耗 PPT模板下载 3 3通过搜索求解 搜索算法基础 PPT模板下载 3 3通过搜索求解 问题求解算法性能完备性 有解时能否保证找到解最优性 是否有找到最优解时间复杂度 根据搜索过程中产生的节点数目来度量空间复杂度 在执行搜索的过程中需要的内存 取决于储存的最大节点数 时间与空间的复杂度往往要与问题难度的某种度量一起考虑 PPT模板下载 3 4无信息搜索策略 广度优先搜索当b有限时 搜索是完备的如果路径耗散是节点深度的非递减函数 则解是最优的 假设每个状态都有b个后继 解的深度是d 则找到解时 所访问过的节点数为O bd 1 PPT模板下载 3 4无信息搜索策略 代价一致搜索 bfs算法的引伸 扩展路径消耗最低的节点 有可能陷入无限循环 如果规定每一步的耗散都大等于某个小的正值常数 那么就能保证完备性和最优性 复杂度与b和最优解的耗散值有关 PPT模板下载 3 4无信息搜索策略 代价一致搜索 PPT模板下载 3 4无信息搜索策略 深度优先搜索 对内存的需求很少 有可能错误地选择一条分支而且沿着一条很长的路径 甚至是无限 走下去 非最优 非完备 在最坏情况下 dfs所生成的节点数是O bm PPT模板下载 3 4无信息搜索策略 深度优先搜索 PPT模板下载 3 4无信息搜索策略 深度受限搜索 当b有限时 搜索是完备的 如果路径耗散是节点深度的非递减函数 则解是最优的 空间需求是O bd PPT模板下载 3 4无信息搜索策略 迭代加深的深度优先搜索 不断增大深度限制 直到找到目标节点 PPT模板下载 3 4无信息搜索策略 迭代加深的深度优先搜索 不断增大深度限制 直到找到目标节点 PPT模板下载 3 4无信息搜索策略 迭代加深的深度优先搜索结合了深度优先和广度有限的优点 空间需求和深度优先一样小完备的当路径耗散是节点深度的非递减函数时是最优的当搜索空间很大且解的深度未知 迭代深入搜索是首先 PPT模板下载 3 4无信息搜索策略 代价一致搜索的迭代搜索 不断增加的路径耗散限双向搜索 运行两个同时的搜索 向前搜索 从初始状态向前搜索 向后搜索 从目标状态向后搜索 扩展节点前检查该节点是否在另一棵树的边缘空间需求大当两个搜索都是广度优先搜索时是完备的和最优的 PPT模板下载 3 5有信息 启发式 搜索策略 前面讨论的方法都是无信息的搜索方法 即都没有利用问题本身的特性信息 在决定要被扩展的节点时 都没有考虑该节点在解的路径上的可能性有多大 它是否有利于问题求解以及求出的解是否为最优 启发式搜索要用到问题自身的某些特性信息 以指导搜索朝着最有希望的方向前进 启发信息的强度强 降低搜索工作量 但可能导致找不到最优解弱 一般导致工作量加大 极限情况下变为无信息搜索 但可能可以找到最优解 PPT模板下载 3 5有信息 启发式 搜索策略 状态空间状态空间 在求解一个问题时 从初始状态到目标状态寻找一条解的过程 这个过程会可能产生很多的解 进而构成了一个图 启发式搜索就是在状态空间对每一个位置行进评估进而找到一个最优解 PPT模板下载 3 5有信息 启发式 搜索策略 启发性信息和估价函数用于指导搜索过程 且与具体问题有关的控制性信息称为为启发性信息用于评价节点重要性的函数称为估价函数 记为f x g x h x g x 为从初始节点S0到节点x已经实际付出的代价h x 是从节点x到目标节点Sg的最优路径的估价代价 体现了问题的启发性信息 称为启发函数f x 表示从初始节点经过节点x到达目标节点的最优路径的代价估价值 PPT模板下载 3 5有信息 启发式 搜索策略 最佳优先搜索思想 对每个节点使用估价函数 估计希望 扩展最有希望未扩展的节点主要包括 贪婪最佳优先搜索 A 算法 PPT模板下载 3 5有信息 启发式 搜索策略 最佳优先搜索思想 对每个节点使用估价函数 估计希望 扩展最有希望未扩展的节点主要包括 贪婪最佳优先搜索 A 算法 PPT模板下载 3 5有信息 启发式 搜索策略 贪婪最佳优先搜索启发失函数f n h n 从n到最近的目标节点代价的估计这里采用hSLD n 从n到Bucharest的直线距离贪婪算法扩展看来与目标最近的节点 PPT模板下载 3 5有信息 启发式 搜索策略 A 算法思想 避免对已经扩展的路径进行再扩展评价函数为 f x g x h x g x 到达节点以花费的代价h x 该节点到目标节点的花费代价因此 f n 经过n节点的最小代价解的估计代价 PPT模板下载 3 5有信息 启发式 搜索策略 A 算法 PPT模板下载 3 5有信息 启发式 搜索策略 A 算法 PPT模板下载 3 5有信息 启发式 搜索策略 A 算法 PPT模板下载 3 5有信息 启发式 搜索策略 A 算法 PPT模板下载 3 5有信息 启发式 搜索策略 A 算法 PPT模板下载 3 5有信息 启发式 搜索策略 A 算法完备性 Yes 除非有无限多的节点具有f f G 时间 指数空间 保存所有的节