《图搜索技术》PPT课件

《《图搜索技术》PPT课件》由会员分享，可在线阅读，更多相关《《图搜索技术》PPT课件（63页珍藏版）》请在装配图网上搜索。

1、1李 伟 生信 科 大 厦 19楼Tel： 2 内 容 提 要 : 8.1 状 态 图 搜 索 策 略 8.2 启 发 式 搜 索 8.3 与 或 图 搜 索 8.4 博 弈 树 搜 索 3 l迷 宫 问 题 ： 把 迷 宫 每 一 个 位 置 以 及 入 口 和 出 口 都 作 为 节 点 ， 把 通 道作 为 边 ， 则 迷 宫 可 由 一 个 有 向 图 表 示 。 走 迷 宫 实 际 就 是 从 该 有 向 图的 初 始 节 点 （ 入 口 ） 出 发 ， 寻 找 目 标 节 点 （ 出 口 ） 的 问 题 ， 或 者 是寻 找 通 向 目 标 节 点 （ 出 口 ） 的 路 径 的

2、问 题 。l8数 码 问 题 ： 在 一 个 3*3的 方 格 棋 盘 上 放 置 着 1， 2， 3， 4， 5， 6， 7，8八 个 数 码 ， 每 个 数 码 占 一 格 ， 且 有 一 个 空 格 。 这 些 数 码 可 在 棋 盘 上移 动 ， 其 移 动 规 则 是 ： 与 空 格 相 邻 的 数 码 才 可 以 移 入 空 格 。 问 题 ：对 于 指 定 的 初 始 棋 局 和 目 标 棋 局 ， 给 出 数 码 的 移 动 序 列 。 如 果 把 一 个 棋 局 作 为 一 个 节 点 ， 相 邻 的 节 点 就 可 以 通 过 移 动 数 码 ，一 个 一 个 地 产 生

3、出 来 。 这 样 ， 所 有 节 点 就 可 由 它 们 相 邻 的 关 系 连 成一 个 有 向 图 ， 图 中 的 一 条 边 就 对 应 一 次 数 码 移 动 ， 反 之 ， 一 次 数 码移 动 就 对 应 着 图 中 的 一 条 边 ， 边 也 就 代 表 着 一 个 移 动 规 则 或 者 移 动规 则 的 一 次 执 行 。 该 问 题 也 就 是 要 在 该 有 向 图 中 寻 找 目 标 节 点 ， 或找 一 条 从 初 始 节 点 到 目 标 节 点 的 路 径 问 题 。 4 l上 述 两 个 问 题 虽 然 内 容 不 同 ， 但 抽 象 地 看 ， 它 们 都 是

4、 在 某 个 有 向 图中 寻 找 目 标 或 路 径 的 问 题 。 我 们 把 这 种 描 述 问 题 的 有 向 图 称 为 状 态空 间 图 ， 简 称 状 态 图 。 5 8.1.1 图 搜 索 策 略 的 定 义 8.1.2 图 搜 索 算 法 中 的 几 个 重 要 名 词 术 语 8.1.3 图 搜 索 (GRAPH SEARCH)的 一 般 过 程 8.1.4 图 搜 索 方 法 分 析 6 l 图 搜 索 策 略 可 看 作 一 种 在 图 中 寻 找 路 径 的 方 法 。 初 始节 点 和 目 标 节 点 分 别 代 表 初 始 数 据 库 和 满 足 终 止 条 件的

5、 数 据 库 。 求 得 把 一 个 数 据 库 变 换 为 另 一 数 据 库 的 规则 序 列 问 题 就 等 价 于 求 得 图 中 的 一 条 路 径 问 题 。l 研 究 图 搜 索 的 一 般 策 略 ， 能 够 给 出 图 搜 索 过 程 的 一 般步 骤 。 7 l （ 1） OPEN表 与 CLOSED表l （ 2） 搜 索 (状 态 )图 与 搜 索 树 登 记 当 前待 考 查 的节 点 记 录 考 查过 的 节 点父 节 点 编 号节 点 编 号 父 节 点 编 号节 点OPEN CLOSED 8 (1) 建 立 一 个 只 含 有 起 始 节 点 S的 搜 索 图 G

6、， 把 S放 到 一 个 叫 做OPEN的 未 扩 展 节 点 表 中 。(2) 建 立 一 个 叫 做 CLOSED的 已 扩 展 节 点 表 ， 其 初 始 为 空 表 。(3) LOOP： 若 OPEN表 是 空 表 ， 则 失 败 退 出 。(4) 选 择 OPEN表 上 的 第 一 个 节 点 ， 把 它 从 OPEN表 移 出 并 放 进CLOSED表 中 。 称 此 节 点 为 节 点 n。(5) 若 n为 一 目 标 节 点 ， 则 有 解 并 成 功 退 出 ， 此 解 是 追 踪 图 G中沿 着 指 针 从 n到 S这 条 路 径 而 得 到 的 (指 针 将 在 第 7步

7、 中 设 置 )。(6) 扩 展 节 点 n， 同 时 生 成 不 是 n的 祖 先 的 那 些 后 继 节 点 的 集 合M。 把 M的 这 些 成 员 作 为 n的 后 继 节 点 添 入 图 G中 。 9 (7) 对 那 些 未 曾 在 G中 出 现 过 的 (既 未 曾 在 OPEN表 上 或 CLOSED表 上 出 现 过 的 )M成 员 设 置 一 个 通 向 n的 指 针 。 把 M的 这 些 成 员加 进 OPEN表 。 对 已 经 在 OPEN或 CLOSED表 上 的 每 一 个 M成 员 ，确 定 是 否 需 要 更 改 通 到 n的 指 针 方 向 。 对 已 在 CL

