问题求解及搜索技术要点-copy.ppt

人工智能 问题求解基本原理及搜索技术 问题求解基本原理 问题求解 在给定条件下 寻求一个能解决某类问题且能在有限步骤内完成的算法 问题求解特征 传统软件 求解的问题是能够用数学精确描述的良结构的问题 如 解方程 计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动 AI软件 求解的是不可直接用数学模型描述的所谓不良结构问题 如 几何证明 求不定积分 逻辑演算等 通常需要采用弱方法进行搜索求解 AI程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息 应表现人类进行推理所需要的各种知识 问题求解基本原理 一 问题求解的基本方法二 搜索技术 问题求解基本原理 问题求解方法 基于状态空间的问题求解方法基于问题空间的问题求解方法基于博弈搜索的问题求解方法 问题实例 桌上固定了3根柱子 按1 2 3次序排例 有n个大小全不一样大的盘子d1 dn 按从小到大 小的在上的次序依次插在第一根柱子上 要把这n个盘子全部搬到第三根柱子上 每次只许搬一个 任何时候都不允许把大盘子放在小盘子上面 问该如何搬法 设n 3 该如何搬法 123123 梵塔问题 基于状态空间的问题求解方法 1 1 1 1 1 2 1 1 1 1 1 3 1 1 2 1 3 2 状态合法变换规则 满足约束条件 状态定义 i大C j中B k小A 设向量下标分别表示小盘A 中盘B 大盘C 向量值分别表示盘子所在柱子的编号 状态描述 大盘C在第i根柱子上 中号盘B在第j根柱子上 小号盘A在第k根柱子上 基于问题空间的问题求解方法 问题 如何将i柱子上的m个盘子搬到k柱子上 将i柱子上的m 1个盘子搬到j柱子上 将i柱子上的第m个盘子搬到k柱子上 将j柱子上的m 1个盘子搬到k柱子上 问题描述 问题 a b c 将b柱子上的a个盘子搬到c柱子上 问题分解合法规则 3 1 3 2 1 2 1 1 3 2 2 3 基于问题空间的问题求解方法 状态空间法有关概念 状态空间法 从问题的初始状态出发 通过一系列的状态变换找到目标状态的问题求解方法 状态 描述问题中事物形状或状况的符号或数据结构 状态空间 所有状态的全体构成的集合 用四元组 S S0 O G 表示 S 非空状态子集 S0 初始状态 非空 G 非空目标状态子集 O 操作算子集合 一个状态合法转换为另一个状态的描述规则 问题求解过程 隐含求一个普通有向图 节点 状态 边 算子 搜索空间 问题求解过程中到达过的所有状态 节点 的集合 状态空间法有关概念 状态空间 搜索空间及解径的关系 问题有解 从代表初始状态s节点出发 存在一条通向目标节点的路径 问题空间法有关概念 问题空间法 首先产生待证问题的所有子问题 而后通过解决所有子问题达到问题求解目的的方法 问题 描述问题及其子问题的符号或数据结构 问题空间 初始问题以及其所有子问题的全体构成的集合 用四元组 S S0 F G 表示 S 问题和子问题 S0 初始问题 G 具有平凡解的本原问题集合 F 操作算子集合 用于将问题分解成其若干个子问题的描述规则 问题空间法的有关概念 2 问题空间分解过程 隐含求一个与或图节点 问题 边 分解问题的算子 与 节点 如果节点A有边通向一组节点 B1 B2 Bn 问题A的解决有待于A的子问题组 B1 B2 Bn 的全部解决 则称A为 与 节点 如图a所示 或 节点 若节点 有边通向一组节点 2 n 问题 的解决有待于子问题 或 2或 或 n中某一个子问题的解决 则称A为 或 节点 如图b所示 问题空间法有关概念 2 问题的解 解图 从代表初始问题的节点出发 搜索到一个完整的 与或 子图 图中所有叶节点均满足问题求解的结束条件 例 C B Z M M 重写规则 R1 C D L R2 C B M R3 B M M R4 Z B B M 小结 问题求解方法比较 问题求解基本原理 一 问题求解的基本方法二 搜索技术 一 搜索技术预备状态空间搜索有关概念盲目搜索策略启发式搜索策略 问题求解基本原理 搜索策略预备 盲目搜索 不考虑给定问题所具有的特定知识 系统按照事先确定好的某种固定顺序调用规则 或是随机地调用规则 常用的盲目搜索算法 深度优先搜索策略 宽度优先搜索策略 搜索策略预备 启发式信息 与问题求解有关的信息和知识 由于信息的片面性和不准确性 应用启发式信息不能百分之百地保证找到问题的解 但能提高问题求解的可能性 启发式信息在问题求解过程中的作用 有助于加速求解过程 有助于找到 较优 解 启发式搜索策略 考虑给定问题领域具有的特定知识 启发式信息 系统动态地规定规则调用顺序 优先使用 较 合适的规则 搜索策略预备 常用的基于状态图的启发式搜索策略 爬山搜索策略 HillClimbing 大英博物馆搜索策略 BritishMuseum 启发式图搜索策略 A 最佳启发式图搜索策略 A 常用的基于与或图及博弈的启发式搜索策略 最佳启发式与或图搜索策略 AO 极大极小搜索策略 Minimax 剪枝搜索策略 Alpha BetaPruning 基于状态空间的搜索技术 有关搜索概念盲目搜索策略启发式搜索策略 问题求解基本原理 状态空间搜索有关概念 状态图特点 多条路径通向同一节点 例 状态空间搜索有关概念 状态空间搜索有关概念 节点深度 根节点的深度为0 其它节点的深度规定为其父节点的深度加1 即dn 1 dn 1 标记节点n 利用指针把后继节点连接到父节点n的操作 节点 对应状态图中有关状态的描述 扩展节点n 算符 规则 作用于节点n生成的新节点称为节点n的后继节点 生成节点n的所有后继节点并计算生成这些后继节点所使用的花费的过程叫做扩展节点n 路径 对于一个节点序列 n0 n1 nl nk 如若每一节点ni 1都有一个后继节点ni i 1 2 k 则称该节点序列为一条从节点n0到节点nk 长度为k的路径 路径还可表示为与节点序列对应的规则序列 状态空间搜索有关概念 路径花费 设C ni nj 为节点ni到nj这段路径 或弧线 的花费 一条路径的花费等于连接这条路径各节点间所有弧线花费值的总和 路径ni nj t的花费值C ni t 可递归计算如下 C ni t C ni nj C nj t 基于状态空间的盲目搜索算法 宽度优先搜索策略深度优先搜索策略 问题求解基本原理 盲目搜索算法的符号及数据结构 s 初始节点 n 当前节点 open 已被生成但未被扩展的节点序列表 closed 已被生成且已被扩展的节点序列表 mi mj mk ml 扩展n后所得的n的后继节点其中 mk 在OPEN表中出现过的待扩展节点 ml 在CLOSED表中出现过的已扩展节点 宽度优先搜索算法 open S closed whileopen do n first open remove first open add n closed ifn goalthenexit success expand n mi delete mi mi mk mi ml add open mj exit fail 宽度优先搜索算法 1 S A D 2 A D B D 3 D B A E Open表为队操作 先进先出 节点扩展顺序 宽度优先搜索算法 open S closed d 深度限制值whileopen do n first open remove first open add n closed ifn goalthenexit success ifdepth n dthencontinue expand n mi delete mi mi mk mi ml add mj open exit fail 深度优先搜索算法 深度优先搜索算法 1 S 2 A D 3 B D D Open表为栈操作 后进先出 4 C E D 节点扩展顺序 深度优先搜索算法 盲目搜索算法应用实例 8数码问题 描述状态 矩阵 Sij 其中1 i j 3 Sij 0 1 8 盲目搜索算法应用实例 合法走步规则 设 i0 j0 为空格所在行列数值 Si0j0 0R1 ifj 1 1thenSi0j0 Si0 j0 1 Si0 j0 1 0空格左移 R2 ifi 1 1thenSi0j0 S i0 1 j0 S i0 1 j0 0空格上移 R3 ifj 1 3thenSi0j0 Si0 j0 1 Si0 j0 1 0空格右移 R4 ifi 1 3thenSi0j0 S i0 1 j0 S i0 1 j0 0空格下移 8数码问题 宽度优先策略求解8数码问题 深度优先策略求解8数码问题 说明 设规则固定使用顺序 R1 左移 R2 上移 R3 右移 R4 下移 设节点深度限制值 6 合法的走步规则 重复节点 造成循环 问题求解基本原理 基于状态空间的启发式搜索算法 A算法 A 算法 启发式图搜索算法 假设 f n g n h n 任意节点n的评价函数 指迄今为止已找到的从初始节点s 到达节点n 再从节点n到达目标节点t的路径全程的最小费用 是对f n 的一个估计 h n 迄今为止从节点n到目标节点t最佳分段路径将要花费的未知估计费用 是对h n 的一个估计 可视为启发式分量函数 有h n 0 g n 迄今为止搜索到的从初始节点s到当前节点n最佳路径分段的已知费用 是对g n 的一个估计 f n g n h n 从初始节点s出发 经过最佳路径上任意节点n 到达目标节点t的最小费用 h n n t最佳路径的分段费用 g n s n最佳路径的分段费用 s 初始节点 n 当前节点 t 目标节点 启发式图搜索算法 A算法 定义 按照f n g n h n 估价函数值由小到大地排列待扩展节点顺序的图搜索算法 称为A算法 A算法流程 A算法应用实例 普通有向图A算法搜索实例 8数码问题A算法搜索实例 启发式图搜索算法 A算法 算法中符号 s 初始节点 G 搜索图的节点集合 OPEN表 已生成但尚未被扩展的节点序列表 CLOSED表 已生成且已被扩展的节点序列表 n 待扩展的当前节点 mi mj mk ml 扩展n后生成的后继节点其中 mj 第一次生成的节点 mj OPEN且mj CLOSED表 mk 在OPEN表中出现过的待扩展节点 ml 在CLOSED表中出现过的已扩展节点 A算法 启发式最佳图搜索算法 A 算法 A 算法定义 若将A算法中评价函数f n 的启发式分量函数h n 的值限制在h n 的下界范围内 亦即对所有节点n 都满足h n h n 则称此时的A算法为A 算法 A 算法作用 问题有解时 A 算法一定能够找到从初始节点s到目标节点t的最佳解径 信息性定理 有两个A 算法A1和A2 若A2比A1有较多的启发式信息 即对所有非目标节点均有 h1 n h2 n h n 则在具有一条从s到t的隐含状态图上 搜索结束时 由A2扩展的每一个节点 也必定由A1所扩展 即A1扩展的节点数至少和A2一样多 启发式最佳图搜索算法 A 算法 A 算法应用验证 8数码问题A 算法搜索实例 8数码问题搜索策略比较 宽度优先A算法A 算法 小结 启发式搜索策略 g 考虑当前路径已经花费的费用 及时抛弃已经经过的花费太大且距目标仍远的路径 h 估计当前路径上节点到目标节点还需要的费用 引导搜索向最有希望的路径前进 A算法 定义估计函数 f g h A 算法 定义估计函数 f g h 满足h n h n 程序实现宽度优先法和深度优先法求解High waymap问题 给出求解过程 Open Closed内容 标出解径 作业 给定两个油桶 一个可装4公斤油 一个可装3公斤油 油桶上无任何度量标记 问 怎样才能使4公斤油桶里恰好只装2公斤油 设状态定义 x y 其中 x 4公斤油桶中实际装油公斤数 y 3公斤油桶中实际装油公斤数 问题表示 0 0 2 y 要求定义合法的装油规则 利用盲目搜索策略画出状态图 作业