<4D6963726F736F667420506F776572506F696E74202D203320BCC6CBE3D1A7BFC6D6D0B5C4B5E4D0CDCECACCE2C7F3BDE22E707074205BBCE6C8DDC4A3CABD5D>

计 算 机 科 学 中 的 问 题 求 解 初 探 计 算 学 科 中 的 典 型 问 题 求 解 李 瑞 轩 教 授 华 中 科 技 大 学 智 能 与 分 布 计 算 实 验 室 rxli@hust.edu.cn http://idc.hust.edu.cn/~rxli/

主 要 内 容 哥 尼 斯 堡 七 桥 问 题 梵 天 塔 问 题 P 类 问 题 与 NP 类 问 题 哲 学 家 共 餐 问 题 GoTo 语 句 问 题 人 工 智 能 中 的 若 干 哲 学 问 题 图 灵 测 试 西 尔 勒 的 中 文 屋 子 计 算 机 中 的 博 弈 问 题

一 计 算 学 科 中 的 典 型 问 题 ( 非 数 值 计 算 ) 反 映 计 算 学 科 某 一 方 面 本 质 特 性 的 典 型 实 例 著 名 的 问 题 可 以 促 进 计 算 机 软 件 算 法 的 进 步

1 哥 尼 斯 堡 (Konigsberg) 七 桥 问 题 17 世 纪 的 东 普 鲁 士 有 一 座 哥 尼 斯 堡 城, 城 中 有 一 座 奈 佛 夫 岛, 普 雷 格 尔 河 的 两 条 支 流 环 绕 其 旁, 并 将 整 个 城 市 分 成 北 区 东 区 南 区 和 岛 区 4 个 区 域, 全 城 共 有 7 座 桥 将 4 个 城 区 相 连 起 来 人 们 常 通 过 这 7 座 桥 到 各 城 区 游 玩, 于 是 产 生 了 一 个 有 趣 的 数 学 难 题 : 寻 找 走 遍 这 7 座 桥, 且 只 许 走 过 每 座 桥 一 次, 最 后 又 回 到 原 出 发 点 的 路 径 该 问 题 就 是 著 名 的 哥 尼 斯 堡 七 桥 问 题 北 区 岛 区 东 区 南 区

Konigsberg 七 桥 问 题

Konigsberg 七 桥 问 题 C 问 题 抽 象 描 述 A B D 莱 昂 哈 德 欧 拉 (Leonhard Euler,1707-1783) 欧 拉 : 从 一 点 出 发 不 重 复 地 走 遍 七 桥, 最 后 又 回 到 原 点 是 不 可 能 的 一 般 化 处 理 : 对 给 定 的 任 意 一 个 河 道 图 与 任 意 多 座 桥, 判 定 可 能 不 可 能 每 座 桥 恰 好 走 过 一 次

欧 拉 回 路 欧 拉 用 数 学 方 法 给 出 了 3 条 判 定 规 则 : 如 果 通 奇 数 座 桥 的 地 方 不 止 两 个, 满 足 要 求 的 路 线 是 找 不 到 的 如 果 只 有 两 个 地 方 通 奇 数 座 桥, 可 以 从 这 两 个 地 方 之 一 出 发, 找 到 所 要 求 的 路 线 如 果 没 有 一 个 地 方 是 通 奇 数 座 桥 的, 则 无 论 从 哪 里 出 发, 所 要 求 的 路 线 都 能 实 现 上 述 3 条 判 定 规 则 包 含 了 任 一 连 通 无 向 图 是 否 存 在 欧 拉 路 径 (Euler Path) 和 欧 拉 回 路 (Euler Circuit) 的 判 定 条 件 根 据 判 定 规 则 (3) 可 以 得 出, 任 一 连 通 无 向 图 存 在 欧 拉 回 路 的 充 分 必 要 条 件 是 图 的 所 有 顶 点 均 为 偶 数 度 欧 拉 回 路 为 图 论 的 形 成 奠 定 了 基 础