8、OSED表 上 的每 个 M成 员 ， 确 定 是 否 需 要 更 改 图 G中 通 向 它 的 每 个 后 裔 节 点的 指 针 方 向 。(8) 按 某 一 或 按 某 个 探 试 值 ， 重 排 OPEN表 。(9) GO LOOP。 10 开 始把 S放 入 OPEN表把 第 一 个 节 点 (n)从 OPEN移 至 CLOSE表OPEN为 空 表 n为 目 标 节 点把 n的 后 继 节 点 放 入 OPEN表 的 末 端 ，提 供 返 回 节 点 的 指 针修 改 指 针 方 向 重 排 OPEN表 失 败成 功 11 图 搜 索 过 程 的 第 8步 （ 按 某 一 方 式 重

9、排 OPEN表 ） 对 OPEN表 上 的 节 点 进行 排 序 ， 以 便 能 够 从 中 选 出 一 个 “ 最 好 ” 的 节 点 作 为 第 4步 扩 展 用 。 这 种排 序 可 以 是 任 意 的 即 盲 目 的 (属 于 盲 目 搜 索 )， 也 可 以 用 以 后 要 讨 论 的 各 种启 发 思 想 或 其 它 准 则 为 依 据 (属 于 启 发 式 搜 索 )。 每 当 被 选 作 扩 展 的 节 点 为目 标 节 点 时 ， 这 一 过 程 就 宣 告 成 功 结 束 。 这 时 ， 能 够 重 现 从 起 始 节 点 到目 标 节 点 的 这 条 成 功 路 径 ，

10、其 办 法 是 从 目 标 节 点 按 指 针 向 S返 回 追 溯 。 当搜 索 树 不 再 剩 有 未 被 扩 展 的 端 节 点 时 ， 过 程 就 以 失 败 告 终 (某 些 节 点 最 终可 能 没 有 后 继 节 点 ， 所 以 OPEN表 可 能 最 后 变 成 空 表 )。 在 失 败 终 止 的 情况 下 ， 从 起 始 节 点 出 发 ， 一 定 达 不 到 目 标 节 点 。 1. 宽 度 优 先 搜 索2. 深 度 优 先 搜 索 12 1)定 义 如 果 搜 索 是 以 接 近 起 始 节 点 的 程 度 依 次 扩 展 节点 的 ， 那 么 这 种 搜 索 就 叫

11、 做 宽 度 优 先 搜 索 。 (breadth-first search) 2)特 点 这 种 搜 索 是 逐 层 进 行 的 ； 在 对 下 一 层 的 任 一 节点 进 行 搜 索 之 前 ， 必 须 搜 索 完 本 层 的 所 有 节 点 。 13 3)宽 度 优 先 搜 索 算 法 (1) 把 起 始 节 点 放 到 OPEN表 中 (如 果 该 起 始 节 点 为 一 目 标 节 点 ， 则 求 得一 个 解 答 )。 (2) 如 果 OPEN是 个 空 表 ， 则 没 有 解 ， 失 败 退 出 ； 否 则 继 续 。 (3) 把 第 一 个 节 点 (节 点 n)从 OPEN

12、表 移 出 ， 并 把 它 放 入 CLOSED的 扩 展节 点 表 中 。 (4) 扩 展 节 点 n。 如 果 没 有 后 继 节 点 ， 则 转 向 上 述 第 (2)步 。 (5) 把 n的 所 有 后 继 节 点 放 到 OPEN表 的 末 端 ， 并 提 供 从 这 些 后 继 节 点 回到 n的 指 针 。 (6) 如 果 n的 任 一 个 后 继 节 点 是 个 目 标 节 点 ， 则 找 到 一 个 解 答 ， 成 功 退 出； 否 则 转 向 第 (2)步 。 14 (1) 把 起 始 节 点 放 到 OPEN表 中(如 果 该 起 始 节 点 为 一 目 标 节点 ， 则

13、 求 得 一 个 解 答 )。(2) 如 果 OPEN是 个 空 表 ， 则 没有 解 ， 失 败 退 出 ； 否 则 继 续 。(3) 把 第 一 个 节 点 (节 点 n)从OPEN表 移 出 ， 并 把 它 放 入CLOSED的 扩 展 节 点 表 中 。(4) 扩 展 节 点 n。 如 果 没 有 后 继节 点 ， 则 转 向 上 述 第 (2)步 。(5) 把 n的 所 有 后 继 节 点 放 到OPEN表 的 末 端 ， 并 提 供 从 这些 后 继 节 点 回 到 n的 指 针 。(6) 如 果 n的 任 一 个 后 继 节 点 是个 目 标 节 点 ， 则 找 到 一 个 解

14、答 ， 成 功 退 出 ； 否 则 转 向 第 (2)步。 15 4)宽 度 优 先 搜 索 方 法 分 析 ： 宽 度 优 先 搜 索 是 图 搜 索 一 般 过 程 的 特 殊 情 况 ， 将 图 搜 索 一般 过 程 中 的 第 8步 具 体 化 为 本 算 法 中 的 第 6步 ， 这 实 际 是 将OPEN表 作 为 “ 先 进 先 出 ” 的 队 列 进 行 操 作 。 宽 度 优 先 搜 索 方 法 能 够 保 证 在 搜 索 树 中 找 到 一 条 通 向 目 标节 点 的 最 短 途 径 ； 这 棵 搜 索 树 提 供 了 所 有 存 在 的 路 径 (如 果 没有 路 径

15、存 在 ， 那 么 对 有 限 图 来 说 ， 我 们 就 说 该 法 失 败 退 出 ；对 于 无 限 图 来 说 ， 则 永 远 不 会 终 止 )。 16 5)例 ： 八 数 码 难 题把 宽 度 优 先 搜 索 应 用 于 八 数 码 难 题 时 所 生 成 的 搜 索 树 ， 这 个问 题 就 是 要 把 初 始 棋 局 变 为 如 下 目 标 棋 局 的 问 题 ：2 8 31 47 6 5 1 2 38 47 6 5 17 2 8 31 47 6 5 1 2 38 47 6 52 8 3 1 47 6 5 2 31 8 47 6 5 2 8 31 6 47 5 2 8 31 47

