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