哈 密 尔 顿 回 路 问 题 在 图 论 中 还 有 一 个 很 著 名 的 哈 密 尔 顿 回 路 问 题 该 问 题 是 爱 尔 兰 著 名 学 者 威 廉 哈 密 尔 顿 爵 士 (W.R.Hamilton) 在 1859 年 提 出 的 一 个 数 学 问 题 其 大 意 是 : 在 任 一 给 定 的 图 中, 能 不 能 找 到 这 样 的 路 径, 即 从 一 点 出 发 不 重 复 地 走 过 所 有 的 结 点 ( 不 必 通 过 图 中 每 一 条 边 ), 最 后 又 回 到 原 出 发 点 对 于 前 面 的 例 子 来 说, 如 果 是 求 哈 密 尔 顿 回 路, 就 是 遍 历 A B C D 四 个 点, 最 后 又 回 到 原 出 发 点 A C B 对 于 哈 密 尔 顿 回 路 问 题 至 今 仍 未 找 到 满 足 问 题 的 充 分 必 要 条 件 D

图 论 的 形 成 和 发 展 欧 拉 的 论 文 为 图 论 的 形 成 奠 定 了 基 础 图 论 已 广 泛 地 应 用 于 : 计 算 学 科 运 筹 学 信 息 论 控 制 论 等 学 科 图 论 已 成 为 我 们 对 现 实 问 题 进 行 抽 象 的 一 个 强 有 力 的 数 学 工 具 图 论 在 计 算 学 科 中 的 作 用 越 来 越 大, 图 论 本 身 也 得 到 了 充 分 的 发 展

2 Hanoi 塔 问 题 相 传 印 度 教 的 天 神 梵 天 在 创 造 地 球 这 一 世 界 时, 建 了 一 座 神 庙, 神 庙 里 竖 有 三 根 宝 石 柱 子, 柱 子 由 一 个 铜 座 支 撑 梵 天 将 64 个 直 径 大 小 不 一 的 金 盘 子, 按 照 从 大 到 小 的 顺 序 依 次 套 放 在 第 一 根 柱 子 上, 形 成 一 座 金 塔, 即 所 谓 的 梵 天 塔 ( 又 称 汉 诺 塔 ) 天 神 让 庙 里 的 僧 侣 们 将 第 一 根 柱 子 上 的 64 个 盘 子 借 助 第 二 根 柱 子 全 部 移 到 第 三 根 柱 子 上, 即 将 整 个 塔 迁 移, 同 时 定 下 3 条 规 则

Hanoi 塔 问 题 1 2 3 B A C 问 题 : 将 第 一 根 柱 子 上 的 64 盘 子 借 助 于 第 二 根 柱 子 全 部 移 动 第 三 根 柱 子 上 约 束 : (1) 每 次 只 能 移 动 一 个 ; (2) 只 能 在 三 根 柱 子 上 来 回 移 动, 不 能 放 在 它 处 ; (3) 在 移 动 过 程 中, 三 根 柱 子 上 的 盘 子 必 须 始 终 保 持 大 在 下 小 在 上

解 题 过 程 (3 个 圆 盘 问 题 ) 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3

多 圆 盘 梵 天 塔 难 题 演 示

多 圆 盘 梵 天 塔 难 题 演 示 64 个 盘 子 63 个 盘 子

梵 天 塔 问 题 解 法 解 : 采 用 递 归 的 思 想 : 将 一 个 较 大 的 问 题 归 约 为 一 个 或 多 个 子 问 题 的 求 解, 子 问 题 比 原 问 题 简 单, 且 结 构 与 原 问 题 相 同 h(n)=2h(n-1)+1 =2(2h(n-2)+1)+1=2 ( ) 2 h(n-2)+2+1 =2 3 h(n-3)+2 2 +2+1 =2 n h(0)+2 n-1 + +2 2 +2+1 =2 n-1 + +2 2 +2+1=2 n -1 2 64-1=18446744073709551615 1 次 / 秒,2 64-1/31536000( 秒 )=5849 亿 年 ( 世 界 末 日 ) 2 64-1/1000 万 次 =58490 年 能 行 问 题 O(2 n ) 能 行 问 题 O(2 ) P=?NP 问 题