16、 6 5 8 32 1 47 6 5 2 8 37 1 4 6 5 2 31 8 47 6 5 2 31 8 47 6 5 2 8 31 6 4 7 5 2 8 31 6 47 5 2 81 4 37 6 5 2 8 31 4 57 68 32 1 47 6 5 2 8 37 1 46 5 1 2 3 8 47 6 5 2 3 41 8 7 6 5 2 8 3 6 41 7 5 2 8 31 67 5 4 2 81 4 37 6 5 2 8 31 4 57 68 32 1 47 6 5 8 1 32 47 6 5 2 8 37 46 1 5 2 8 37 1 46 5 1 2 37 8 4 6

17、 5 18 1)定 义 在 此 搜 索 中 ， 首 先 扩 展 最 新 产 生 的 (即 最 深 的 )节 点 。 深度 相 等 的 节 点 可 以 任 意 排 列 。 这 种 盲 目 (无 信 息 )搜 索 叫 做 深 度 优 先 搜 索 (depth-first search)。2)特 点 首 先 ， 扩 展 最 深 的 节 点 的 结 果 使 得 搜 索 沿 着 状 态 空 间某 条 单 一 的 路 径 从 起 始 节 点 向 下 进 行 下 去 ； 只 有 当 搜 索 到达 一 个 没 有 后 裔 的 状 态 时 ， 它 才 考 虑 另 一 条 替 代 的 路 径 。 19 3)深 度

18、 界 限 为 了 避 免 考 虑 太 长 的 路 径 (防 止 搜 索 过 程 沿 着 无 益 的 路 径扩 展 下 去 )， 往 往 给 出 一 个 节 点 扩 展 的 最 大 深 度 棗 深 度 界 限 。任 何 节 点 如 果 达 到 了 深 度 界 限 ， 那 么 都 将 把 它 们 作 为 没 有 后继 节 点 处 理 。4)含 有 深 度 界 限 的 深 度 优 先 搜 索 算 法 请 课 后 自 学 。 20 1.为 什 么 需 要 启 发 式 搜 索 盲 目 搜 索 效 率 低 ， 耗 费 过 多 的 计 算 空 间 与 时 间 ， 这 是组 合 爆 炸 的 一 种 表 现 形

19、 式 。2.定 义 进 行 搜 索 技 术 一 般 需 要 某 些 有 关 具 体 问 题 领 域 的 特 性的 信 息 ， 把 此 种 信 息 叫 做 启 发 信 息 。 利 用 启 发 信 息 的搜 索 方 法 叫 做 启 发 式 搜 索 方 法 。 21 3.启 发 式 搜 索 策 略 有 关 具 体 问 题 领 域 的 信 息 常 常 可 以 用 来 简 化 搜 索 。一 个 比 较 灵 活 (但 代 价 也 较 大 )的 利 用 启 发 信 息 的 方 法 是 应用 某 些 准 则 来 重 新 排 列 每 一 步 OPEN表 中 所 有 节 点 的 顺 序。 然 后 ， 搜 索 就

20、可 能 沿 着 某 个 被 认 为 是 最 有 希 望 的 边 缘 区段 向 外 扩 展 。应 用 这 种 排 序 过 程 ， 需 要 某 些 估 算 节 点 “ 希 望 ” 的 量 度 ，这 种 量 度 叫 做 估 价 函 数 (evalution function)。 22 4.估 价 函 数 为 获 得 某 些 节 点 “ 希 望 ” 的 启 发 信 息 ， 提 供 一 个 评 定 侯 选扩 展 节 点 的 方 法 ， 以 便 确 定 哪 个 节 点 最 有 可 能 在 通 向 目 标 的 最佳 路 径 上 。 f(n)表 示 节 点 n的 估 价 函 数 值 建 立 估 价 函 数 的

21、 一 般 方 法 ： 试 图 确 定 一 个 处 在 最 佳 路 径 上的 节 点 的 概 率 ； 提 出 任 意 节 点 与 目 标 集 之 间 的 距 离 量 度 或 差 别量 度 ； 或 者 在 棋 盘 式 的 博 弈 和 难 题 中 根 据 棋 局 的 某 些 特 点 来 决定 棋 局 的 得 分 数 。 这 些 特 点 被 认 为 与 向 目 标 节 点 前 进 一 步 的 希望 程 度 有 关 。 23 1、 定 义 用 估 价 函 数 f来 排 列 GRAPHSEARCH第 8步 中 OPEN表 上的 节 点 。 应 用 某 个 算 法 选 择 OPEN表 上 具 有 最 小 f

22、值 的 节 点 作为 下 一 个 要 扩 展 的 节 点 。 这 种 搜 索 方 法 叫 做 有 序 搜 索(ordered search)或 最 佳 优 先 搜 索 best-first search)， 而 其 算 法就 叫 做 有 序 搜 索 算 法 或 最 佳 优 先 算 法 。 尼 尔 逊 (Nilsson)曾 提 出 一 个 有 序 搜 索 的 基 本 算 法 。 估 价函 数 f是 这 样 确 定 的 ： 一 个 节 点 的 希 望 程 序 越 大 ， 其 f值 就 越小 。 被 选 为 扩 展 的 节 点 ， 是 估 价 函 数 最 小 的 节 点 。 24 2、 实 质l 选

23、 择 OPEN表 上 具 有 最 小 f值 的 节 点 作 为 下一 个 要 扩 展 的 节 点 ， 即 总 是 选 择 最 有 希 望 的 节点 作 为 下 一 个 要 扩 展 的 节 点 。 25 3、 有 序 状 态 空 间 搜 索 算 法 (1) 把 起 始 节 点 S放 到 OPEN表 中 ， 计 算 f(S)并 把 其 值 与 节 点 S联 系 起 来 。 (2) 如 果 OPEN是 个 空 表 ， 则 失 败 退 出 ， 无 解 。 (3) 从 OPEN表 中 选 择 一 个 f值 最 小 的 节 点 i。 结 果 有 几 个 节 点合 格 ， 当 其 中 有 一 个 为 目 标

