《人工智能基础03__搜索技术》由会员分享，可在线阅读，更多相关《人工智能基础03__搜索技术（80页珍藏版）》请在金锄头文库上搜索。
1、目录 第一章绪论第二章知识表示第三章搜索技术第四章推理技术第五章机器学习第六章专家系统第七章自动规划系统第八章自然语言理解第九章智能控制第十章人工智能程序设计 3 1盲目搜索 盲目搜索 即无信息搜索宽度优先与深度优先3 1 1图搜索策略图搜索策略可看作一种在图中寻找路径的方法 初始节点和目标节点分别代表初始数据库和满足终止条件的数据库 求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题 研究图搜索的一般策略 能够给出图搜索过程的一般步骤 3 1盲目搜索 3 1 1图搜索策略例3 1从王某家族的四代中找王A的后代且其寿命为X的人 A 47 B1 77 A3 52 B2
2、65 C2 87 C1 96 D1 77 E1 57 E2 92 F1 32 G1 27 H1 51 3 1盲目搜索 3 1 1图搜索策略1 图搜索 GRAPHSEARCH 的一般过程 1 建立一个只含有起始节点S的搜索图G 把S放到一个叫做OPEN的未扩展节点表中 2 建立一个叫做CLOSED的已扩展节点表 其初始为空表 3 LOOP 若OPEN表是空表 则失败退出 4 选择OPEN表上的第一个节点 把它从OPEN表移出并放进CLOSED表中 称此节点为节点n 5 若n为一目标节点 则有解并成功退出 此解是追踪图G中沿着指针从n到S这条路径而得到的 指针将在第7步中设置 3 1盲目搜索 3
3、1 1图搜索策略1 图搜索 GRAPHSEARCH 的一般过程 6 扩展节点n 同时生成不是n的祖先的那些后继节点的集合M 把M的这些成员作为n的后继节点添入图G中 7 对那些未曾在G中出现过的 既未曾在OPEN表上或CLOSED表上出现过的 M成员设置一个通向n的指针 把M的这些成员加进OPEN表 对已经在OPEN或CLOSED表上的每一个M成员 确定是否需要更改通到n的指针方向 对已在CLOSED表上的每个M成员 确定是否需要更改图G中通向它的每个后裔节点的指针方向 8 按某一任意方式或按某个探试值 重排OPEN表 9 GOLOOP 3 1盲目搜索 3 1 1图搜索策略2 图搜索算法的几个
4、重要名词 1 OPEN表与CLOSE表OPEN表CLOSED表 3 1盲目搜索 3 1 1图搜索策略3 搜索图与搜索树搜索过程框图 3 1盲目搜索 3 1 1图搜索策略4 图搜索方法分析 图搜索过程的第8步对OPEN表上的节点进行排序 以便能够从中选出一个 最好 的节点作为第4步扩展用 这种排序可以是任意的即盲目的 属于盲目搜索 也可以用以后要讨论的各种启发思想或其它准则为依据 属于启发式搜索 每当被选作扩展的节点为目标节点时 这一过程就宣告成功结束 这时 能够重现从起始节点到目标节点的这条成功路径 其办法是从目标节点按指针向S返回追溯 当搜索树不再剩有未被扩展的端节点时 过程就以失败告终 某
5、些节点最终可能没有后继节点 所以OPEN表可能最后变成空表 在失败终止的情况下 从起始节点出发 一定达不到目标节点 3 1盲目搜索 3 1 2宽度优先搜索定义3 1如果搜索是以接近起始节点的程度依次扩展节点的 那么这种搜索就叫做宽度优先搜索 breadth firstsearch 3 1盲目搜索 3 1 2宽度优先搜索宽度优先搜索算法 1 把起始节点放到OPEN表中 如果该起始节点为一目标节点 则求得一个解答 2 如果OPEN是个空表 则没有解 失败退出 否则继续 3 把第一个节点 节点n 从OPEN表移出 并把它放入CLOSED的扩展节点表中 4 扩展节点n 如果没有后继节点 则转向上述第
6、2 步 5 把n的所有后继节点放到OPEN表的末端 并提供从这些后继节点回到n的指针 6 如果n的任一个后继节点是个目标节点 则找到一个解答 成功退出 否则转向第 2 步 3 1盲目搜索 3 1 2宽度优先搜索 例3 2八数码问题操作规定 允许空格四周上 下 左 右的数码块移入空格中 不许斜方向移动 不许返回先辈结点 初始布局S和目标状态D如下图所示 3 1盲目搜索 3 1 2宽度优先搜索 例3 2八数码问题 3 1盲目搜索 3 1 3深度优先搜索深度优先算法步骤 1 初始结点S放到未扩展节点OPEN中 2 若OPEN为空 则搜索失败 问题无解 3 弹出OPEN表中最顶端结点放到CLOSE表中
7、 并给出顺序编号n 4 若n为目标结点D 则搜索成功 问题有解 5 若n无子结点 转 2 6 扩展n结点 将其所有子结点配上返回n的指针 并按次序压入OPEN堆栈 转 2 3 1盲目搜索 3 1 3深度优先搜索 3 1盲目搜索 3 1 3深度优先搜索有界深度优先搜索 引入搜索深度限制值d 使深度优先搜索过程具有完备性 设定搜索深度限制d 5 问题同深度优先算法中的八数码问题 2 3 1盲目搜索 3 1 3深度优先搜索 3 1盲目搜索 3 1 3深度优先搜索有界深度优先算法步骤 1 初始结点S放入堆栈OPEN中 2 若OPEN为空 则搜索失败 问题无解 3 弹出OPEN中栈顶结点n 放入CLOS
8、E表中 并给出顺序编号n 4 若n为目标结点D 则搜索成功 问题有解 5 若n的深度d n d 则转 2 6 若n无子结点 即不可扩展 转 2 7 扩展结点n 将其所有子结点配上返回n的指针 并压入OPEN堆栈 转 2 3 1盲目搜索 3 1 4等代价搜索宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题 这种推广了的宽度优先搜索算法叫做等代价搜索算法 等代价搜索中的几个记号起始节点记为S 从节点i到它的后继节点j的连接弧线代价记为c i j 起始节点S到任一节点i的路径代价记为g i 如果所有的连接弧线具有相等的代价 那么等代价算法就简化为宽度优先搜索算法 3 2启
9、发式搜索 盲目搜索的不足 效率低 耗费空间与时间 启发式搜索 利用问题域特性的信息 启发信息 进行搜索 3 2 1启发式搜索策略启发式信息按用途分为三种 1 用于确定要扩展的下一个节点 避免盲目扩展 2 在扩展一个节点的过程中 用于确定要生成哪一个或哪几个后继节点 避免盲目生成所有可能节点 3 用于确定某些应该从搜索树中抛弃或修剪得节点 3 2启发式搜索 有序搜索 orderedsearch 利用第一种启发信息 总是选择 最有希望 的节点作为下一个被扩展的节点 估价函数 evaluationfunction 估算节点 希望 的量度 这种量度叫做估价函数 建立估价函数的一般方法 试图确定一个处在
10、最佳路径上的节点的概率 提出任意节点与目标集之间的距离量度或差别量度 或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数 这些特点被认为与向目标节点前进一步的希望程度有关 f n 表示节点n的估价函数值 3 2启发式搜索 3 2 2有序搜索用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点 应用某个算法 例如等代价算法 选择OPEN表上具有最小f值的节点作为下一个要扩展的节点 这种搜索方法叫做有序搜索或最佳优先搜索 best firstsearch 而其算法就叫做有序搜索算法或最佳优先算法 3 2启发式搜索 3 2 2有序搜索有序状态空间搜索算法 1 把起始节点S放
11、到OPEN表中 计算f S 并把其值与节点S联系起来 2 如果OPEN是个空表 则失败退出 无解 3 从OPEN表中选择一个f值最小的节点i 结果有几个节点合格 当其中有一个为目标节点时 则选择此目标节点 否则就选择其中任一个节点作为节点i 4 把节点i从OPEN表中移出 并把它放入CLOSED的扩展节点表中 3 2启发式搜索 3 2 2有序搜索 5 如果i是个目标节点 则成功退出 求得一个解 6 扩展节点i 生成其全部后继节点 对于i的每一个后继节点j a 计算f j b 如果j既不在OPEN表中 又不在CLOSED表中 则用估价函数f把它添入OPEN表 从j加一指向其父辈节点i的指针 以便
12、一旦找到目标节点时记住一个解答路径 c 如果j已在OPEN表上或CLOSED表上 则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值 如果新的f值较小 则 3 2启发式搜索 3 2 2有序搜索 i 以此新值取代旧值 ii 从j指向i 而不是指向它的父辈节点 iii 如果节点j在CLOSED表中 则把它移回OPEN表 7 转向 2 即GOTO 2 3 2启发式搜索 3 2 2有序搜索 开始 把S放入OPEN表 OPEN为空表 失败 选取OPEN表中f值最小的节点i 放入CLOSED表 i Sg 成功 是 是 扩展i得后继节点j 计算f j 提供返回i的指针 利用f j 对OPEN表重新排
13、序调整父子关系及指针 3 2启发式搜索 3 2 2有序搜索宽度优先搜索 等代价搜索和深度优先搜索统统是有序搜索技术的特例 对于宽度优先搜索 选择f i 作为节点i的深度 对于等代价搜索 f i 是从起始节点至节点i这段路径的代价 有序搜索的有效性直接取决于f的选择 如果选择的f不合适 有序搜索就可能失去一个最好的解甚至全部的解 如果没有适用的准确的希望量度 那么f的选择将涉及两个方面的内容 一方面是一个时间和空间之间的折衷方案 另一方面是保证有一个最优的解或任意解 3 2启发式搜索 3 2 2有序搜索例3 4 八数码难题 采用了简单的估价函数f n d n W n 其中 d n 是搜索树中节点
14、n的深度 W n 用来计算对应于节点n的数据库中错放的棋子个数 因此 起始节点棋局的f值等于0 4 4 2 8 3 1 6 4 7 5 3 2启发式搜索 3 2 2有序搜索 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2
15、 3 7 8 4 6 5 3 2启发式搜索 3 2 3A 算法A 算法是一种有序搜索算法 其特点在于对估价函数的定义上 1 A 算法的估价函数k ni nj 表示任意两个节点ni和nj之间最小代价路径的实际代价 对于两节点间没有通路的节点 函数k没有定义 k n ti 从节点n到某个具体的目标节点ti 某一条最小代价路径的代价 h n 表示整个目标节点集合 ti 上所有k n ti 中最小的一个 因此 h n 就是从n到目标节点最小代价路径的代价 而且从n到目标节点能够获得h n 的任一路径就是一条从n到某个目标节点的最佳路径 对于任何不能到达目标节点的节点n 函数h 没有定义 3 2启发式搜
16、索 3 2 3A 算法定义g 为g n k S n 从已知起始节点S到任意节点n的一条最佳路径代价 定义函数f f n g n h n 使得在任一节点n上其函数值f n 就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和 3 2启发式搜索 3 2 3A 算法希望估价函数f是f 的一个估计 此估计可由下式给出 f n g n h n 其中 g是g 的估计 h是h 的估计 对于g n 一个明显的选择就是搜索树中从S到n这段路径的代价 这一代价可以由从n到S寻找指针时 把所遇到的各段弧线的代价加起来给出 这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径 这个定义包含了g n g n h n 对h n 的估计 依赖于有关问题的领域的启发信息 这种信息可能与八数码难题中的函数W n 所用的那种信息相似 把h叫做启发函数 3 2启发式搜索 3 2 3A 算法2 A算法和A 算法的定义定义3 3在GRAPHSEARCH过程中 如果第8步的重排OPEN表是依据f x g x h x 进行的 则称该过程为A算法 定义3 4在A算法中 如果对所有的x存
