人工智能ch3 盲目搜索.ppt

第3章盲目搜索 3 1一般搜索过程3 2回溯策略3 3宽度 广度 优先搜索3 4代价树的宽度优先搜索3 5深度优先搜索 参考教材 M TimJones著 黄厚宽等译 人工智能 电子工业出版社 2010年7月 第3章盲目搜索 搜索 推理与人工智能 搜索是人工智能中的一个基本问题 是推理不可分割的一部分 它直接关系到智能系统的性能与运行效率 尼尔逊把它列为人工智能研究中的核心问题之一 搜索的基本问题 是否一定能找到一个解 是否能终止运行或陷入一个死循环 找到的是否是最佳解 时间与空间复杂性如何 第3章盲目搜索 已提出的搜索策略 求任一解路的搜索策略爬山法 深度优先法 限定范围搜索法 回溯法 最好优先法 求最佳解路的搜索策略宽度优先法 分枝界限法 动态规划法 最佳图搜索法 A 求与或关系解图的搜索法一般与或图搜索法 极大极小法 剪枝法 启发式剪枝法 第3章盲目搜索 搜索策略选取操作算子的方式 盲目搜索对特定问题不具有任何有关信息 按预定步骤 依次或随机 进行搜索 搜索过程中获得的中间信息不用来改进控制策略 特点 能快速调用操作算子 启发式搜索考虑特定问题领域可应用的启发性信息 动态确定调用操作算子的步骤 指导搜索朝最有希望的方向前进 特点 优先选取合适的操作算子 减少不必要搜索 提高效率启发式一般优于盲目搜索 但不能过于追求更多甚至更完整的启发信息 应综合考虑 尽量使搜索系统的总开销较小 第3章盲目搜索 3 1一般搜索过程一 数据结构 OPEN 未扩展节点表扩展 用合适算符对一个节点进行操作 生成一组子节点 存放刚生成的节点 不同搜索策略 节点在OPEN表中的排列顺序不同 CLOSED 已扩展节点表存放将扩展或已扩展节点 3 1一般搜索过程 3 1 3一般搜索过程 3 1一般搜索过程 二 算法流程 建立只含有初始节点S的搜索图G 把S放到OPEN表中 建立CLOSED表 其初始值为空表 若OPEN表是空表 则失败退出 选择OPEN表中第一个节点 把它从OPEN表移出并放进CLOSED表中 称此节点为节点n 若n为目标节点 则有解并成功退出 解是追踪图G中沿指针从n到S这条路径得到 指针在第 步中设置 扩展n 生成不是n的祖先的那些后继节点的集合M 把M的这些成员作为n的后继节点添入图G中 3 1一般搜索过程 二 算法流程 对M中子节点进行如下处理 对没在G中出现过的 即没在OPEN或CLOSED表中出现过的 M成员设置一个指向n的指针 把M的这些成员加进OPEN表 已在OPEN或CLOSED表中的每个M成员 确定是否需要更改指向n的指针方向 已在CLOSED表中的每个M成员 确定是否需要更改图G中它的每个后裔节点指向父节点的指针 按某种方式或按某个试探值 重排OPEN表 转第 步 3 1一般搜索过程 三 几点说明 搜索过程具有通用性此后讨论的各种搜索策略都可以看成是它的特例 各种搜索策略的主要区别在于 步骤 对OPEN表上的节点进行排序的准则 以便选出一个 最好 的节点作为步骤 扩展使用 排序是任意的 即肓目的 盲目搜索 排序用启发信息为依据 启发式搜索 3 1一般搜索过程 三 几点说明 搜索图和搜索树图搜索的一般过程中生成的明确图 被称为搜索图G 由图G中所有节点及反向指针 在第 步形成的指向父节点的指针 构成的集合T 是一棵树 称为搜索树 扩展某节点时图G已保存了从初始节点到该节点的搜索树 G中每个节点 S除外 有且仅有一个指向G中一个父节点的指针 OPEN表中节点都是搜索图上未被扩展的端节点 CLOSED表中节点 是已被扩展但没有生成后继节点的端节点 或是搜索树的非端节点 3 1一般搜索过程 三 几点说明 搜索过程终止条件有解 在第 步 当被选作扩展的节点是目标节点时 搜索过程成功结束 得到了一个解 从目标节点按指向父节点的指针 第 步形成 不断回溯 能重现从初始节点到目标节点的成功路径 解是由从初始节点到该目标节点路径上的算符构成 无解 当搜索树不再有末被扩展的端节点时 即OPEN表为空 搜索过程失败 从初始节点达不到目标节点 3 1一般搜索过程 三 几点说明 步骤 的说明一个节点经一个算符操作通常指生成一个子节点 由于适用于一个节点的算符可能有多个 此时就会生成一组子节点 判断子节点是否是当前扩展节点的父节点 祖父节点等 若是 则删除 余下的子节点记做集合M 加入图G中 扩展节点时 生成该节点的所有后继节点 3 1一般搜索过程 三 几点说明 步骤 的说明问题 一个新生成的节点 若已作为其他节点的后继节点被生成过 该新节点应作为哪个节点的后继节点 解决方法 一般由初始节点到该节点路径上所付出的代价来决定 那条路经付出的代价小 相应的节点就作为父节点 3 1一般搜索过程 实心圆圈代表已扩展节点 它们位于CLOSED表中 空心圆圈代表未扩展节点 它们位于OPEN表中 有向边旁的箭头是指向父节点的指针 设有向弧两端节点间的代价都为1 4 4 5 2 4 3 5 3 1一般搜索过程 3 2回溯策略 基本思想 从初始节点出发 不停地 试探性地寻找路径直到到达目标节点或 不可解节点 为止 当遇到不可解节点时 就回溯到路径中最近的父节点上 查看该节点是否还有其他的子节点未被扩展 如有 则沿这些子节点继续搜索 如找到目标 就成功地退出搜索 返回解题路径 3 2回溯策略 回溯策略示例 3 2回溯策略 回溯策略的数据结构 PS PathStates 表 保存当前搜索路径上的节点若找到目标节点 PS就是解题路径上的节点有序集 NPS NewPathStates 表 新路径表包含待搜索节点 其后裔节点还未被搜索 即未被扩展 NPS可使算法回溯到其中任一节点 NSS NoSolvableStates 表 不可解节点表列出找不到解题路径的节点 如果在搜索中 扩展出的节点包含在NSS中 则立即将它排除 不需要沿着该节点继续搜索 NSS可避免算法重新搜索无解的路径 Open表 3 2回溯策略 回溯策略示例 3 2回溯策略 回溯策略的伪代码 procedurebreadth first searchbeginPS Start NPS Start NSS CS Start 初始化whileNPS dobeginifCS 目标节点thenreturn PS ifCS没有子节点 不包括PS NPS NSS中已有节点 thenbeginwhile PS非空 and CS PS中第一个元素 dobegin将CS加入到NSS 标明此 节点不可解 从CS中删除第一个元素CS 回溯从NPS中删去第一个元素CSCS NPS中第一个元素 end将CS加入PS endendelsebegin将CS子节点 不包括PS NPS和NSS中已有的 加入到NPS CS NPS中第一个元素 将CS加入到PS endruturnFAIL endendend 3 2回溯策略 回溯策略的几点说明 各种合适的推理规则或其他问题求解操作都可以应用于PS 得到一些新的子节点有序集 为避免死循环 若有序集中的子节点已在3张表的任一表中 说明它已被搜索过 不需要再考虑 有序集中的第一个子节点作为CS 当前正在被检测的节点 并加入到PS中 有序集中其余子节点按顺序放入NPS 用于以后搜索 如应用后 CS无子节点 从PS NPS中删除它 并将它加入到NSS中 之后回溯查找NPS中表首位置的节点 3 2回溯策略 3 3宽度优先搜索 基本思想 从初始节点开始 逐层对节点进行扩展 并考察它是否为目标节点 在第n层节点没有全部扩展并考察之前 不对第n 1层的节点进行扩展 3 3宽度优先搜索 一 数据结构 OPEN表包含已生成但子节点未被搜索的节点 表中节点的排列次序就是搜索的次序 OPEN表采用先进先出的队列结构 CLOSED表记录已被生成扩展过的节点 相当于回溯算法中PS表和NSS表的合并 3 3宽度优先搜索 二 算法流程 把起始节点放到OPEN表中 如果该起始节点为一目标节点 则求得一个解答 若OPEN是空表 则没有解 失败退出 否则继续 把第一个节点 节点n 从OPEN表移出 并把它放入CLOSED的扩展节点表中 扩展n 如果没有后继节点 则转向步骤 把n的所有后继节点放到OPEN表的末端 并提供从这些后继节点回到n的指针 如果n的任一个后继节点是个目标节点 则找到一个解答 成功退出 否则转向步骤 3 3宽度优先搜索 四 几点说明 删除OPEN或CLOSED表中出现过的子状态 避免循环搜索 只要问题有解 总能找到最短解题路径 如果问题无解 对有限图 算法会失败退出 对无限图 则永远不会终止 3 3宽度优先搜索 五 算法的缺陷 盲目性较大 当目标节点距初始节点较远 会产生许多无用节点 搜索效率低 因此 当图中分枝数太多 实用意义不大 图中各边代价都相同 都为一个单位量 从而可用路径的长度代替路径的代价 然而 对许多问题这种假设是不现实的 即状态空间中各边的代价不可能完全相同 代价树的宽度优先搜索算法 启发式搜索算法 3 3宽度优先搜索 3 4代价树的宽度优先搜索算法 例 城市交通问题 设有5个城市 它们之间的交通路线如图所示 图中的数字表示两个城市之间的交通费用 即代价 求从A市出发到E市 费用最小的交通路线 结论 在搜索树中给每条边都标上代价 3 4代价树的宽度优先搜索 一 代价树生成方法 从初始节点A开始 把与A直接相邻的节点作为子节点 对其他节点作相同处理 若一个节点已是某节点的直系先辈节点 就不能再作为该节点的子节点 除A外 其它节点可能在代价树中多次出现 为便于区分 用下标1 2 标出 3 4代价树的宽度优先搜索 二 代价的定义 若节点j是i的子女 c i j 从i到j的连接弧线代价 g i 从起始节点S到i的路径代价 即从S到i的最少代价路径上的代价 g j g i c i j 3 4代价树的宽度优先搜索 三 算法流程 把起始节点S放到未扩展节点表OPEN中 如果S为一目标节点 则求得一个解 否则令g S 0 如果OPEN是个空表 则没有解 失败退出 把OPEN表中第一个节点n取出 放入CLOSED表 如果n是目标节点 则求得问题的解 退出 若n不可扩展 则转第 2 步 扩展n 将其子节点放入OPEN表 并配置指向父节点的指针 计算各子节点的代价 按代价对OPEN表中全部节点从小到大进行排序 然后转第 步 3 4代价树的宽度优先搜索 四 示例 最优解为 A B1 E1代价为 9 3 4代价树的宽度优先搜索 3 5深度优先搜索 从初始节点开始 在其子节点中选择一个进行考察 记为子节点n 若n不是目标节点 搜索n所有子节点以及子节点的后裔节点 当到达某个子节点 该子节点既不是目标节点又不能继续扩展 才选择n的兄弟节点进行考察 3 5深度优先搜索 一 两种算法比较 3 5深度优先搜索 二 算法缺陷和解决方法 缺陷 搜索一旦进入某个分支 就沿着该分支一直向下搜索 如果目标节点不在此分支上 且该分支又是一个无穷分支 则不可能得到解 因此 深度优先搜索是不完备的 解决方法 为防止搜索沿一条路径无限扩展 深度优先搜索常设定深度限制值 即有界深度优先搜索 3 5深度优先搜索 三 有界深度优先搜索 节点深度定义起始节点的深度为0 其他节点的深度等于其父节点的深度加1 深度界限为避免考虑太长路径 防止搜索沿着无益路径扩展 往往给出一个节点扩展的最大深度 称为深度界限 若达到深度界限 对任何节点都认为它们没有后继节点 采用深度界限后 解答路径也不一定是最短路径 3 5深度优先搜索 三 有界深度优先搜索 算法流程 把起始节点S放到OPEN表中 如果此节点为目标节点 则得到一个解 如果OPEN为空表 则失败退出 把第一个节点 节点n 从OPEN表移到CLOSED表 如果n的深度等于最大深度dm 则转向步骤 扩展n 产生其全部后裔 并把它们放入OPEN表的前头 如果没有后裔 则转向步骤 如果后继节点中有任一个为目标节点 则求得一个解 成功退出 否则 转向步骤 3 5深度优先搜索 3 5深度优先搜索 三 有界深度优先搜索 如果问题有解 且路径长度 dm 则上述搜索过程一定能求得解 但若解的路径长度 dm 则得不到解 为找到最优解 可增设表R 每找到一个目标节点Sg后 就把它放到R的前面 并令dm等于该目标节点所对应的路径长度 然后继续搜索 3 5深度优先搜索 四 代价树的深度优先搜索 算法