24、 节 点 时 ， 则 选 择 此 目 标 节 点 ， 否则 就 选 择 其 中 任 一 个 节 点 作 为 节 点 i. (4) 把 节 点 i从 OPEN表 中 移 出 ， 并 把 它 放 入 CLOSED的 扩 展节 点 表 中 。 (5) 如 果 i是 个 目 标 节 点 ， 则 成 功 退 出 ， 求 得 一 个 解 。 (6) 扩 展 节 点 i， 生 成 其 全 部 后 继 节 点 。 对 于 i的 每 一 个 后 继节 点 j： 26 (6) 扩 展 节 点 i， 生 成 其 全 部 后 继 节 点 。 对 于 i的 每 一 个 后 继 节点 j： (a)计 算 f(j)。 (b

25、)如 果 j既 不 在 OPEN表 中 ， 又 不 在 CLOSED表 中 ， 则 用 估价 函 数 f把 它 添 入 OPEN表 。 从 j加 一 指 向 其 父 辈 节 点 i的 指 针， 以 便 一 旦 找 到 目 标 节 点 时 记 住 一 个 解 答 路 径 。 (c)如 果 j已 在 OPEN表 上 或 CLOSED表 上 ， 则 比 较 刚 刚 对 j计 算 过 的 f值 和 前 面 计 算 过 的 该 节 点 在 表 中 的 f值 。 如 果 新 的 f值 较 小 ， 则 (i) 以 此 新 值 取 代 旧 值 。 (ii) 从 j指 向 i， 而 不 是 指 向 它 的 父

26、辈 节 点 。 (iii) 如 果 节 点 j在 CLOSED表 中 ， 则 把 它 移 回 OPEN表(7) 转 向 (2)， 即 GO TO(2)。 27 4、 有 序 搜 索 方 法 分 析 宽 度 优 先 搜 索 和 深 度 优 先 搜 索 统 统 是 有 序 搜 索 技 术 的 特例 。 有 序 搜 索 的 有 效 性 直 接 取 决 于 f的 选 择 ， 如 果 选 择 的 f不合 适 ， 有 序 搜 索 就 可 能 失 去 一 个 最 好 的 解 甚 至 全 部 的 解 。如 果 没 有 适 用 的 准 确 的 希 望 量 度 ， 那 么 f的 选 择 将 涉 及 两 个 方面

27、的 内 容 ： 一 方 面 是 一 个 时 间 和 空 间 之 间 的 折 衷 方 案 ； 另 一方 面 是 保 证 有 一 个 最 优 的 解 或 任 意 解 。 28 5、 例 ： 八 数 码 难 题 采 用 了 简 单 的 估 价 函 数 f(n)=d(n)+W(n) 其 中 ： d(n)是 搜 索 树 中 节 点 n的 深 度 ； W(n)用 来 计 算 对 应于 节 点 n的 数 据 库 中 错 放 的 棋 子 个 数 。 因 此 ， 起 始 节 点 棋 局2 8 31 6 47 5的 f值 等 于 0+4=4。 1 2 38 47 6 5 29 八 数 码 难 题的 有 序 搜 索

28、 树 2 8 31 6 47 5 1 2 38 47 6 52 8 31 6 4 7 5 2 8 31 47 6 5 2 8 31 6 47 52 8 3 1 47 6 5 2 31 8 47 6 5 2 8 31 47 6 5 8 32 1 47 6 5 2 8 37 1 4 6 5 2 31 8 47 6 5 2 31 8 47 6 51 2 37 8 4 6 51 2 3 8 47 6 5 30 l A*算 法 是 一 种 有 序 搜 索 算 法 ， 其 特 点 在 于 对 估 价 函 数的 定 义 上 。 31 1、 几 个 记 号 令 k(ni， nj)表 示 任 意 两 个 节 点

29、 ni和 nj之 间 最 小 代 价 路 径 的实 际 代 价 (对 于 两 节 点 间 没 有 通 路 的 节 点 ， 函 数 k没 有 定 义 )。 于 是 ， 从 节 点 n到 某 个 具 体 的 目 标 节 点 ti， 某 一 条 最 小 代价 路 径 的 代 价 可 由 k(n,ti)给 出 。 令 h*(n)表 示 整 个 目 标 节 点 集 合 ti 上 所 有 k(n,ti)中 最 小的 一 个 ， 因 此 ， h*(n)就 是 从 n到 目 标 节 点 最 小 代 价 路 径 的 代价 ， 而 且 从 n到 目 标 节 点 能 够 获 得 h*(n)的 任 一 路 径 就 是

30、 一 条从 n到 某 个 目 标 节 点 的 最 佳 路 径 (对 于 任 何 不 能 到 达 目 标 节 点的 节 点 n， 函 数 h*没 有 定 义 )。 32 2、 估 价 函 数 的 定 义 定 义 g*为 g*(n)=k(S,n) 定 义 函 数 f*， 使 得 在 任 一 节 点 n上 其 函 数 值 f*(n)就 是 从节 点 S到 节 点 n的 一 条 最 佳 路 径 的 实 际 代 价 加 上 从 节 点 n到某 目 标 节 点 的 一 条 最 佳 路 径 的 代 价 之 和 ， 即f*(n)=g*(n)+h*(n) 33 希 望 估 价 函 数 f是 f*的 一 个 估

31、计 ， 此 估 计 可 由 下 式 给 出 ：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)依 赖

32、于 有 关 问 题 的 领 域 的 启 发 信 息 。 这 种 信 息 可 能 与 八数 码 难 题 中 的 函 数 W(n)所 用 的 那 种 信 息 相 似 。 把 h叫 做 启 发函 数 。 34 3、 A*算 法 定 义 定 义 1 在 GRAPHSEARCH过 程 中 ， 如 果 第 8步 的 重 排 OPEN表是 依 据 f(x)=g(x)+h(x) 进 行 的 ， 则 称 该 过 程 为 A算 法 。定 义 2 在 A算 法 中 ， 如 果 对 所 有 的 x存 在 h(x)h*(x),则 称 h(x)为h*(x)的 下 界 ， 它 表 示 某 种 偏 于 保 守 的 估 计 。

