第1讲 搜索问题.pptx

人工智能 中国农业大学信息与电气工程学院 第1讲搜索问题 问题求解 2 大纲 一 搜索问题表示法二 状态空间的搜索策略 盲目搜索盲目搜索又叫做无信息搜索 一般只适用于求解比较简单的问题 且需要大量的时间空间作为基础 启发式搜索启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估 得到最好的位置 再从这个位置进行搜索直到目标 3 搜索问题 续1 S0 Sg 问题全状态空间 问题的搜索空间 解路径 概念1 状态空间表示法 状态空间表示法是用来表示问题及其搜索过程的一种方法 是人工智能中最基本的形式化方法 也是讨论问题求解技术的基础 是用 状态 和 算符 来表示问题的一种方法 其中 状态 用以描述问题求解过程中不同时刻的状况 算符 表示对状态的操作 算符的每次使用就使问题由一种状态变换为另一种状态 当到达目标状态时 由初始状态到目标状态所用算符的序列就是问题的一个解 概念1 状态空间表示法 状态是描述问题求解过程中的任一时刻的数据结构 一般用一组变量的有序组合表示 算符 引起状态中某些分量发生改变 从而使一个具体状态变化到另一个具体状态的作用 状态空间 由问题的全部状态及一切可用算符所构成的集合 称为问题的状态空间 一般用三元组表示 S是问题的初始状态集合 F是算符的集合 G是目标状态的集合 6 举例 梵塔问题的状态空间 举例 二阶梵塔问题 一号杆有A B两个金盘 A小于B 要求将AB移至三号杆 每次只可移动一个盘子 任何时刻B不能在A上 用二元组 SA SB 表示状态 SA表示A所在杆号 SB表示B所在杆号 全部状态如下 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 7 举例梵塔问题的状态空间 B A A A A A B A B B B B B B B 8 举例梵塔问题的状态空间 转换规则 A i j 表示金盘A从第i号杆移到j号杆B i j 表示金盘B从第i号杆移到j号杆A 1 2 A 1 3 A 2 1 A 2 3 A 3 1 A 3 2 B 1 2 B 1 3 B 2 1 B 2 3 B 3 1 B 3 2 初始状态 1 1 目标状态 3 3 梵塔问题用状态图表示为 9 举例 梵塔问题的状态空间 1 1 2 1 3 1 2 3 3 3 1 3 3 2 1 2 2 2 A 1 3 A 2 1 B 3 1 A 3 2 A 1 3 B 1 3 A 2 1 B 1 2 A 3 2 10 思考 n n 3 阶梵塔问题 假设金片Pk从小片到大片按下标k顺序编号 即k 1 2 3 n n阶梵塔问题状态空间可用矢量表示为 P1 P2 P3 Pk Pn Pk表示第k个金片穿在编号为Pk的宝石针上 Pk 1 2 3 初始状态S0 1 1 1 1 1 目标状态Sg1 2 2 2 2 2 Sg2 3 3 3 3 3 11 n n 3 阶梵塔问题 n阶梵塔问题的操作集合表示为 F Rk i j i j 1 2 3 k 1 2 n 全部可能状态数为3n个 最佳解长度为2n 1 三阶梵塔问题状态图 S0 1 1 1 Sg2 3 3 3 Sg1 2 2 2 概念2 与或树 与或图 表示法 分解 一个复杂的问题P常常可以分解为与之等价的一组子问题P1 P2 Pn 当这些问题全部可解时 问题可解 任何一个子问题无解时 都将导致原问题P无解 即一个问题与一组子问题的与等价 等价变换 一个复杂的问题P常常可以分别归约为与之等价的一组子问题P1 P2 Pn 其中任何一个子问题可解时 问题可解 全部子问题无解时 原问题P无解 即一个问题与一组子问题的或等价 概念2 与或树 与或图 表示法 与 或 或 概念2 与或树 与或图 表示法 与或图的几个概念直接可解的问题称为本原问题 本原问题对应的节点称为终止节点 无子节点的节点称为端节点 子节点为与关系 则该节点为与节点 子节点为或关系 则该节点为或节点 与或图一般表示问题的变换过程 就是从原问题出发 运用某些规则不断的进行问题的分解 得到与分支 和变换 得到或分支 而得到一个与或图 与或图的节点一般代表问题 整个图就表示问题空间 二 状态空间的搜索策略 广度 广度 搜索策略深度搜索策略有界深度优先策略代价树的广度优先策略代价树的深度优先策略启发式搜索A 算法 16 1 1回溯策略 例 皇后问题 17 18 Q 1 1 19 Q Q 1 1 1 1 2 3 20 Q 1 1 1 1 2 3 21 Q Q 1 1 1 1 2 3 1 1 2 4 22 Q Q 1 1 1 1 2 3 1 1 2 4 Q 1 1 2 4 3 2 23 Q Q 1 1 1 1 2 3 1 1 2 4 1 1 2 4 3 2 24 Q 1 1 1 1 2 3 1 1 2 4 1 1 2 4 3 2 25 1 1 1 1 2 3 1 1 2 4 1 1 2 4 3 2 26 1 1 1 1 2 3 1 1 2 4 1 1 2 4 3 2 Q 1 2 27 1 1 1 1 2 3 1 1 2 4 1 1 2 4 3 2 Q 1 2 Q 1 2 2 4 28 1 1 1 1 2 3 1 1 2 4 1 1 2 4 3 2 Q 1 2 Q 1 2 2 4 Q 1 2 2 4 3 1 29 1 1 1 1 2 3 1 1 2 4 1 1 2 4 3 2 Q 1 2 Q 1 2 2 4 Q 1 2 2 4 3 1 Q 1 2 2 4 3 1 4 3 30 回溯搜索算法 OPEN表CLOSED表OPEN表用于存放刚生成的节点 CLOSED表用于存放将要扩展或者已经扩展的节点 31 一般回溯搜索算法 1 把初始节点S0放入OPEN表 并建立目前只包含S0的图 记为G 2 检查OPEN表是否为空 若为空则问题无解 退出 3 把OPEN表的第一个节点取出放入CLOSED表 并记该节点为节点n 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 扩展节点n 生成一组子节点 把其中不是节点n先辈的那些子节点记作集合M 并把这些子节点作为节点n的子节点加入G中 6 针对M中子节点的不同情况 分别进行如下处理 32 一般回溯搜索算法 续 6 1对于那些未曾在G中出现过的M成员设置一个指向父节点 即节点n 的指针 并把它们放入OPEN表 6 2对于那些先前已经在G中出现过的M成员 确定是否需要修改它指向父节点的指针 6 3对于那些先前已经在G中出现并且已经扩展了的M成员 确定是否需要修改其后继节点指向父节点的指针 7 按某种搜索策略对OPEN表中的节点进行排序 8 转第2步 思考题1 如何理解状态空间的一般搜索过程 34 存在问题及解决办法 解决办法 对搜索深度加以限制记录从初始状态到当前状态的路径 问题 深度问题 死循环问题 35 1 2图搜索策略 问题的引出回溯搜索 只保留从初始状态到当前状态的一条路径 图搜索 保留所有已经搜索过的路径 36 一些基本概念 节点深度 根节点深度 0其它节点深度 父节点深度 1 0 1 2 3 37 一些基本概念 续1 路径设一节点序列为 n0 n1 nk 对于i 1 k 若节点ni 1具有一个后继节点ni 则该序列称为从n0到nk的路径 路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和 用C ni nj 表示从ni到nj的路径的耗散值 38 一些基本概念 续1 扩展一个节点生成该节点的所有后继节点 并给出它们之间的耗散值 这一过程称为 扩展一个节点 39 40 1 3无信息图搜索过程 广度优先搜索深度优先搜索 广度优先搜索 41 42 深度优先搜索 1 把初始节点S0放入OPEN表 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 若节点n不可扩展 则转第2步 6 扩展节点n 将其子节点放入到OPEN表的首部 并为其配置指向父节点的指针 然后转第2步 43 44 有界深度优先搜索 1 把初始节点S0放入OPEN表中 置S0的深度d S0 0 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 如果节点n的深度d 节点n dm 则转第2步 6 若节点n不可扩展 则转第2步 7 扩展节点n 将其子节点放入到OPEN表的首部 并为其配置指向父节点的指针 然后转第2步 45 46 代价树 图 在上面的讨论中 都没有考虑搜索的代价问题 当时假设图中各边的代价都相同 且都为一个单位量 边上标有代价 或费用 的树 图 称为代价树 图 在代价树中 若用g x 表示从初始节点S0到节点x的代价 用c x1 x2 表示从父节点x1到节点x2的代价 则有 g x2 g x1 c x1 x2 广度优先搜索 47 48 广度优先搜索 1 把初始节点S0放入OPEN表 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表中 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 若节点n不可扩展 则转第2步 6 扩展节点n 将其子节点放入OPEN表的尾部 并为每一个子节点都配置父节点的指针 然后转第2步 49 代价树的广度优先搜索 1 把初始节点S0放入OPEN表 令g S0 0 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表中 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 若节点n不可扩展 则转第2步 6 扩展节点n 将其子节点放入OPEN表中 并为其配置父节点的指针 计算各子节点的代价 并按各节点的代价对OPEN表中的全部节点进行排序 按从小到大的顺序 然后转第2步 举例 交通图A城是出发地 E是目的地 数字表示两城之间交通费用 求A到E的最小费用的旅行路线 50 广度优先搜索 代价树的深度优先搜索 52 53 代价树的深度优先搜索 1 把初始节点S0放入OPEN表 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 若节点n不可扩展 则转第2步 6 扩展节点n 将其子节点按边代价从小到大的顺序放到OPEN表的首部 并为各子节点配置指向父节点的指针 然后转第2步 举例 交通图A城是出发地 E是目的地 数字表示两城之间交通费用 求A到E的最小费用的旅行路线 54 广度优先搜索 10 10 10 10 10 56 深度优先搜索的性质 一般不能保证找到最优解当深度限制不合理时 可能找不到解 可以将算法改为可变深度限制最坏情况时 搜索空间等同于穷举与回溯法的差别 图搜索是一个通用的与问题无关的方法 57 渐进式深度优先搜索方法 属于有界深度搜索的一种 目的解决广度优先方法的空间问题和回溯方法不能找到最优解的问题 思想首先给回溯法一个比较小的深度限制 然后逐渐增加深度限制 直到找到解或找遍所以分支为止 58 1 4启发式图搜索 利用知识来引导搜索 达到减少搜索范围 降低问题复杂度的目的 启发信息的强度强 降低搜索工作量 但可能导致找不到最优解弱 一般导致工作量加大 极限情况下变为盲目搜索 但可能可以找到最优解 59 希望 引入启发知识 在保证找到最佳解的情况下 尽可能减少搜索范围 提高搜索效率 60 基本思想 定义一个评价函数f 对当前的搜索状态进行评估 找出一个最有希望的节点来扩展 61 1 启发式搜索算法A A算法 评价函数f x 的格式 f x g x h x g x 从初始节点S0到节点x的实际付出的代价h x 从节点x到目标节点Sg的最优路径估计的代价f x 表示从初始节点S0经过节点x到目标节点Sg的代价估计值 62 局部择优搜索 1 把初始节点S0放入OPEN表 计算f S0 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 若节点n不可扩展 则转第2步 6 扩展节点n 用估价函数f x 计算每个子节点的估价值 并按估价值从小到大的顺序依次放到OPEN表的首部 为每个子节点配置指向父节点的指针 然后转第2步 63 局部择优搜索与深度优先搜索的关系 深度优先搜索 代价树的深度优先搜索以及局部择优搜索都是以子节点作为考察范围的 若令f x g x 则局部择优搜索就成为代价树的深度优先搜索 若令f x d x 这里d x 表示节点x的深度 则局部择优搜索就成为深度优先搜索 所以深度优先搜索和代价树的深度优先搜索可看作局部择优搜索的两个特例 64 全局择优搜索 1 把初始节点S0放入OPEN表 计算f S0 2 如果OPEN表为空 则问题无解 退出 3 把OPEN表的第一个节点 记为节点n 取出放入CLOSED表 4 考察节点n是否为目标节点 若是 则求得了问题的解 退出 5 若节点n不可扩展 则转第2步 6 扩展节点n 用估价函数f x 计算每个子节点的估价值 并为每个子节点配置指向父节点的指针 把这些子节点都送入OPEN表中 然后对OPEN表中的全部节点按估价值从小到大的顺序进行排序7 转第2步 65 全局择优搜索与广度优先搜索的关系 在全局择优搜索中 若令f x g x 则全局择优搜索就成为代价树的广度优先搜索 若令f x d x 这里d x 表示节点x的深度 则全局择优搜索就成为广度优先搜索 所以广度优先搜索和代价树的广度优先搜索可看作全局择优搜索的两个特例 作业题 用C 完成12皇后问题的求解 要求显示每种求解的皇后位置坐标 提供代码和结果 谢谢听讲 人工智能 中国农业大学信息与电气工程学院 第1讲搜索问题 问题求解 续 2最佳图搜索算法A A 算法 69 70 2最佳图搜索算法A A 算法 如果使一般搜索过程满足如下条件 则它成为A 算法 1 把OPEN表中的节点按估价函数 f x g x h x 的值从小到大进行排序 一般搜索过程的第7步 2 g x 是对g x 的估计 g x 0 3 h x 是对h x 的下界 即对所有的x均有 h x h x 其中g x 是从初始节点S0到节点x的最小代价 h x 是从节点x到目标节点的最小代价 若有多个目标节点 则为其中的最小值 71 A 算法的性质 A 算法的假设设ni nj是任意两个节点 有 C ni nj 其中 为大于0的常数 几个等式1 f s f t h s g t f n 其中s是初始节点 t是目标节点 n是s到t的最佳路径上的节点 2 对于最佳路径 s n1 n2 ni t 中的任一节点ni 均有f ni f s 3 对于一条到达t的最佳路径 s n1 n2 ni ni 1 t 则针对任一节点ni 路径 s n1 n2 ni 也是从s到达ni的最佳路径 即 g ni g ni 证明 对任意节点ni 若 s n1 n2 ni 不是到达ni的最佳路径 即存在路径 s n1 n2 ni 使得从s到达ni更近 那么显然路径 s n1 n2 ni ni 1 t 也是从s到达t的最佳路径 这与 s n1 n2 ni ni 1 t 是从s到达t的最佳路径矛盾 问题 什么是图搜索 其中 重排OPEN表意味着什么 重排的原则是什么 广度优先搜索方法中OPEN表需要按什么方式进行操作A 先进后出B 先进先出有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗 试比较各种盲目搜索搜索方法的效率 找出影响算法效率的原因试比较广度优先搜索 有界深度优先搜索及有序搜索的搜索效率 并以实例数据加以说明 启发式搜索的必要性 现实的困难迫使人们转而求援于启发式算法 这种算法的本质是部分地放弃算法 一般化 通用化 的概念 把所要解的问题的具体领域的知识加进算法中去 以提高算法的效率 如广度优先法几乎可以用于解一切搜索问题 九宫图 八数码难题 hanoi塔 焚塔问题 旅行推销员 华容道 以至魔方等等 但实际使用时 效率也许低得惊人 甚至根本解不出来 例如魔方问题 如果我们为每类问题找出一些特殊规则 和广度优先法配合起来使用 那结果就可能完全不一样了 启发式搜索的必要性 根据启发信息 在生成各种搜索树时可以考虑种种可能的选择 如 1 下一步展开哪个节点 2 是部分展开还是完全展开 3 使用哪个规则 或算子 4 怎样决定舍弃还是保留新生成的节点 5 怎样决定舍弃还是保留一棵子树 6 怎样决定停止或继续搜索 7 如何定义启发函数 评价函数 8 如何决定搜索方向 由于这些选择的不同 就得到了不同的启发式算法 解路径如粗线所标左 上 右 下 S A B L M等为状态空间图中各个节点名 其后的小括号中数字表示该节点的评价函数f n 的估计值 例如S 4 L 5 等 图中标记 节点为被扩的节点 标记 的节点为生成的节点 九宫重排问题 搜索效率比较 77 A 算法的性质 续1 定理1 1 对有限图 如果从初始节点s到目标节点t有路径存在 则算法A一定成功结束 78 A 算法的性质 续2 引理1 1 对无限图 若有从初始节点s到目标节点t的路径 则A 不结束时 在OPEN表中即使最小的一个f值也将增到任意大 或有f n f s 证明 假设A 不终止 设e是图中各条边的最小代价 d xn 是从S0到节点xn的最短路径长度 则显然有 g xn d xn e 又因为g xn g xn 所以有g xn d xn e 因为h xn 0 f xn g xn 故得到f xn d xn e 由于A 算法不终止 随着搜索的进行 d xn 会无限增大 从而使f xn 也无限增大 最终使得f n f s 而f s 显然应该是一个有限值 矛盾 79 A 算法的性质 续3 引理1 2 在A 终止前的每一步 总是有一个节点n 它在OPEN表中 且存在以下属性 n在最佳路径上 A 已经发现了到达n的一条最佳路径 f n f s 证明 用归纳法 在搜索开始时 S在OPEN表中 它是到达目标的一条最佳路径 A 已经发现了这条路径 而且因为f S h S h S f S 定理成立 假设在节点m m 0 扩展时引理的结论是正确的 现在证明在节点 m 1 扩展时引理是正确的 80 A 算法的性质 续4 设n是m个节点扩展后 A 发现的一个最佳路径上的假设节点 它在OPEN上 如果在第 m 1 步 n没有被选择扩展 n的属性和以前相同 因此证明了归纳步骤 如果n被选为扩展点 它的所有后继将被放在OPEN上 他们中至少有一个np 将会在到达目标的最优路径上 因为由于假定一个最优路径通过n 它必须通过它的一个后继 故A 找到了到达np的一条最佳路径 因为如果有到达np的一条更好路径 那么这条路径也是到达目标的更好路径 这和我们的假设没有比通过n到达目标的路径更好的路径相矛盾 这样 我们让np称为第m 1步新的n 现在证明f np f s 因为对在一条最佳路径上的节点np A 已经找到了到达np的一条最佳路径 我们有 f np g np h np g np h np g np h np f np f s 81 A 算法的性质 续5 定理1 2 对无限图 若从初始节点s到目标节点t有路径存在 则A 一定成功结束 证明 由引理1 1 则OPEN中所有的n有f n f s 由引理1 2 在A 结束前OPEN表中必存在节点n 使得f n f s 所以如果不结束 将导致矛盾 82 A 算法的性质 续6 推论1 1 OPEN表上任一具有f n f s 的节点n 最终都将被A 选作扩展的节点 证明 由定理1 2知 A 一定结束 由A 的结束条件 OPEN表中f t 最小时才结束 而f t f t f s 所以 f n f s 的n 均被扩展 83 A 算法的性质 续7 定理1 3 可采纳性定理 若存在从初始节点s到目标节点t的路径 则A 必能找到最佳解结束 84 可采纳性的证明 续8 证明 由定理1 1 1 2知 A 一定会找到一个目标节点结束 设找到一个目标节点t结束 而s到t不是一条最佳路径 即 f t g t f s 而根据引理1 2知结束前OPEN表上一定存在有节点n 且处在最佳路径上 并有f n f s 所以f n f s f t 这时算法A 应选n作为当前节点扩展 不可能选t 从而也不会去测试目标节点t 即这与假定A 选t结束矛盾 所以A 只能结束在最佳路径上 85 A 算法的性质 续9 推论1 2 A 选作扩展的任一节点n 有f n f s 证明 由引理1 2知 在A 结束前 OPEN中存在节点n 使得f n f s 设此时A 选择n扩展 如果n n 则f n f s 得证 如果n n 由于A 选择n扩展 而不是n 所以有f n f n f s 得证 86 A 算法的性质 续10 定理1 4 设对同一个问题定义了两个A 算法A1和A2 若A2比A1有较多的启发信息 即对所有非目标节点有h2 n h1 n 则在具有一条从s到t的路径的隐含图上 搜索结束时 由A2所扩展的每一个节点 也必定由A1所扩展 即A1扩展的节点数至少和A2一样多 简写 如果h2 n h1 n 目标节点除外 则A1扩展的节点数 A2扩展的节点数 87 A 算法的性质 续11 注意 在定理1 4中 评价指标是 扩展的节点数 也就是说 同一个节点无论被扩展多少次 都只计算一次 88 定理1 4的证明 续12 使用数学归纳法 对节点的深度进行归纳 1 当d n 0时 即只有一个节点 显然定理成立 2 设d n k时定理成立 归纳假设 3 当d n k 1时 用反证法 设存在一个深度为k 1的节点n 被A2扩展 但没有被A1扩展 而由假设 A1扩展了n的父节点 即n已经被生成了 因此当A1结束时 n将被保留在OPEN中 89 定理1 4的证明 续1 因为A1没有扩展n 所以有 f1 n f s 推论1 1 即 g1 n h1 n f s 所以 h1 n f s g1 n 由于A2扩展了n 有f2 n f s 推论1 2 即 h2 n f s g2 n A 另一方面 由于d n k时 A2扩展的节点A1一定扩展 有g1 n g2 n 因为A2的路A1均走到了 所以 h1 n f s g1 n f s g2 n B 比较A B两式 有h1 n h2 n 与定理条件矛盾 故定理得证 90 对h加以限制 定义 一个启发函数h 如果对所有节点ni和nj 其中nj是ni的子节点 满足h ni h nj c ni nj h t 0或h ni c ni nj h nj h t 0则称h