第 4 章 回 溯 寻 找 问 题 的 解 的 一 种 可 靠 的 方 法 是 首 先 列 出 所 有 候 选 解 ， 然 后 依 次 检 查 每 一 个 ， 在 检 查 完 所有 或 部 分 候 选 解 后 ， 即 可 找 到 所 需 要 的 解 。 理 论 上 ， 当 候 选 解 数 量 有 限 并 且 通 过 检 查 所 有 或部 分 候 选 解 能 够 得 到 所 需 解 时 ， 上 述 方 法 是 可 行 的 。 不 过 ， 在 实 际 应 用 中 ， 很 少 使 用 这 种 方法 ， 因 为 候 选 解 的 数 量 通 常 都 非 常 大 （ 比 如 指 数 级 ， 甚 至 是 大 数 阶 乘 ） ， 即 便 采 用 最 快 的 计算 机 也 只 能 解 决 规 模 很 小 的 问 题 。 对 候 选 解 进 行 系 统 检 查 的 方 法 有 多 种 ， 其 中 回 溯 和 分 枝 定界 法 是 比 较 常 用 的 两 种 方 法 。按 照 这 两 种 方 法 对 候 选 解 进 行 系 统 检 查 通 常 会 使 问 题 的 求 解 时间 大 大 减 少 （ 无 论 对 于 最 坏 情 形 还 是 对 于 一 般 情 形 ） 。 事 实 上 ， 这 些 方 法 可 以 使 我们避免对很 大 的 候 选 解 集合进 行 检 查 ， 同时 能 够 保证算 法 运行 结束时 可 以 找 到 所 需 要 的 解 。 因 此， 这些 方 法 通 常 能 够 用 来求 解 规 模 很 大 的 问 题 。 本章 集中 阐述 回 溯 方 法 ， 这 种 方 法 被用 来设计 货箱装船、背包、最 大 完 备子图、旅行 商和 电路板排列 问 题 的 求 解 算 法 。 4.1 算 法 思想 回 溯 （ b a c k t r a c k i n g） 是 一 种 系 统 地搜索问 题 解 答的 方 法 。 为 了实 现回 溯 ， 首先 需 要 为 问 题 定 义一 个 解 空间 （ solution space） ， 这 个 空间 必须至 少 包含问 题 的 一 个 解（ 可 能 是 最 优的 ） 。 在 迷宫老鼠问 题 中 ， 我们可 以 定 义一 个 包含从入口到 出 口的 所 有 路径的解 空间 ；在 具有 n 个 对 象的 0 / 1背包问 题 中 （ 见1 . 4节和 2 . 2节） ， 解 空...