33、定 义 3 采 用 h*(x)的 下 界 h(x)为 启 发 函 数 的 A算 法 ， 称 为 A*算法 。 当 h=0时 ， A*算 法 就 变 为 有 序 搜 索 算 法 。 35 状 态 图 搜 索 策 略 小 结 树 式 搜 索 穷 举 式盲 目 搜 索启 发 式 搜 索 宽 度 优 先深 度 优 先A算 法A*算 法线 式 搜 索 36 为 了 便 于 分 析 ， 我 们 仅 考 虑 二 阶 梵 塔 (即 只 有 两 个 金 盘 )问 题 。 设 有 三 根 宝 石 杆 ， 在 1号 杆 上 穿 有 A、 B两 个 金 盘 ， A小于 B， A位 于 B的 上 面 . 要 求 把 这

34、 两 个 金 盘 全 部 移 到 另 一 根杆 上 ， 而 且 规 定 每 次 只 能 移 动 一 个 盘 子 ， 任 何 时 刻 都 不 能使 B位 于 A的 上 面 。 37 设 用 二 元 组 (SA， SB)表 示 问 题 的 状 态 ， SA表 示 金 盘 A所 在 的 杆 号 ， SB表示 金 盘 B所 在 的 杆 号 。 这 样 ， 全 部 可 能 的 状 态 有 9种 ， 可 表 示 如 下 ：这 里 的 状 态 转 换规 则 就 是 金 盘 的搬 动 规 则 ， 分 别用 A(i， J)及 B(i， J)表 示 ： A(i， J)表示 把 A从 第 i号 杆移 到 第 J号

35、杆 上 ； 共 有 l 2个 操 作 ， 它 们 分 别 是 : A(1， 2)， A(1， 3)， A(2， 1)， A(2， 3)， A(3，1)， 4(3， 2)， B(1， 2)， B(1， 3)， B(2， 1)， B(2， 3)， B(3， 1)， B3， 2) 38 二 阶 梵 塔 状 态 空 间 图 39 在 现 实 世 界 中 ， 经 常 会 遇 到 这 样 的 问 题 ： 一 个 问 题 可 以 有几 种 求 解 方 法 ， 只 要 其 中 一 种 方 法 可 以 求 解 问 题 ， 则 该 问题 被 求 解 。 也 就 是 说 ， 对 求 解 该 问 题 来 说 ， 方

36、法 之 间 是“ 或 ” 的 关 系 。但 在 用 每 一 种 方 法 求 解 时 ， 又 可 能 需 要 求 解 几 个 子 问 题 ，这 些 子 问 题 必 须 全 部 求 解 ， 才 可 能 用 该 方 法 求 解 原 始 问 题 。也 就 是 说 ， 这 些 子 问 题 之 间 是 “ 与 ” 的 关 系 。此 类 问 题 可 以 用 与 或 图 来 表 示 。 40 它 表 示 ， 如 果 要 求 解 n0， 可 以 求 解 n1， 或 者 求 解 n4、 n5， 也 就 是 说 ， 对于 n0来 说 ， n4和 n5是 与 的 关 系 ， 而 n1和 n4、 n5的 与 之 间 是

37、 或 的 关 系 。其 他 节 点 之 间 也 具 有 类 似 的 关 系 。 一 个 节 点 与 它 的 k个 与 子 节 点 间 用 下 图的 形 式 连 接 ， 称 为 k 连 接 符 。 41 从 图 可 以 看 出 ， 节 点 n0有 两 个 连 接 符 ：1-连 接 符 指 向 节 点 n1； 2-连 接 符 指 向 节点 集 n4， n5。 该 2-连 接 符 还 用 一 小 段圆 弧 括 起 来 （ 对 k 1的 k-连 接 符 都 应 有小 圆 弧 标 记 ） ， 以 表 示 子 节 点 间 与 的 关系 。 可 以 看 出 这 种 标 记 法 在 节 点 间 具 有明 确

38、的 关 系 。显 然 若 用 原 先 的 术 语 ， 则 对 父 节 点 n0来说 ， n4、 n5是 两 个 与 节 点 ， 而 n1可 称 为或 节 点 ；而 n8既 是 n5的 一 个 与 节 点 ， 又 是 n4的 一个 或 节 点 ， 混 淆 难 于 避 免 。另 外 也 把 图 中 没 有 任 何 父 节 点 的 节 点 叫 根 节 点 ， 没 有 任 何 后 继 节 点 的 节 点 叫 端节 点 或 叶 节 点 。 42 在 普 通 图 中 ， 目 标 用 一 个 节 点 表 达 ， 而 在 与 或 图 中 ， 目 标 则表 现 为 一 个 节 点 的 集 合 ， 该 集 合 中

39、 由 一 些 子 目 标 节 点 组 成 。值 得 指 出 的 是 ， 解 图 不 一 定 要 求 到 达 目 标 集 中 的 每 一 个 子 目标 节 点 ， 而 只 要 求 解 图 的 端 节 点 是 目 标 集 中 的 节 点 即 可 。 也就 是 说 ， 解 图 中 的 端 节 点 是 目 标 集 的 子 集 即 可 。 43 与 或 图 中 某 一 个 节 点 n到 节 点 集 N的 一 个 解 图 类 似 于 普 通 图 中的 一 条 解 路 径 。解 图 的 求 法 是 ： 从 节 点 n开 始 ， 正 确 选 择 一 个 外 向 连 接 符 ， 再从 该 连 接 符 所 指 的

