AI(搜索策略2).pdf

4 1搜索的基本概念搜索的基本概念 4 24 2状态空间的盲目搜索状态空间的盲目搜索状态空间的盲目搜索状态空间的盲目搜索 4 3状态空间的启发式搜索状态空间的启发式搜索 4 4与与 或树的盲目搜索或树的盲目搜索 4 5与与 或树的启发式搜索或树的启发式搜索 4 6博弈树的启发式搜索博弈树的启发式搜索 第第4章 搜索策略章 搜索策略 4 2 状态空间的盲目搜索状态空间的盲目搜索 一 一般图搜索过程一 一般图搜索过程 二 广度优先和深度优先搜索二 广度优先和深度优先搜索 三 代价树搜索三 代价树搜索 1 状态空间搜索的基本思想1 状态空间搜索的基本思想 先把问题的初始状态作为当前扩展节点 对其进行先把问题的初始状态作为当前扩展节点 对其进行 扩展扩展 生成一组子节点 生成一组子节点 然后检查问题的目标状态是否出现在这些子节点中 若出现 则搜索成功 找到了问题的解 若没出现 然后检查问题的目标状态是否出现在这些子节点中 若出现 则搜索成功 找到了问题的解 若没出现 则再按照某种搜索策略 从已生成的子节点中选择一个 节点作为当前扩展节点 则再按照某种搜索策略 从已生成的子节点中选择一个 节点作为当前扩展节点 重复上述过程 直到目标状态出现在子节点中 或者 没有可供操作的节点为止 重复上述过程 直到目标状态出现在子节点中 或者 没有可供操作的节点为止 一 一般图搜索过程一 一般图搜索过程 2 算法的数据结构和符号约定2 算法的数据结构和符号约定 Open表表 用于存放刚生成的节点 用于存放刚生成的节点 Closed表表 用于存放已经扩展或将要扩展的节点 用于存放已经扩展或将要扩展的节点 S0 表示问题的初始状态 表示问题的初始状态 G 表示搜索过程所得到的搜索图 表示搜索过程所得到的搜索图 M 表示当前扩展节点新生成的 且不是自己先辈 的子节点集 表示当前扩展节点新生成的 且不是自己先辈 的子节点集 一 一般图搜索过程一 一般图搜索过程 3 一般图搜索过程3 一般图搜索过程 1 把初始节点把初始节点S0放入放入Open表 并建立目前仅包含表 并建立目前仅包含S0的图的图 G 2 检查检查Open表是否为空 若为空 则问题无解 失败退 出 表是否为空 若为空 则问题无解 失败退 出 3 把把Open表的第一个节点取出 放入表的第一个节点取出 放入Closed表 并记该节 点为节点 表 并记该节 点为节点n 4 考察节点考察节点n是否为目标节点 若是 则得到了问题的解 成功退出 是否为目标节点 若是 则得到了问题的解 成功退出 5 扩展节点扩展节点n 生成一组子节点 把这些子节点中不是节点 生成一组子节点 把这些子节点中不是节点 n先辈的那部分子节点记入集合先辈的那部分子节点记入集合M 并把这些子节点作为节 点 并把这些子节点作为节 点n的子节点加入的子节点加入G中 中 一 一般图搜索过程一 一般图搜索过程 6 针对针对M中子节点的不同情况 分别作如下处理 中子节点的不同情况 分别作如下处理 对那些没有在 对那些没有在G中出现过的中出现过的M成员设置一个指向其父 节点 即节点 成员设置一个指向其父 节点 即节点n 的指针 并把它放入 的指针 并把它放入Open表 表 对那些原来已在 对那些原来已在G中出现过 但还没有被扩展的中出现过 但还没有被扩展的M成 员 确定是否需要修改它指向父节点的指针 成 员 确定是否需要修改它指向父节点的指针 对于那些先前已在 对于那些先前已在G中出现过 并已经扩展了的中出现过 并已经扩展了的M成 员 确定是否需要修改其后继节点指向父节点的指针 成 员 确定是否需要修改其后继节点指向父节点的指针 7 按某种策略对按某种策略对Open表中的节点进行排序表中的节点进行排序 8 转第转第 2 步 检查步 检查Open表是否为空 表是否为空 一 一般图搜索过程一 一般图搜索过程 例如例如 一 一般图搜索过程一 一般图搜索过程 S 12 3 4 5 6 1 4 5 S 2 3 Open Closed S S 1 2 3 S 2 1 3 S 1 3 S 2 1 3 4 5 S 2 3 1 4 5 S 2 1 4 5 6 S 2 3 扩展S的子节点扩展S的子节点 按某种策略排序按某种策略排序 注意下列情形注意下列情形 对那些原来已在G中出现过 但还没有被扩展的M成员 确定是否需要修 改它指向父节点的指针 对那些原来已在G中出现过 但还没有被扩展的M成员 确定是否需要修 改它指向父节点的指针 对于那些先前已在G中出现过 并已经扩展了的M成员 确定是否需要 修改其后继节点指向父节点的指针 对于那些先前已在G中出现过 并已经扩展了的M成员 确定是否需要 修改其后继节点指向父节点的指针 一 一般图搜索过程一 一般图搜索过程 已扩展节点 末扩展节点 已扩展节点 末扩展节点 4 2 状态空间的盲目搜索状态空间的盲目搜索 一 一般图搜索过程一 一般图搜索过程 二 广度优先和深度优先搜索二 广度优先和深度优先搜索 三 代价树搜索三 代价树搜索 1 广度优先搜索 广度优先搜索 基本思想基本思想 从初始节点从初始节点S0开始 逐层向下扩展 在第开始 逐层向下扩展 在第n层节 点还没有全部搜索完之前 不进入第 层节 点还没有全部搜索完之前 不进入第n 1层节点的 搜索 层节点的 搜索 Open表中的节点总是按进入的先后排序 先 进入的节点排在前面 后进入的节点排在后面 表中的节点总是按进入的先后排序 先 进入的节点排在前面 后进入的节点排在后面 二 广度优先和深度优先搜索二 广度优先和深度优先搜索 搜索算法搜索算法 1 把初始节点把初始节点S0放入放入Open表中 表中 2 如果如果Open表为空 则问题无解 失败退出 表为空 则问题无解 失败退出 3 把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表 并记 该节点为 表 并记 该节点为n 4 考察节点考察节点n是否为目标节点 若是 则得到问题的 解 成功退出 是否为目标节点 若是 则得到问题的 解 成功退出 5 若节点若节点n不可扩展 则转第不可扩展 则转第 2 步 步 6 扩展节点扩展节点n 将其子节点放入 将其子节点放入Open表的尾部 并 为每一个子节点设置指向父节点的指针 表的尾部 并 为每一个子节点设置指向父节点的指针 然后转第 然后转第 2 步 步 二 广度优先和深度优先搜索二 广度优先和深度优先搜索 例例4 5 八数码难题 在八数码难题 在3 3的方格棋盘上 分别放置了标有 数字 的方格棋盘上 分别放置了标有 数字1 2 3 4 5 6 7 8的八张牌 初始状态的八张牌 初始状态S0 目标状 态 目标状 态Sg 如下图所示 可以使用的操作有 如下图所示 可以使用的操作有 空格左移 空格上移 空格右移 空格下移空格左移 空格上移 空格右移 空格下移 即只允许把位于空格左 上 右 下方的牌移入空格 要求 应用广度优先搜索策略 寻找从初始状态到目标状态的解路径 即只允许把位于空格左 上 右 下方的牌移入空格 要求 应用广度优先搜索策略 寻找从初始状态到目标状态的解路径 二 广度优先和深度优先搜索二 广度优先和深度优先搜索 28 3 1 4 7 6 5 1 2 3 8 4 7 6 5 S0Sg 6 7 8 9 10 11 12 13 2 8 3 1 4 7 6 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 2 8 3 1 6 4 7 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 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 S01 2 3 4 5 14 15 16 17 18 1920 21 22 23 24 25 26 27 Sg 二 广度优先和深度优先搜索二 广度优先和深度优先搜索 2 深度优先搜索 深度优先搜索 基本思想基本思想 从初始节点S从初始节点S0 0开始 在其子节点中选择一个最新 生成的节点进行考察 如果该子节点不是目标节点 且可以扩展 则扩展该子节点 开始 在其子节点中选择一个最新 生成的节点进行考察 如果该子节点不是目标节点 且可以扩展 则扩展该子节点 然后再在此子节点 的子节点中选择一个最新生成的节点进行考察 然后再在此子节点 的子节点中选择一个最新生成的节点进行考察 依 此向下搜索 直到某个子节点既不是目标节点 又 不能继续扩展时 才选择其兄弟节点进行考察 依 此向下搜索 直到某个子节点既不是目标节点 又 不能继续扩展时 才选择其兄弟节点进行考察 二 广度优先和深度优先搜索二 广度优先和深度优先搜索 算法描述算法描述 1 把初始节点 1 把初始节点S0放入放入Open表中 表中 2 如果如果Open表为空 则问题无解 失败退出 表为空 则问题无解 失败退出 3 把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表 并记 该节点为 表 并记 该节点为n 4 考察节点考察节点n是否为目标节点 若是 则得到问题 的解 成功退出 是否为目标节点 若是 则得到问题 的解 成功退出 5 若节点若节点n不可扩展 则转第不可扩展 则转第 2 步 步 6 扩展节点扩展节点n 将其子节点放入 将其子节点放入Open表的首部 并 为每一个子节点设置 指向父节点的指针 表的首部 并 为每一个子节点设置 指向父节点的指针 然后转第然后转第 2 步 步 深度优先搜索如图 深度优先搜索如图 有界深度优先搜索算法 即设定 一个深度限制 有界深度优先搜索算法 即设定 一个深度限制dm 例例4 6 八数码难题八数码难题 S01 2 8 3 1 4 7 6 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 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 6 7 5 4 2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4 2 8 1 6 3 7 5 4 2 3 4 5 6 4 2 状态空间的盲目搜索状态空间的盲目搜索 一 一般图搜索过程一 一般图搜索过程 二 广度优先和深度优先搜索二 广度优先和深度优先搜索 三 代价树搜索三 代价树搜索 在搜索树中给每条边标上其代价 称为代价树 在搜索树中给每条边标上其代价 称为代价树 在代价树中 在代价树中 g n 表示从初始节点 表示从初始节点S0到节点到节点n的代价的代价 c n1 n2 表示从父节点 表示从父节点n1到其子节点到其子节点n2的代价 则节点 的代价 则节点n2的代价为 的代价为 g n2 g n1 c n1 n2 代价树搜索的目的是为了找到最优解 即找到一条 代价最小的解路径 代价树搜索的目的是为了找到最优解 即找到一条 代价最小的解路径 三 代价树搜索三 代价树搜索 1 代价树的广度优先搜索算法 1 代价树的广度优先搜索算法 1 把初始节点把初始节点S0放入放入Open表中 置表中 置S0的代价的代价g S0 0 2 如果如果Open表为空 则问题无解 失败退出 表为空 则问题无解 失败退出 3 把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表 并记该节点为表 并记该节点为 n 4 考察节点考察节点n是否为目标 若是 则找到了问题的解 成功退 出 是否为目标 若是 则找到了问题的解 成功退 出 5 若节点若节点n不可扩展 则转第不可扩展 则转第 2 步 步 6 扩展节点扩展节点n 生成其子节点 生成其子节点ni i 1 2 将这些子节点放 入 将这些子节点放 入Open表中 表中 并为每一个子节点设置指向父节点的指针 按如下公式 并为每一个子节点设置指向父节点的指针 按如下公式 g ni g n c n ni i 1 2 计算各子结点的代价 并根据各子结点的代价对计算各子结点的代价 并根据各子结点的代价对Open表中的 全部结点按由小到大的顺序排序 然后转第 表中的 全部结点按由小到大的顺序排序 然后转第 2 步 步 三 代价树搜索三 代价树搜索 例例4 7 城市交通问题 设有5个城市 构成城市交通图 图中的数 字表示两个城市之间的交通费用 即代价 用代价树的广度优先搜 索 求从A市出发到E市 费用最小的交通路线 城市交通问题 设有5个城市 构成城市交通图 图中的数 字表示两个城市之间的交通费用 即代价 用代价树的广度优先搜 索 求从A市出发到E市 费用最小的交通路线 AB CD E 4 3 4 5 2 3 2 4 5 A C1 B1 D1D2 E1 E2 B2C2E3 E4 3 4 3 4 2 3 5 城市交通图城市交通图 解 解 代价树如右图所示 其中 红线为最优解 其代价为 代价树如右图所示 其中 红线为最优解 其代价为8 城市交通图的代价树城市交通图的代价树 三 代价树搜索三 代价树搜索 2 代价树的深度优先搜索算法2 代价树的深度优先搜索算法 1 把初始节点把初始节点S0放入放入Open表中 置表中 置S0的代价的代价g S0 0 2 如果如果Open表为空 则问题无解 失败退出 表为空 则问题无解 失败退出 3 把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表 并记该节点为表 并记该节点为 n 4 考察节点考察节点n是否为目标节点 若是 则找到了问题的解 成功退出 是否为目标节点 若是 则找到了问题的解 成功退出 5 若节点若节点n不可扩展 则转第不可扩展 则转第 2 步 步 6 扩展节点扩展节点n 生成其子节点 生成其子节点ni i 1 2 将这些子节点按 边代价由小到大放入 将这些子节点按 边代价由小到大放入Open表的首部 并为每一个子节点设置指 向父节点的指针 表的首部 并为每一个子节点设置指 向父节点的指针 然后转第然后转第 2 步 步 三 代价树搜索三 代价树搜索 4 1搜索的基本概念搜索的基本概念 4 2状态空间的盲目搜索状态空间的盲目搜索 4 34 3状态空间的启发式搜索状态空间的启发式搜索状态空间的启发式搜索状态空间的启发式搜索 4 4与与 或树的盲目搜索或树的盲目搜索 4 5与与 或树的启发式搜索或树的启发式搜索 4 6博弈树的启发式搜索博弈树的启发式搜索 第第4章 搜索策略章 搜索策略 4 3 状态空间的启发式搜索状态空间的启发式搜索 一 启发性信息和估价函数一 启发性信息和估价函数 二 二 A算法算法 三 三 A 算法算法 四 四 A 算法应用举例算法应用举例 1 启发性信息启发性信息 启发性信息的概念启发性信息的概念 启发性信息是指那种与具体问题求解过程有关的 并 可指导搜索过程朝着最有希望方向前进的控制信息 启发性信息是指那种与具体问题求解过程有关的 并 可指导搜索过程朝着最有希望方向前进的控制信息 启发性信息的种类启发性信息的种类 有效地帮助确定扩展节点的信息 有效地帮助确定扩展节点的信息 有效的帮助决定哪些后继节点应被生成的信息 有效的帮助决定哪些后继节点应被生成的信息 能决定在扩展一个节点时 哪些节点应从搜索树 上删除的信息 能决定在扩展一个节点时 哪些节点应从搜索树 上删除的信息 启发性信息的作用启发性信息的作用 启发信息的启发能力越强 扩展的无用结点越少 启发信息的启发能力越强 扩展的无用结点越少 一 启发性信息和估价函数一 启发性信息和估价函数 2 估价函数估价函数 估价函数估价函数f n 是用来估计节点重要性的函数 是用来估计节点重要性的函数 f n 的定义的定义 从初始节点从初始节点S0出发 约束经过节点出发 约束经过节点n 到达目标节点到达目标节点Sg的所有路径中最小路径代价的的所有路径中最小路径代价的估 计值 估 计值 f n 的一般形式为 的一般形式为 f n g n h n 其中 其中 g n 是从初始节点是从初始节点S0到节点到节点n的实际代价 的实际代价 h n 是从节点是从节点n到目标节点到目标节点Sg的最优路径的估计代 价 的最优路径的估计代 价 一 启发性信息和估价函数一 启发性信息和估价函数 例例4 8 八数码难题 八数码难题 设问题的初始状态设问题的初始状态S0和目标状 态 和目标状 态Sg如下图所示 且估价函数为如下图所示 且估价函数为 f n d n w n 其中 其中 d n 表示节点表示节点n在搜索树中的深度在搜索树中的深度 w n 表示节点表示节点n中中 不在位不在位 的数码个数 的数码个数 计算初始状态计算初始状态S0的估价函数值的估价函数值f S0 283 14 7 6 5 1 2 3 8 4 7 6 5 S0Sg 一 启发性信息和估价函数一 启发性信息和估价函数 解 解 取取g n d n 即用从S 即用从S0 0到到n的路径上的单位代价 表示实际代价 取 的路径上的单位代价 表示实际代价 取h n w n 即用结点 即用结点n中中 不在位不在位 的数码个数 作为启发信息 一般来说 某节点中的 的数码个数 作为启发信息 一般来说 某节点中的 不在位不在位 的 数码个数越多 说明它离目标节点越远 的 数码个数越多 说明它离目标节点越远 对初始节点对初始节点S0 d S0 0 w S0 3 因此有 因此有 f S0 0 3 3 一 启发性信息和估价函数一 启发性信息和估价函数 4 3 状态空间的启发式搜索状态空间的启发式搜索 一 启发性信息和估价函数一 启发性信息和估价函数 二 二 A算法算法 三 三 A 算法算法 四 四 A 算法应用举例算法应用举例 概念 概念 在图搜索算法中 如果能在搜索的每一步都利用估价函数在图搜索算法中 如果能在搜索的每一步都利用估价函数 f n g n h n 对Open表中的节点进行排序 则该搜索算法为A 算法 对Open表中的节点进行排序 则该搜索算法为A 算法 由于估价函数中带有问题自身的启发性信息 因此 A算 法也被称为启发式搜索算法 由于估价函数中带有问题自身的启发性信息 因此 A算 法也被称为启发式搜索算法 类型 类型 可根据搜索过程中选择扩展节点的范围 将启发式搜索算 法分为全局择优搜索算法和局部择优搜索算法 可根据搜索过程中选择扩展节点的范围 将启发式搜索算 法分为全局择优搜索算法和局部择优搜索算法 全局择优 全局择优 从Open表的所有节点中选择一个估价函数值 最小的一个进行扩展 从Open表的所有节点中选择一个估价函数值 最小的一个进行扩展 局部择优 局部择优 仅从刚生成的子节点中选择一个估价函数值最 小的一个进行扩展 仅从刚生成的子节点中选择一个估价函数值最 小的一个进行扩展 二 二 A算法算法 全局择优搜索A算法描述 全局择优搜索A算法描述 1 把初始节点把初始节点S0放入放入Open表中 表中 f S0 g S0 h S0 2 如果如果Open表为空 则问题无解 失败退出 表为空 则问题无解 失败退出 3 把把Open表的第一个节点取出放入表的第一个节点取出放入Closed表 并记该节点为表 并记该节点为n 4 考察节点考察节点n是否为目标节点 若是 则找到了问题的解 成功退 出 是否为目标节点 若是 则找到了问题的解 成功退 出 5 若节点若节点n不可扩展 则转第不可扩展 则转第 2 步 步 6 扩展节点扩展节点n 生成其子节点 生成其子节点ni i 1 2 计算每一个子节点的估 价值 计算每一个子节点的估 价值f ni i 1 2 并为每一个子节点设置指向父节点的指针 然后 将这些子节点放入 并为每一个子节点设置指向父节点的指针 然后 将这些子节点放入Open表中 表中 7 根据各节点的估价函数值 对根据各节点的估价函数值 对Open表中的全部节点按从小到大的 顺序重新进行排序 表中的全部节点按从小到大的 顺序重新进行排序 8 转第转第 2 步 步 二 二 A算法算法 例例4 9 八数码难题 设问题的初始状态八数码难题 设问题的初始状态S0和目标状态和目标状态Sg如 图所示 估价函数与例 如 图所示 估价函数与例4 8相同 用全局择优搜索解决该问题 相同 用全局择优搜索解决该问题 解 解 该问题的全局择优搜索树如下图所示 在该图中 每 个节点旁边的数字是该节点的估价函数值 例如 对节点 该问题的全局择优搜索树如下图所示 在该图中 每 个节点旁边的数字是该节点的估价函数值 例如 对节点S2 其估价函数值的计算为 其估价函数值的计算为 f S2 d S2 w S2 1 3 4 2 83 1 4 7 6 5 1 2 3 8 4 7 6 5 S0Sg 二 二 A算法算法 八数码难题的全局择优搜索树 该问题的解为 八数码难题的全局择优搜索树 该问题的解为 S0 S1 S2 S3 Sg 2 8 3 14 7 6 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 2 8 3 1 6 4 7 5 S0 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 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 1 2 3 84 7 6 5 4 4 5 5 5 6 4 6 4 4 Sg S1 S2 S3 6 二 二 A算法算法 4 3 状态空间的启发式搜索状态空间的启发式搜索 一 启发性信息和估价函数一 启发性信息和估价函数 二 二 A算法算法 三 三 A 算法算法 四 四 A 算法应用举例算法应用举例 A 算法是对算法是对A算法的估价函数算法的估价函数f n g n h n 加上某些限制后 得到的一种启发式搜索算法 加上某些限制后 得到的一种启发式搜索算法 假设假设f n 是从初始节点出发 约束经过节点是从初始节点出发 约束经过节点n达到目标节点的 最小代价 估价函数 达到目标节点的 最小代价 估价函数f n 是对是对f n 的估计值 且的估计值 且 f n g n h n A 算法对算法对A算法 全局择优的启发式搜索算法 中的算法 全局择优的启发式搜索算法 中的g n 和和 h n 分别提出如下限制 第一 分别提出如下限制 第一 g n 是对最小代价是对最小代价g n 的估计 且的估计 且g n 0 第二 第二 h n 是最小代价是最小代价h n 的下界 即对任意节点的下界 即对任意节点n均有均有 h n h n 满足上述两条限制的 满足上述两条限制的A算法称为算法称为A 算法 算法 三 三 A 算法算法 A 算法的性质算法的性质 A 算法的性质算法的性质 1 A 算法的可纳性算法的可纳性 2 A 算法的最优性算法的最优性 3 h n 的单调性限制的单调性限制 三 三 A 算法算法 1 A 算法的可纳性算法的可纳性 可纳性的含义 可纳性的含义 对任一状态空间图 当从初始节点到目标节点有 路经存在时 如果搜索算法总能在有限步内找到 一条从初始节点到目标节点的最佳路径 并在此 路径上结束 则称该搜索算法是可采纳的 对任一状态空间图 当从初始节点到目标节点有 路经存在时 如果搜索算法总能在有限步内找到 一条从初始节点到目标节点的最佳路径 并在此 路径上结束 则称该搜索算法是可采纳的 三 三 A 算法算法 定理4 3定理4 3A A 算法是可采纳的 即若存在从初始节点 S 算法是可采纳的 即若存在从初始节点 S0 0到目标节点S到目标节点Sg g的路径 则A的路径 则A 算法必能结束在最佳 路径上 算法必能结束在最佳 路径上 定理说明两个问题 1 A 定理说明两个问题 1 A 算法一定能够终止在某个目标节点上 2 A 算法一定能够终止在某个目标节点上 2 A 算法只能终止在最佳路径上 算法只能终止在最佳路径上 三 三 A 算法算法 2 A 算法的最优性算法的最优性 A 算法的搜索效率很大程度上取决于估价函数算法的搜索效率很大程度上取决于估价函数 h n 一般来说 在满足 一般来说 在满足h n h n 的前提下 的前提下 h n 的值越大越好 的值越大越好 h n 的值越大 说明它携带的启发性 信息越多 的值越大 说明它携带的启发性 信息越多 A 算法搜索时扩展的节点就越少 搜索 效率就越高 算法搜索时扩展的节点就越少 搜索 效率就越高 三 三 A 算法算法 定理定理4 4 设有两个设有两个A 算法算法A1 和和A2 它们有 它们有 A1 f1 n g1 n h1 n A2 f2 n g2 n h2 n 如果如果A2 比比A1 有更多的启发性信息 即对所有非目标 节点均有 有更多的启发性信息 即对所有非目标 节点均有 h2 n h1 n 则在搜索过程中 被则在搜索过程中 被A2 扩展的节点也必然被扩展的节点也必然被A1 扩 展 即 扩 展 即A1 扩展的节点不会比扩展的节点不会比A2 扩展的节点少 亦即扩展的节点少 亦即 A2 扩展的节点集是扩展的节点集是A1 扩展的节点集的子集 扩展的节点集的子集 三 三 A 算法算法 3 h n 的单调限制的单调限制 在在A 算法中 每当扩展一个节点算法中 每当扩展一个节点n时 都需要检查其子节点 是否已在 时 都需要检查其子节点 是否已在Open表或表或Closed表中 对已在 表中 对已在Open表中的子节点 需要决定是否调整指向其父节 点的指针 对已在 表中的子节点 需要决定是否调整指向其父节 点的指针 对已在Closed表中的子节点 除需要决定是否调整其指向父 节点的指针外 还需要决定是否调整其子节点的后继节点的父 指针 如果能够保证 每当扩展一个节点时就已经找到了通往这 个节点的最佳路径 就没有必要再去作上述检查 表中的子节点 除需要决定是否调整其指向父 节点的指针外 还需要决定是否调整其子节点的后继节点的父 指针 如果能够保证 每当扩展一个节点时就已经找到了通往这 个节点的最佳路径 就没有必要再去作上述检查 三 三 A 算法算法 为满足这一要求 我们需要对启发函数为满足这一要求 我们需要对启发函数h n 增加 单调性限制 增加 单调性限制 定义定义4 1 如果启发函数满足以下两个条件如果启发函数满足以下两个条件 1 h Sg 0 2 对任意节点对任意节点ni及其任一子节点及其任一子节点nj 都有 都有 0 h ni h nj c ni nj 其中其中c ni nj 是是ni到其子节点到其子节点nj的边代价 则称的边代价 则称h n 满 足单调限制 满 足单调限制 三 三 A 算法算法 定理定理4 5 如果如果h满足单调条件 则当满足单调条件 则当A 算法扩展节点算法扩展节点n时 该节 点就已经找到了通往它的最佳路径 即 时 该节 点就已经找到了通往它的最佳路径 即g n g n 定理定理4 6 如果如果h n 满足单调限制 则满足单调限制 则A 算法扩展的节点序列的算法扩展的节点序列的f 值是非递减的 即值是非递减的 即f ni f ni 1 1 以上两个定理都是在以上两个定理都是在h n 满足单调性限制的前提下才成立 的 如果 满足单调性限制的前提下才成立 的 如果h n 不满足单调性限制 则它们不一定成立 不满足单调性限制 则它们不一定成立 在在h n 满足单调性限制下的满足单调性限制下的A 算法常被称为算法常被称为改进的改进的A 算法算法 三 三 A 算法算法 4 3 状态空间的启发式搜索状态空间的启发式搜索 一 启发性信息和估价函数一 启发性信息和估价函数 二 二 A算法算法 三 三 A 算法算法 四 四 A 算法应用举例算法应用举例 例例4 10 八数码难题 八数码难题 A 算法一算法一 f n d n w n d n 深度 深度 w n 不在位不在位 数码个数数码个数 如上图如上图w n 3 因为因为w n h n 故为故为A 算法算法 四 四 A 算法应用举例算法应用举例 A 算法二算法二 f n d n P n d n 深度 深度 P n 与目标位置之间的距离 与目标位置之间的距离 如上图如上图p n 4 因为因为p n h n 故也为故也为A 算法算法 2 83 1 4 7 6 5 1 2 3 8 4 7 6 5 八数码难题八数码难题h n P n 的搜索树 的搜索树 f n d n P n d n 深度 深度 P n 与目标距离 与目标距离 f g h 注意 注意 h n 满足单 调性 满足单 调性 f非递减非递减 四 四 A 算法应用举例算法应用举例 2 8 3 1 4 7 6 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 2 8 3 1 6 4 7 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 1 2 3 84 7 6 5 S0 f 6 g 1 h 3f 6 f 6 g 2 h 2f 6 f 4 g 3 h 1 f 4 g 4 h 0 f 4 f 6 Sg f 4 h 4 f 4 例例4 11 修道士和野人问题修道士和野人问题 M C问题 问题 可与例可与例4 2一起考虑 一起考虑 四 四 A 算法应用举例算法应用举例 思考题思考题 一 教材一 教材P131习题习题4 4 5 二 教材二 教材P131习题习题4 4 7 三 教材三 教材P131习题习题4 4 8 注 此问题又称为旅行商问题 注 此问题又称为旅行商问题 travelling salesman problem TSP 或货郎担问题 是一个较有 普遍性的实际应用问题 或货郎担问题 是一个较有 普遍性的实际应用问题 参考答案参考答案 一 解 一 解 1 定义问题的描述形式定义问题的描述形式 用四元组用四元组S f w s v 表示问题状态 其中 表示问题状态 其中 f w s和和v分别 表示农夫 狼 羊和青菜是否在左岸 取值 分别 表示农夫 狼 羊和青菜是否在左岸 取值0或或1 取 取0表示在左岸 取表示在左岸 取1 表示在右岸 表示在右岸 2 用所定义的问题状态表示方式 把所有可能的问题状态表示出来 包 括问题的初始状态和目标状态 用所定义的问题状态表示方式 把所有可能的问题状态表示出来 包 括问题的初始状态和目标状态 由于状态变量有由于状态变量有4个 每个状态变量都有个 每个状态变量都有2种取值 因此有以下种取值 因此有以下16种可能 的状态 种可能 的状态 S0 0 0 0 0 S1 0 0 0 1 S2 0 0 1 0 S3 0 0 1 1 S4 0 1 0 0 S5 0 1 0 1 S6 0 1 1 0 S7 0 1 1 1 S8 1 0 0 0 S9 1 0 0 1 S10 1 0 1 0 S11 1 0 1 1 S12 1 1 0 0 S13 1 1 0 1 S14 1 1 1 0 S15 1 1 1 1 其中 其中 S0和和S15分别是初始状态和目标状态分别是初始状态和目标状态 注意 哪些状态是不合法状态 例如注意 哪些状态是不合法状态 例如S3 0 0 1 1 3 定义操作 由于每次过河船上都必须有农夫 且除农夫外船上只能 载狼 羊和菜中的一种 故操作定义如下 定义操作 由于每次过河船上都必须有农夫 且除农夫外船上只能 载狼 羊和菜中的一种 故操作定义如下