算 法 : 梵 天 塔 问 题 C 语 言 描 述 hanoi(int n, char left, char middle, char right) { } { if (n==1) move(1, one, _, three); else } hanoi(n-1, left, right, middle); move(1, left, _, right); hanoi(n-1, middle, left, right);

3 P 类 问 题 与 NP 类 问 题 算 法 复 杂 性 包 括 算 法 的 空 间 以 及 时 间 两 方 面 的 复 杂 性 问 题, 梵 天 塔 问 题 主 要 讲 的 是 算 法 的 时 间 复 杂 性 将 所 有 可 以 在 多 项 式 时 间 内 求 解 的 问 题 称 为 P 类 问 题 将 所 有 在 多 项 式 时 间 内 可 以 验 证 的 问 题 称 为 NP 类 问 题

P 类 问 题 与 NP 类 问 题 证 比 求 易 问 题 问 题 的 引 入 国 王 求 婚 问 题 求 出 48 770 428 433 377 171 (17 位 数 ) 的 一 个 真 因 子 算 法 1: 从 2 开 始 逐 个 除, 一 秒 一 个, 一 天 算 86400 个 答 案 :223 092 827 算 法 2: 最 小 的 真 因 子 不 会 超 过 9 位, 全 民 动 员 串 行 与 并 行, 时 间 与 空 间, 折 衷 n O(10 2 ) 指 数 级

(1) 旅 行 商 ( 货 郎 担 ) 问 题 (Traveling Salesman Problem,TSP) A 2 B 4 4 6 5 D 2 C 经 且 只 经 每 个 城 市 一 次, 回 到 出 发 点, 路 程 ( 费 用 ) 最 短 ( 少 ) 旅 行 商 ( 货 郎 担 ) 问 题 是 比 哈 密 尔 顿 回 路 更 强 约 束 的 问 题

旅 行 商 问 题 与 组 合 爆 炸 问 题 若 设 城 市 数 目 为 n 时, 那 么 组 合 路 径 数 则 为 (n 1)! 0 ( (n 1)! )

旅 行 商 问 题 与 组 合 爆 炸 问 题 1998 年 实 现 13509 个 城 市 之 间 的 TSP 问 题 2001 年 15112 个 城 市 的 TSP,, 用 了 11 台 计 算 机, 共 花 费 22.9 年 其 他 的 应 用 如 电 路 板 钻 孔, 运 输 业 后 勤 服 务 业 等

顺 序 算 法 和 并 行 算 法 顺 序 算 法 -- 时 间 复 杂 性 大 并 行 算 法 -- 空 间 复 杂 性 大 直 觉 上, 顺 序 算 法 解 决 不 了 的 问 题 完 全 可 以 用 并 行 算 法 来 解 决, 是 这 样 吗?

(2) 阿 尔 达 定 律 ( 并 行 ) 加 速 比 的 局 限 设 f 为 求 解 某 个 问 题 的 计 算 存 在 的 必 须 串 行 执 行 操 作 占 整 个 计 算 的 百 分 比,p 为 处 理 器 的 数 目,Sp 为 并 行 计 算 机 系 统 最 大 的 加 速 能 力, 则 : S P 1 f 1 f P P + 无 穷 大 S p =1/f p / 对 难 解 性 问 题 而 言, 降 低 算 法 复 杂 度 的 数 量 级 是 关 键!