40、 每 一 个 后 继 节 点 出 发 ， 继 续 选 一 个 外 向 连接 符 ， 如 此 进 行 下 去 直 到 由 此 产 生 的 每 一 个 后 继 节 点 成 为 集合 N中 的 一 个 元 素 为 止 。 44 在 与 或 图 是 无 环 （ 即 不 存 在 这 样 的 节 点 -其 后 继 节 后 同 时又 是 它 的 祖 先 ） 的 假 定 下 ， 解 图 可 递 归 定 义 如 下 ：定 义 ： 一 个 与 或 图 G中 ， 从 节 点 n到 节 点 集 N的 解 图 记 为 G， G是 G的 子 图 。 若 n是 N的 一 个 元 素 ， 则 G由 单 一 节 点 组 成 ；

41、 若 n有 一 个 指 向 节 点 n1， ， nk的 外 向 连 接 符 K， 使 得从 每 一 个 ni到 N有 一 个 解 图 （ i=1， ， k） ， 则 G由 节 点 n，连 接 符 K， 及 n1， ， nk中 的 每 一 个 节 点 到 N的 解 图 所 组成 ； 否 则 n到 N不 存 在 解 图 。 45 递 归 定 义 局 部 图 ：定 义 ： 单 一 节 点 是 一 个 局 部 图 ； 对 于 一 个 局 部 图 的 任 意 叶 节 点 n， 选 择 一 个 n的 外 向 连接 符 K， 则 该 局 部 图 、 外 向 连 接 符 K， 以 及 K所 连 接 的 n的

42、后 继 节 点 一 起 组 成 的 图 ， 仍 然 组 成 一 个 局 部 图 。 46 与 或 图 一 般 表 示 问 题 的 变 换 过 程 （ 而 不 是 状 态 变 换 ） 。 具体 讲 ， 它 是 从 原 问 题 出 发 ， 通 过 运 用 某 些 规 则 不 断 进 行 问题 分 解 （ 得 到 与 分 支 ） 和 变 换 （ 得 到 或 分 支 ） ， 而 得 到 一个 与 或 图 。换 句 话 说 ， 与 或 图 的 节 点 一 般 代 表 问 题 。 那 么 ， 整 个 图 就表 示 问 题 空 间 。与 或 图 中 的 父 节 点 与 其 子 节 点 服 从 逻 辑 上 的

43、 与 、 或 运 算 关系 。 所 以 ， 与 或 图 表 示 的 问 题 是 否 有 解 ， 要 进 行 逻 辑 判 断 ，与 或 图 的 搜 索 也 受 逻 辑 的 制 约 。 47 与 或 图 也 是 一 个 三 元 组(Q0,F,Qn)Q0,表 示 初 始 问 题 ， F表 示 问 题 变 换 规 则 集 ， Qn表 示 本 原 问题 集 。例 如 ： 积 分 公 式 ， 就 是 一 些 典 型 的 问 题 分 解 和 变 换 问 题 。 所以 ， 一 般 求 不 定 积 分 就 可 用 与 或 图 来 描 述 。 48 例 三 阶 Hanoi塔1 2 3三 阶 Hanoi塔 可 分

44、解 为 下 面 三 个 子 问 题 ：1） 把 A、 B盘 从 1号 杆 移 到 2号 杆 。2） 把 C盘 从 1号 杆 移 到 3号 杆 。3） 把 A、 B盘 从 2号 杆 移 到 3号 杆 。其 中 ， 子 问 题 1） 、 3） 又 可 分 解 为 三 个 子 问 题 。 49 三 阶 Hanoi塔 的 与 或 图 表 示 (i,j,k) i: C盘 所 在 杆 号 ， j: B盘 所 在 杆 号 ， k: A盘 所 在 杆 号 。(1,1,1)(3,3,3)(1,1,1)(1,2,2) (1,2,2)(3,2,2) (3,2,2)(3,3,3)(1,1,1)(1,1,3) (1,1

45、,3)(1,2,3) (1,2,3)(1,2,2) (3,2,2)(3,2,1) (3,2,1)(3,3,1) (3,3,1)(3,3,3) 50 这 里 所 讲 的 博 弈 ， 指 的 是 类 似 于 象 棋 这 样 的 游 戏 问 题 。 这类 问 题 有 以 下 一 些 特 点 ： （ 1） 双 人 对 弈 ， 对 垒 的 双 方 轮 流 走 步 。 （ 2） 信 息 完 备 ， 对 垒 双 方 所 得 到 的 信 息 是 一 样 的 ，不 存 在 一 方 能 看 到 ， 而 另 一 方 看 不 到 的 情 况 。 （ 3） 零 和 。 即 对 一 方 有 利 的 棋 ， 对 另 一 方

46、 肯 定 是 不利 的 ， 不 存 在 对 双 方 均 有 利 、 或 均 无 利 的 棋 。 对 弈 的 结 果是 一 方 赢 ， 而 另 一 方 输 ， 或 者 双 方 和 棋 。 51 博 弈 问 题 为 什 么 可 以 用 与 或 图 表 示 呢 ？可 以 这 样 来 看 待 这 个 问 题 ： 当 轮 到 我 方 走 棋 时 ， 只 需 从 若干 个 可 以 走 的 棋 中 ， 选 择 一 个 棋 走 就 可 以 了 。 从 这 个 意 义上 说 ， 若 干 个 可 以 走 的 棋 是 “ 或 ” 的 关 系 。 而 对 于 轮 到 对方 走 棋 时 ， 对 于 我 方 来 说 ，

47、必 须 能 够 应 付 对 手 的 每 一 种 走棋 。 这 就 相 当 于 这 些 棋 是 “ 与 ” 的 关 系 。因 此 ， 博 弈 问 题 可 以 看 成 是 一 个 与 或 图 ， 但 是 与 一 般 的 与或 图 并 不 一 样 ， 是 一 种 特 殊 的 与 或 图 。 52 1 概 述 博 弈 一 向 被 认 为 是 富 有 智 能 行 为 的 游 戏 ， 因 而 很 早 就 受到 人 工 智 能 界 的 重 视 ， 早 在 60年 代 就 已 经 出 现 若 干 博 弈 程 序 ，并 达 到 一 定 水 平 。 博 弈 问 题 的 研 究 还 不 断 提 出 一 些 新 的

