《蔡自兴全套配套课件人工智能基础第2版 第3章 搜索原理》由会员分享，可在线阅读，更多相关《蔡自兴全套配套课件人工智能基础第2版 第3章 搜索原理（34页珍藏版）》请在金锄头文库上搜索。
1、智 能 基人 工 智 能 基 础 主讲 蔡自兴教授主讲 蔡自兴教授 1 第三章 搜索原理第三章 搜索原理 3 1 盲目搜索3 1 盲目搜索 3 2 启发式搜索 3 3 博弈树搜索 3 4 遗传算法 3 5 模拟退火算法3 5 模拟退火算法 3 6 免疫算法免疫算法 3 1 盲目搜索 3 1 1 图搜索策略3 1 1 图搜索策略 一种在图中寻找路径的方法 图中每个节点对应个状态每条连线对应图中每个节点对应一个状态 每条连线对应一 个操作符 这些节点和连线 即状态与操作符 又分别由产生式系统的数据库和规则来标记又分别由产生式系统的数据库和规则来标记 求得把一个数据库变换为另一数据库的规则序 列问题
2、就等价于求得图中的条路径问题列问题就等价于求得图中的一条路径问题 OPEN表和CLOSED表 图搜索过程框图 3 开始开始 把把S放入放入OPEN表表 是是 OPEN表为空表 表为空表 把第一个节点把第一个节点 n 从从OPEN表移至表移至CLOSED表表 失败失败 是是 否否 把第一个节点把第一个节点 n 从从OPEN表移至表移至CLOSED表表 n为目标为目标节节点吗 点吗 成成功功 是是 节节 把把n的后继节点放入的后继节点放入OPEN表的表的 末端末端提供返节点提供返节点 的指针的指针 成成 否否 末端末端 提供返提供返回回节点节点n的指针的指针 修改指针方向修改指针方向修改指针方向修
3、改指针方向 重排重排OPEN表表 4 图图3 2 图搜索过程框图图搜索过程框图 3 1 1 图搜索策略 盲目搜索盲目搜索 特点 不需重排OPEN表 种类 宽度优先 深度优先 等代价搜索 等 等 启发式搜索 特点重排OPEN表选择最有希望的节特点 重排OPEN表 选择最有希望的节 点加以扩展 种类 有序搜索 A 算法等 5 3 1 2 宽度优先搜索 定义定义 以接近起始节点的程度逐层扩展节点的搜索 方法 特点 特点 一种高代价搜索 但若有解存在 则必能找 到它到它 算法 6 开始开始 把把S放入放入OPEN表表 OPEN表为空表 表为空表 失败失败 是是 否否 把第一个节点把第一个节点 n 从从
4、OPEN表移至表移至CLOSED表表 否否 扩展扩展n 把 把n的后继节点放入的后继节点放入OPEN 表的末端 提供返回节点表的末端 提供返回节点n的指针的指针 是否有后继节点 为目标 是否有后继节点 为目标节节点 点 成功成功 是是 节节 否否 7 图图3 4 宽度优先算法框图宽度优先算法框图 3 1 2 宽度优先搜索 八数码难题 8lbl 八数码难题 8 puzzle problem 238123 14 567 84 567567567 目标状态 初始状态 规定 将牌移入空格的顺序为 从空格左边开 始顺时针旋转不许斜向移动也不返回先辈始顺时针旋转 不许斜向移动 也不返回先辈 节点 8 1
5、238 4 567 1 23823238238 6789 10111213 1 238 4 567 1 23 84 567 1 238 4 5 6 7 1 238 4 567 2345 12 38 41 238 4 56 741 23 8 567 1 2 3 841 238 4 5 6 7 1 238 4 5 6 7 1 2 3 8 4 567 10111213 1 238 45 67567567 4 56567575756767567567 12 38 41 238 47 1 23 84 1 2 3 8 4 238 461 238 61 2 3 8 4 14 151617 18 19 20
6、21 1 238 4 5 23 2425 26 27 22 14 567 14 56 7 4 567 1 8 5671 4 57 1 457 1 4 567 1 4 67 14 1 2 38 4 238 471 238 47 1 23 8 47 1 2 3 8 4 2425 26 2 38 9 图图3 5 八数码难题的宽度优先搜索树八数码难题的宽度优先搜索树 5656715656565677 3 1 3 深度优先搜索 定义定义 首先扩展最新产生的 即最深的 节点 算法 防止搜索过程沿着无益的路径扩展下去防止搜索过程沿着无益的路径扩展下去 往往给出一个节点扩展的最大深度 深度 界限界限 与宽度优
7、先搜索算法最根本的不同在于 将 扩展的后继节点放在OPEN表的前端扩展的后继节点放在OPEN表的前端 10 3 1 4 等代价搜索 定义定义 是宽度优先搜索的一种推广 不是沿着等长 度路径断层进行扩展 而是沿着等代价路径 断层进行扩展 搜索树中每条连接弧线上的有关代价 表示时 间 距离等花费 间距离等花费 算法 若所有连接弧线具有相等代价则简化为宽若所有连接弧线具有相等代价 则简化为宽 度优先搜索算法 11 开始开始 把把S S放入放入OPENOPEN表表把把S S放入放入OPENOPEN表表 S是否目标节点S是否目标节点 是是 成功成功 否否 令令g s 0 否否 OPEN表为空表 表为空表
8、 失败失败 是 否 是 否 把具有最小把具有最小g i 值的节点值的节点i从从OPEN表 移至 表 移至CLOSED表表 是否有后继节点是否有后继节点 为目标节点为目标节点 成功成功 是是 为目标节点为目标节点 否否 扩展扩展i i 计算计算其后继其后继节节点点j j的的g j 12 图图3 9 等代价搜索算法框图等代价搜索算法框图 扩展扩展计算节计算节j jg j 并把后继节点放入并把后继节点放入OPEN表表 3 2 启发式搜索 3 2 1 启发式搜索策略 盲目搜索可能带来组合爆炸 启发式信息启发式信息 用来加速搜索过程的有关问题领域的特征信 息按其用途分为息 按其用途分为 用于决定要扩展的
9、下一个节点 以免像在宽度优 先或深度优先搜索中那样盲目地扩展先或深度优先搜索中那样盲目地扩展 在扩展一个节点的过程中 用于决定要生成哪一 个或哪几个后继节点以免盲目地同时生成所有个或哪几个后继节点 以免盲目地同时生成所有 可能的节点 用于决定某些应该从搜索树中抛弃或修剪的节点用于决定某些应该从搜索树中抛弃或修剪的节点 13 3 2 1 启发式搜索策略 估价函数估价函数 获得某些节点 希望 的启发信息 f n 表示节点n的估价函数值 重排OPEN表重排OPEN表 3 2 2 有序搜索 实质 选择OPEN表上具有最小f值的节点作为下一选择OPEN表上具有最小f值的节点作为下 个节点 14 开始开始
10、 把把S放入放入OPEN表 计算估价函数 表 计算估价函数 f s OPEN表为空表 表为空表 失败失败 是是 选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CLOSED表表 否否 i为目标节点吗 为目标节点吗 成功成功 是是 扩展扩展i 得后继节点 得后继节点j 计算 计算f j 提供返回 提供返回 节点节点i的指针的指针利用利用f j 对对OPEN表重新排表重新排 否否 节点节点i的指针的指针 利用利用f j 对对OPEN表重新排表重新排 序 调整亲子关系及指针序 调整亲子关系及指针 15 图图3 10 有序搜索算法框图有序搜索算法框图 3 2 2 有序搜索 八数码难题 8l
11、bl 八数码难题 8 puzzle problem 123 841 238 46 567 态 57 态 目标状态 初始状态 16 57 1 1 238 46 4 7 1 238 41 238 4 6 1 238 4 6 4 6 6 2 4 3 5675757 23238238 5 1 8 4 567 14 567 1 4 567 6 5 5 5 1 23 841 2 3 84 5 7 1 238 4712 38 4 6 7 6 56756756567 1 23 8 8 4 567 5 17 8 132 4 567 1 23 84 56 7 5 7 图图3 11 八数码难题的有序搜索树八数码难题
12、的有序搜索树 3 2 3 A 算法 估价函数估价函数 对节点n定义f n g n h n 表示从S开始 约束通过节点n的一条最佳路径的代价 希望估价函数f 定义为 f n g n h n 希望估价函数 定义为 g g是g 的估计 h是h 的估计 A 算法的定义A 算法的定义 定义3 3 定义3 4 定义3 5 18 3 3 博弈树搜索 3 3 1 博弈概述3 3 1 博弈概述 对垒的MAX MIN双方轮流采取行动 博弈的采行动博弈 结果只有三种情况 在对垒过程中 任何一方都了解当前的格局及在对垒过程中 任何方都了解当前的格局及 过去的历史 任何一方在采取行动前都要根据当前的实际情任何一方在采取
13、行动前都要根据当前的实际情 况 进行得失分析 选取对自已为最有利而对 对方最为不利的对策对方最为不利的对策 19 3 3 2 极小极大分析法 设博弈的双方中方为MAX另方为MIN设博弈的双方中一方为MAX 另一方为MIN 找到当前的最优行动方案 定义一个估价函数 用来估算当前博弈树端节 点的得分 当端节点的估值计算出来后 再推算出父节点 的得分 倒推值 的得分 倒推值 获得较大的倒推值的方案 是最好的行动方案 20 3 3 3 剪枝技术 剪枝 剪枝 对于一个与节点MIN 若能估计出其倒推值 的上界 并且这个 值不大于 MIN的父节点 一定是或节点 的估计倒推值的下界 即 则就不必再扩展该 MI
14、N节点的其余子 节点了 因为这些节点的估值对MIN父节点 的倒推值已无任何影响了 21 3 3 3 剪枝技术 剪枝 剪枝 对于一个或节点MAX 若能估计出其倒推 值的下界 并且这个 值不小于 MAX的父 节点 一定是与节点 的估计倒推值的上界 即 则就不必再扩展该MAX节点的 其余子节点了 因为这些节点的估值对 MAX父节点的倒推值已无任何影响了 22 3 4 遗传算法 遗传算法的基本原理遗传算法的基本原理 编码与译码 适应度函数 遗传操作遗传操作 控制参数 23 3 4 2 遗传算法的结构 简单遗传算法的求解步骤 初始化群体 计算群体上每个个体的适应度值 计算群体上每个个体的适应度值 按由个
15、体适应度值所决定的某个规则选择 将进入下一代的个体 将进入下代的个体 按概率Pc进行交叉操作 按概率Pc进行突变操作 没有满足某种停止条件 则转第 步 否 没有满足某种停条件则转第 步否 则进入 输出种群中适应度值最优的染色体作为问 输出种群中适应度值最优的染色体作为问 题的满意解或最优解 24 3 4 3 遗传算法的性能 遗传算法性能的影响因素遗传算法性能的影响因素 种群的规模要适当 适应度函数的构造 交叉和变异操作交叉和变异操作 25 3 5 模拟退火算法 3 5 1 模拟退火算法的模型3 5 1 模拟退火算法的模型 解空间解 目标函数 初始解初始解 模拟退火的基本思想 模拟退火算法新解的
16、产生和接受的几个步骤 26 3 5 2 模拟退火算法的简单应用 旅行商问题旅行商问题 解空间 解空间S是遍访每个城市恰好一次的所有回 路 是 1 n 的所有循环排列的集合路是 的所有循环排列的集合 S中的成员记为 w1 w2 wn 并记 wn 1 w1 初始解可选为 1 n 初始解可选为 目标函数 此时的目标函数即为访问所有城市的路径总此时的目标函数即为访问所有城市的路径总 长度 或称为代价函数 27 3 5 2 模拟退火算法的简单应用 模拟退火算法求解TSP问题的伪程序 begin init of T T为初始温度 S 1 n S为初始值 iif ltermination false while termination false begin fi 1 t L dfor i 1 to L do begin generate S form S 从当前回路S产生新回路S t f S f S f S 为路径总长 t f S f S f S 为路径总长 IF tRandom of 0 1 S S IF the halt condition is TRUE THENIF the halt co