(2) 阿 尔 达 定 律 ( 并 行 ) 加 速 比 的 局 限 设 f 为 求 解 某 个 问 题 的 计 算 存 在 的 必 须 串 行 执 行 操 作 占 整 个 计 算 的 百 分 比,p 为 处 理 器 的 数 目,Sp 为 并 行 计 算 机 系 统 最 大 的 加 速 能 力, 则 : S P 1 f 1 f P P + 无 穷 大 S p =1/f p / 对 难 解 性 问 题 而 言, 降 低 算 法 复 杂 度 的 数 量 级 是 关 键!

(3)P= P=?NP P 和 NP 类 问 题 将 所 有 可 以 在 多 项 式 时 间 内 求 解 的 问 题 称 为 P 类 问 题 (Polynomial problem) 将 所 有 在 多 项 式 时 间 内 可 以 验 证 的 问 题 称 为 NP 类 问 题 (Non-deterministic Polynomial problem) 例 子 P 类 问 题 : 配 袜 子 O(n) NP 类 问 题 :DNA 公 主 求 婚 : 证 比 求 易,O(10 n/2 ) P NP 即 能 求 解 一 定 能 验 证 验 证 : 常 数 级 ( 多 项 式 时 间 内 )

P=?NP P=?NP 悬 而 未 决 的 最 大 问 题 如 果 P=NP, 则 所 有 在 多 项 式 时 间 内 可 验 证 的 问 题 都 将 是 在 多 项 式 时 间 内 可 求 解 ( 或 可 判 定 ) 的 问 题 NP 中 某 些 问 题 中 寻 找 多 项 式 时 间 算 法, 从 未 成 功 趋 向 于 NP P 不 成 立, 到 目 前 为 止 P NP 又 无 法 证 明

NP 完 全 性 问 题 NP 完 全 性 问 题 针 对 P=NP 是 否 成 立 的 问 题, 库 克 (S.A.Cook) 等 人 认 为 NP 类 中 的 某 些 问 题 的 复 杂 性 与 整 个 类 的 复 杂 性 有 关, 当 这 些 问 题 中 的 任 何 一 个 存 在 多 项 式 时 间 算 法 时, 则 所 有 这 些 NP 问 题 都 是 多 项 式 时 间 可 解 的, 这 些 问 题 被 称 为 NP 完 全 性 问 题 存 在 多 达 数 千 个 NP 完 全 性 问 题 有 代 表 性 的 有 : 哈 密 尔 顿 回 路 问 题 旅 行 商 问 题 ( 也 称 货 郎 担 问 题 ) 划 分 问 题 带 优 先 级 次 序 的 处 理 机 调 度 问 题 顶 点 覆 盖 问 题 等

NP 完 全 性 问 题 目 前, 只 能 对 NP 完 全 问 题 求 近 似 解, 次 优 解 ( 能 在 多 项 式 时 间 即 有 效 时 间 内 完 成 ) NP 完 全 性 问 题 例 : 可 满 足 性 问 题 (Satisfiability Problem, 简 称 SAT Problem) 判 定 一 个 布 尔 公 式 是 否 可 满 足 的 ; SAT = { < > 是 可 满 足 的 布 尔 公 式 }; 库 克 结 论 : SAT P, 当 且 仅 当 P = NP

计 算 复 杂 性 理 论 应 用 密 码 学 私 钥 密 码 体 制, 加 解 密 规 则 一 致, 易 破 解 明 文 密 钥 密 文 加 密 算 法 解 密 算 法 公 钥 密 码 系 统 RSA 提 出 者 获 得 图 灵 奖 利 用 加 密 秘 钥 解 密 密 钥 是 一 个 NP Complete 问 题, 在 有 效 时 间 不 可 能 求 解, 本 质 是 大 合 数 的 真 因 子 分 解 密 码 体 系 建 立 在 NP Complete 问 题 上, 若 NP Complete 能 在 多 项 式 时 间 内 求 解, 则 结 果 是 可 怕 的