48、研 究课 题 ， 从 而 也 推 动 了 人 工 智 能 研 究 的 发 展 。 对 于 单 人 博 弈 的 一 些 问 题 ， 可 用 一 般 的 搜 索 技 术 进 行 求解 ， 本 节 着 重 讨 论 双 人 完 备 信 息 这 一 类 博 弈 问 题 的 搜 索 策 略 。由 于 双 人 博 弈 可 用 与 或 树 （ 或 图 ） 来 描 述 ， 因 而 搜 索 就 是 寻找 最 佳 解 树 （ 图 ） 的 问 题 。 53 所 谓 双 人 完 备 信 息 ， 就 是 两 位 选 手 对 垒 ， 轮 流 走 步 ， 这 时每 一 方 不 仅 都 知 道 对 方 过 去 已 经 走 过

49、的 棋 步 ， 而 且 还 能 估计 出 对 方 未 来 可 能 的 走 步 。 对 弈 的 结 果 是 一 方 赢 （ 另 一 方则 输 ） ， 或 者 双 方 和 局 。这 类 博 弈 的 实 例 有 ： 一 字 棋 、 余 一 棋 、 西 洋 跳 棋 、 国 际 象棋 、 中 国 象 棋 、 围 棋 等 。 对 于 带 机 遇 性 的 任 何 博 弈 ， 因 不具 有 完 备 信 息 ， 不 属 这 里 讨 论 范 围 ， 但 有 些 论 述 可 推 广 到某 些 机 遇 博 弈 中 应 用 。 54 博 弈 问 题 可 以 用 产 生 式 系 统 的 形 式 来 描 述 ，例 如 中

50、国 象 棋 ， 综 合 数 据 库 可 规 定 为 棋 盘 上 棋 子 各 种 位 置布 局 的 一 种 描 述 ， 产 生 式 规 则 是 各 类 棋 子 合 法 走 步 的 描 述 ，目 标 则 可 规 定 为 将 （ 帅 ） 被 吃 掉 ， 规 则 作 用 于 数 据 库 的 结果 便 生 成 出 博 弈 图 或 博 弈 树 。 55 2 极 小 极 大 分 析 方 法 极 小 极 大 搜 索 方 法 是 博 弈 树 搜 索 的 基 本 方 法 ， 现 在 博 弈 树 搜 索 中 最 常用 的 -剪 枝 搜 索 方 法 ， 就 是 从 这 一 方 法 发 展 而 来 的 。 首 先 假

51、定 ， 有 一 个 评 价 函 数 可 以 对 所 有 的 棋 局 进 行 评 估 。当 评 价 函 数 值 大 于 0时 ， 表 示 棋 局 对 我 方 有 利 ， 对 对 方 不 利 。当 评 价 函 数 小 于 0时 ， 表 示 棋 局 对 我 方 不 利 ， 对 对 方 有 利 。而 评 价 函 数 值 越 大 ， 表 示 对 我 方 越 有 利 。当 评 价 函 数 值 等 于 正 无 穷 大 时 ， 表 示 我 方 必 胜 。评 价 函 数 值 越 小 ， 表 示 对 我 方 越 不 利 。 当评 价 函 数 值 等 于 负 无 穷 大 时 ， 表 示 对 方 必 胜 。假 设 双

52、 方 都 是 对 弈 高 手 ， 在 只 看 一 步 棋 的 情 况 下 ， 我 方 一 定 走 评 价 函 数 值最 大 的 一 步 棋 ， 而 对 方 一 定 走 评 价 函 数 值 最 小 的 一 步 棋 。 会 下 棋 的 都 知 道 ，在 只 看 一 步 的 情 况 下 最 好 的 棋 ， 从 全 局 来 说 不 一 定 就 好 ， 还 可 能 很 不 好 。因 此 为 了 走 出 好 棋 ， 必 须 多 看 几 步 ， 从 多 种 可 能 状 态 中 选 择 一 步 好 棋 。 56 想 一 想 人 是 如 何 下 棋 的 呢 ？ 人 实 际 上 采 用 的 是 一 种 试 探 性

53、 的 方 法 。首 先 假 定 走 了 一 步 棋 ， 看 对 方 会 有 那 些 应 法 ， 然 后 再 根 据 对 方 的 每 一 种应 法 ， 看 我 方 是 否 有 好 的 回 应 .这 一 过 程 一 直 进 行 下 去 ， 直 到 若 干 步 以后 ， 找 到 了 一 个 满 意 的 走 法 为 止 。 初 学 者 可 能 只 能 看 一 、 两 个 轮 次 ， 而高 手 则 可 以 看 几 个 ， 甚 至 十 几 个 轮 次 。 极 小 极 大 搜 索 方 法 ， 模 拟 的 就 是 人 的 这 样 一 种 思 维 过 程 当 轮 到 我方 走 棋 时 ， 首 先 按 照 一 定

54、 的 搜 索 深 度 生 成 出 给 定 深 度 d以 内 的 所 有 状 态 ，计 算 所 有 叶 节 点 的 评 价 函 数 值 。 然 后 从 d-1层 节 点 开 始 逆 向 计 算 ： 对 于 我方 要 走 的 节 点 （ 用 MAX标 记 ， 称 为 极 大 节 点 ） 取 其 子 节 点 中 的 最 大 值 为该 节 点 的 值 （ 因 为 我 方 总 是 选 择 对 我 方 有 利 的 棋 ） ； 对 于 对 方 要 走 的 节点 （ 用 MIN标 记 ， 称 为 极 小 节 点 ） 取 其 子 节 点 中 的 最 小 值 为 该 节 点 的 值（ 对 方 总 是 选 择 对