计 算 复 杂 性 理 论 应 用 密 码 学 公 钥 密 码 系 统 RSA 加 密 密 钥 公 开, 解 密 密 钥 私 有 例 : 三 月 二 十 八 日 早 晨 七 点 不 发 起 总 攻 三 月 二 十 八 日 早 晨 七 点 不 发 起 总 攻 解 密 密 钥 : 质 数 位 无 效 嵌 入 了 干 扰 字 符, 可 利 用 猜 统 计 数 学 方 法 等 解 密

4 哲 学 家 共 餐 问 题 5 个 哲 学 家 围 坐 在 一 张 圆 桌 旁, 每 个 人 的 面 前 摆 有 一 碗 面 条, 碗 的 两 旁 各 摆 有 一 只 筷 子 一 个 哲 学 专 家 的 生 活 进 程 : (1) 思 考 问 题 (2) 左 手 拿 筷 ( 等 待 的 可 能 ) (3) 右 手 拿 筷 ( 等 待 的 可 能 ) (4) 进 餐 (5) 放 右 筷 (6) 放 左 筷 (7) 返 回 (1) 问 题 : 如 何 协 调 5 人 的 生 活 进 程, 使 得 每 一 人 最 终 都 可 进 餐 饿 死 例 : (1) 同 时 拿 起 左 手 筷 全 等 待 (2) 同 时 放 同 时 拿 的 循 环

哲 学 家 共 餐 问 题 程 序 并 发 执 行 时 进 程 同 步 的 两 个 问 题 : 死 锁 与 饥 饿 一 般 性 问 题,n 个 进 程 与 m 个 共 享 资 源 的 问 题 关 键 : 协 调 资 源 调 度 问 题 5 只 筷 子 同 时 只 能 有 2 个 人 能 进 餐 操 作 系 统 : 进 程 调 度 问 题,M/S I/O CPU 之 间 的 协 调 哲 学 家 共 餐 问 题 也 是 解 决 死 锁 的 理 论 和 机 制, 引 入 信 号 灯 的 概 念

5 GoTo 语 句 问 题 以 及 程 序 设 计 方 法 学 任 何 程 序 的 逻 辑 结 构 都 可 以 用 3 种 最 基 本 的 结 构 顺 序 结 构 选 择 结 构 循 环 结 构 来 表 示 处 理 框 判 断 框 循 环 体

GOTO 语 句 1968 年,E.W.Dijkstra: GoTo 语 句 是 有 害 的 结 论 : 滥 用 GoTo 语 句 是 有 害 的, 完 全 禁 止 也 不 明 智 好 的 程 序 应 是 逻 辑 正 确 结 构 清 晰 朴 实 无 华 GoTo 语 句 问 题 的 争 论 导 致 程 序 设 计 方 法 学 的 产 生

二 人 工 智 能 中 的 若 干 哲 学 问 题 图 灵 测 试 西 尔 勒 的 中 文 屋 子 计 算 机 中 的 博 弈 问 题

1. 图 灵 测 试 图 灵 于 1950 年 在 英 国 心 (Mind) 杂 志 上 发 表 了 计 算 机 器 和 智 能 (Computing Machinery and Intelligence) 一 文, 文 中 提 出 了 机 器 能 思 维 吗? 这 样 一 个 问 题, 并 给 出 了 一 个 被 称 作 模 仿 游 戏 (Imitation Game) 的 试 验, 后 人 称 之 为 图 灵 测 试 (Turing Test) 图 灵 测 试 ( 又 称 图 灵 判 断 ) 是 图 灵 提 出 的 一 个 关 于 机 器 人 的 著 名 判 断 原 则 所 谓 图 灵 测 试 是 一 种 测 试 机 器 是 不 是 具 备 人 类 智 能 的 方 法 被 测 试 的 有 一 个 人, 另 一 个 是 声 称 自 己 有 人 类 智 力 的 机 器