55、我 方 不 利 的 棋 ） 。 一 直 到 计 算 出 根 节 点 的 值 为 止 。 获得 根 节 点 取 值 的 那 一 分 枝 ， 即 为 所 选 择 的 最 佳 走 步 。 57 在 博 弈 问 题 中 ， 每 一 个 棋 局 可 供 选 择 的 行 动 方 案 都 有 很 多 ，因 此 会 生 成 十 分 庞 大 的 博 弈 树 。 据 统 计 ， 西 洋 跳 棋 完 整 的博 弈 树 约 有 1040个 节 点 。试 图 利 用 完 整 的 博 弈 树 来 进 行 极 小 极 大 分 析 是 困 难 的 。 可行 的 办 法 是 只 生 成 一 定 深 度 的 博 弈 树 ， 然

56、后 进 行 极 小 极 大分 析 ， 找 出 当 前 最 好 的 行 动 方 案 。 在 此 之 后 ， 再 在 已 选 定的 分 支 上 扩 展 一 定 深 度 ， 再 选 最 好 的 行 动 方 案 。 如 此 进 行下 去 ， 直 到 取 得 胜 败 的 结 果 为 止 。至 于 每 次 生 成 博 弈 树 的 深 度 ， 当 然 是 越 大 越 好 ， 但 由 于 受到 存 储 空 间 的 限 制 ， 只 好 根 据 实 际 情 况 而 定 。 58 在 九 宫 格 棋 盘 上 ， 两 位 选 手 轮 流 在 棋 盘 上 摆 各 自 的 棋 子 （ 每 次 一 枚 ） ， 谁先 取 得

57、 三 子 一 线 的 结 果 就 取 胜 。设 A的 棋 子 用 （ a） 表 示 ， 对 手 B的 棋 子 用 （ b） 表 示 ， A先 走 。 静 态 估 计 函数 f（ p） 规 定 如 下 : (p为 棋 局 ）若 p对 任 何 一 方 来 说 都 不 是 获 胜 的 格 局 ， 则f（ p） （ 所 有 空 格 都 放 上 A的 棋 子 之 后 ， A的 三 子 成 线 （ 行 、 列 、 对 角 ）的 总 数 （ 所 有 空 格 都 放 上 B的 棋 子 之 后 ， B的 三 子 成 线 （ 行 、 列 、 对 角 ） 的 总 数若 p是 A获 胜 的 格 局 ， 则 f（ p）

58、 ；若 p是 B获 胜 的 格 局 ， 则 f（ p） 。例 如 ， 当 p的 格 局 如 下 时 ， 则 可 得 f（ p） 6 4 2； ba 59 另 外 ， 我 们 假 定 具 有 对 称 性 的 两 个 棋 局 算 作 一 个 棋 局 。还 假 定 A先 走 棋 ， 我 们 站 在 A的 立 场 上 。 在 A走 S3这 一着 棋 后 ， B的 最优 选 择 是 S4，因 为 这 一 着 棋的 静 态 估 值 较小 ， 对 A不 利 。不 管 B选 择 S4或S5， A都 要 再 次运 用 极 小 极 大分 析 法 产 生 深度 为 2的 博 奕 树 , 以 决 定 下 一 步应 该

59、 如 何 走 棋 ，其 过 程 与 上 面类 似 ， 不 再 重复 。A的 第 一 着 走 棋 生 成 的 博 弈 树图 中 节 点 旁 的 数 字 分 别 表示 相 应 节 点 的 静 态 估 值 或倒 推 值 。 由 图 可 以 看 出 ，对 于 4来 说 最 好 的 一 着 棋 是S3： ， 因 为 S3比 S1和 S2有较 大 的 倒 推 值 。 60 基 于 谓 词 逻 辑 的 机 器 推 理1.猴 子 香 蕉 问 题已 知 一 串 香 蕉 挂 在 天 花 板 上 ， 猴 子 直 接 去 拿 是 够 不 到 的 ， 但 猴 子 可 以 走 动且 可 以 搬 着 梯 子 走 动 ， 也

60、 可 以 爬 上 梯 子 来 达 到 吃 香 蕉 的 目 的 。 用 谓 词逻 辑 描 述 该 问 题 ， 并 求 得 该 问 题 的 目 标 状 态 （ 猴 子 吃 到 香 蕉 列 ） 。2.设 已 知 ： (1)能 阅 读 者 是 识 字 的 ； (2)海 豚 不 识 字 ； (3)有 些 海 豚 是 很 聪 明 的 。 求 证 ： 有 些 聪 明 者 并 不 能 阅 读 。考 虑 ：设 已 知 ： (1)凡 是 清 洁 的 东 西 就 有 人 喜 欢 ； (2)人 们 都 不 喜 欢 苍 蝇 ； 用 归 结 原 理 证 明 ： 苍 蝇 是 不 清 洁 的 。 61 知 识 表 示 方 法

61、1.用 语 义 网 络 表 示 下 述 命 题 ：(1)树 和 草 都 是 植 物 。(2)树 和 草 都 是 有 根 、 有 叶 的 。(3)水 草 是 草 ， 且 长 在 水 中 。(4)果 树 是 树 ， 且 会 结 果 。(5)苹 果 树 是 果 树 中 的 一 种 ， 它 结 苹 果 。2.用 谓 词 公 式 表 示 下 列 规 则 性 知 识 ：(1)所 有 整 数 要 么 是 偶 数 要 么 就 是 奇 数 。(2)自 然 数 都 是 大 于 零 的 整 数 。 62 1. 设 样 本 空 间 =a, b, c, d， M1, M2为 定 义 在 上 的 概 率 分 配 函 数 。 已 知 ： M1b, c, d=0.7, M1a, b, c, d=0.3 M2a, b=0.6, M2a, b, c, d=0.4求 它 们 的 正 交 和 M1 M2.2.设 U=1,2,3,4,5， 定 义 模 糊 子 集 A=“小 ” =1/1+0.5/2+0/3+0/4+0/5 A=“比 较 小 ” =1/1+1/2+0.5/3+0.2/4+0/5 B=“大 ” =0/1+0/2+0.4/3+0.6/4+1/5已 知 (1)如 果 x小 ， 那 么 y大 ； (2)x比 较 小问 ： y怎 么 样 ？ （ 使 用 Zadeh的 CRI法 ） 63再 见