图 灵 测 试 计 算 机 男 (A) X 女 (B) Y C 提 问 者 如 果 在 C X Y 的 游 戏 中 作 出 的 错 误 判 断 与 在 计 算 机 C Y 的 游 戏 中 作 出 的 错 误 判 断 次 数 相 同, 那 么, 机 器 是 能 够 思 维 的 ( 非 结 构, 而 是 从 功 能 角 度 上 )

图 灵 测 试 根 据 图 灵 的 预 测, 到 2000 年, 此 类 机 器 能 通 过 测 试 现 在, 在 某 些 特 定 的 领 域, 如 博 弈 领 域, 图 灵 测 试 已 取 得 了 成 功,1997 年,IBM 公 司 研 制 的 计 算 机 深 蓝 就 战 胜 了 国 际 象 棋 冠 军 卡 斯 帕 罗 夫 人 类 思 维 的 本 质 尚 未 真 正 了 解 人 工 智 能 并 无 实 质 性 突 破

2. J. R. Searle 的 中 文 屋 子 假 设 西 尔 勒 被 单 独 关 在 一 个 屋 子 里, 屋 子 里 有 序 地 堆 放 着 足 量 的 汉 语 字 符, 而 他 对 中 文 是 一 窍 不 通 这 时 屋 外 的 人 递 进 一 串 汉 语 字 符, 同 时 还 附 一 本 用 英 文 写 的 处 理 汉 语 字 符 的 规 则, 这 些 规 则 将 递 进 来 的 字 符 和 屋 子 里 的 字 符 之 间 的 转 换 作 了 形 式 化 的 规 定, 西 尔 勒 按 规 则 指 假 设 西 尔 勒 很 擅 长 按 照 指 令 娴 熟 地 令 对 这 些 字 符 进 行 一 番 搬 弄 之 后, 处 理 一 些 汉 字 符 号, 而 程 序 设 计 师 又 将 一 串 新 组 成 的 字 符 送 出 屋 外 擅 长 编 写 程 序 ( 即 规 则 ), 那 么, 西 事 实 上 他 根 本 不 知 道 送 进 来 的 字 尔 勒 的 答 案 将 会 与 一 个 地 道 的 中 国 人 符 串 就 是 屋 外 人 提 出 的 问 题, 作 出 的 答 案 没 什 么 不 同 也 不 知 道 送 出 去 的 就 是 所 谓 问 题 但 是, 我 们 能 说 西 尔 勒 真 的 懂 中 文 的 答 案 吗?

J. R. Searle 的 中 文 屋 子 Searle 真 的 懂 中 文 吗? 形 式 化 的 计 算 机 仅 有 语 法, 没 有 语 义 人 在 计 算 能 力 上 超 过 机 器 是 不 现 实 的 机 器 永 远 也 不 可 能 代 替 人 脑 美 国 哲 学 家 约 翰 西 尔 勒 (J.R.Searle) 将 有 关 人 工 智 能 的 研 究 划 分 为 强 人 工 智 能 (Strongg Artificial Intelligence, 强 AI) 和 弱 人 工 智 能 (Soft Artificial Intelligence, 弱 AI) 两 个 派 别 Soft AI: 计 算 机 是 一 个 工 具 Strong AI: 不 仅 是 一 个 工 具, 而 且 具 有 意 识 中 文 屋 子 反 驳 强 人 工 智 能 (SAI) 观 点

3. 博 弈 树 搜 索 所 谓 双 人 完 备 博 弈 就 是 两 位 选 手 对 垒, 轮 流 走 步, 其 中 一 方 完 全 知 道 另 一 方 已 经 走 过 的 棋 步 以 及 未 来 可 能 的 走 步, 对 弈 的 结 果 要 么 是 一 方 赢 ( 另 一 方 输 ), 要 么 是 和 局 国 际 象 棋 西 洋 跳 棋 围 棋 中 国 象 棋 都 属 于 双 人 完 备 博 弈 对 于 任 何 一 种 双 人 完 备 博 弈, 都 可 以 用 一 个 博 弈 树 ( 与 或 树 ) 来 描 述, 并 通 过 博 弈 树 搜 索 策 略 寻 找 最 佳 解

博 弈 树 博 弈 树 类 似 于 问 题 求 解 搜 索 中 使 用 的 搜 索 树 搜 索 树 上 的 第 一 个 结 点 对 应 一 个 棋 局, 树 的 分 支 表 示 棋 的 走 步, 根 节 点 表 示 棋 局 的 开 始, 叶 节 点 表 示 棋 局 的 结 束 一 个 棋 局 的 结 果 可 以 是 赢 输 或 者 和 局 博 弈 树 的 规 模 : 国 际 跳 棋 --10 40 个 结 点 国 际 象 棋 --10 120 个 结 点 ( 棋 局 总 数 ) 中 国 象 棋 -- 估 计 有 10 160 个 结 点, 围 棋 -- 盘 面 状 态 达 10 10 768 768

井 字 棋 游 戏 井 字 棋 游 戏 ( 又 叫 三 子 棋 ), 是 一 款 十 分 经 典 的 益 智 小 游 戏 井 字 棋 的 棋 盘 很 简 单, 是 一 个 3 3 的 格 子, 很 像 中 国 文 字 中 的 井 字, 所 以 得 名 井 字 棋 设 有 九 个 空 格, 由 MAX,MIN 二 人 对 弈, 轮 到 谁 走 棋 谁 就 往 空 格 上 放 一 只 自 己 的 棋 子, 棋 子 放 完 后, 可 以 向 周 围 空 的 格 子 移 动 棋 子, 每 次 一 步, 谁 先 使 自 己 的 棋 子 构 成 三 子 成 一 线 (( 同 一 行 或 列 或 对 角 线 全 是 某 人 的 棋 子 ), 谁 就 取 得 了 胜 利 用 叉 号 表 示 MAX, 用 圆 圈 代 表 MIN

思 考 题 1. 井 字 棋 例, 下 一 步 机 器 (O) 走 X, 定 义 搜 索 树, 局 部 到 底 ( 叶 节 点 ) O O X X 2. 在 汉 诺 塔 中, 1) 先 把 最 小 的 盘 移 到 B; 2) 调 用 63 个 盘 的 移 动 过 程, 移 到 C; 3) 把 B 中 的 小 盘 移 到 C 则 h(n)=h(n-1)+2; h(n)=2n 算 法 时 间 复 杂 度 为 O(n) 上 述 分 析 有 问 题 吗?

思 考 题 赛 纳 河 流 经 巴 黎 的 这 一 段 河 中 有 两 个 岛, 河 岸 与 岛 间 架 设 了 15 座 桥, 如 下 图 所 示 问 : (l) 能 否 从 某 地 出 发, 经 过 这 15 座 桥 各 一 次 后 再 回 到 出 发 点? ( ) 若 不 要 求 回 到 出 发 点 能 否 在 次 散 步 中 穿 过 所 有 的 (2) 若 不 要 求 回 到 出 发 点, 能 否 在 一 次 散 步 中, 穿 过 所 有 的 桥 各 一 次? 若 可 以, 请 把 路 径 写 出

思 考 题 判 断 下 列 图 中, 哪 个 存 在 欧 拉 路 径, 哪 个 存 在 欧 拉 回 路

思 考 题 判 断 下 列 图 中, 哪 个 存 在 哈 密 尔 顿 回 路

思 考 题 对 于 本 质 上 可 以 进 行 并 行 计 算 的 特 定 问 题 ( 如 Google 的 搜 索 引 擎, 其 计 算 本 质 上 是 并 行 的, 该 引 擎 可 以 在 不 同 的 处 理 器 上 运 行 不 同 的 查 询 ), 阿 姆 达 尔 定 律 对 这 类 问 题 适 用 吗?