1.2.1. 模型¶

回想一下，要做分析，我们必须定义一个由两部分组成的模型： 输入规模的定义，以及如何度量解代价的定义。

1. 对我们的模型来说，输入规模 是圆盘的个数。

2. 对我们的模型来说，解的代价 是所做的移动次数。

1.2.2. 寻找算法¶

在尝试求解大多数问题时，一个好的起点是尝试 就小实例求解。 当有 0 个圆盘、1 个圆盘或 2 个 圆盘时，我们会如何解决这个问题？ 这些对你来说应该都比较容易想出来。 3 个圆盘呢？ 这就开始有点难了。 想一想一个 3 圆盘移动系列的所有可能选择。 有好几种可能性，但你应该会发现只有一种 "合理"的选择。 我们能从求解 3 个圆盘的经验中推广出些什么吗？ 解 4 个圆盘时呢？

这里有一个有用的观察：最大的圆盘对其他圆盘的移动 没有影响。 为什么？ 因为它总是在其他圆盘下面，所以其他圆盘 可以像它不存在一样自由移动。 这为什么有用？因为它实质上意味着在思考求解子问题时， 我们可以忽略最大的圆盘。 最重要的是，它意味着我们可以使用最大圆盘所在的 那根柱子来求解子问题，就好比那个圆盘 根本不存在一样。

如果你自己实际摆弄一下这个问题，你还会得出 另一个观察。 这一点很关键： 除非所有其他圆盘都已在柱子 C 上，否则我们不能把 底层圆盘从柱子 A 移到柱子 B。 这个关键观察几乎立即给我们问题的 解。

问题求解常常依赖一个让你得以"破解"问题的 "关键洞察"。 同样，对问题的 分析 可能依赖于 如何看待这个分析的"关键洞察"。 这常常是对算法的"状态"或进展的一种简化， 或是对问题关键输入类别的识别。

当我们把问题推广到更多圆盘时，任何高效解 都必须归结为某种类似的过程：

• 把所有除底层圆盘以外的圆盘移到柱子 C。

• 把底层圆盘从柱子 A 移到柱子 B。

• 把剩余的圆盘从柱子 C 移到柱子 B。

注意，在这个讨论中，我们使用了若干求解问题 的启发式方法来解决这个问题，包括：

• 弄脏双手：尝试摆弄一些简单的例子 （比如输入规模 0、1、2）。

• 走向极端：先检查小情形。

• 倒数第二步：关键的洞察是，除非我们移动底层圆盘， 否则无法解决问题，而这样做的办法只有一种。 所以要解决整个问题，我们首先清空底层圆盘上方的圆盘， 然后移动底层圆盘，再解决问题的其余部分。 把整个问题化简为这几部分，希望它比原来的问题 更容易解。

作为一个实际问题，我们如何处理必须移动 \(n-1\) 个圆盘（两次）这一事实？ 作为程序员，我们习惯于把任务打包进某种 子程序里。 在这种情况下，由于在 \(n-1\) 个圆盘上求解问题 看起来就像是求解原问题的一个较小版本， 自然就会想到用递归。

把这种问题求解方法稍作推广，可以说我们使用了 一种前向－后向策略： 首先我们求解简单的特例并推广它们的 解，然后我们在其他特例上检验这个推广。

下面是算法，以程序的形式给出:

void Tower1(int n, POLE start, POLE goal, POLE tmp) {
  if (n == 0) return;             // 基本情况 Tower1(n-1, start, tmp, goal); // 递归：n-1 个圆盘 move(start, goal);              // 移动一个圆盘 Tower1(n-1, tmp, goal, start); // 递归：n-1 个圆盘
}

1.2.3. 算法分析¶

由于问题的输入是圆盘个数，问题的规模 也是圆盘个数，所以规模为 \(n\) 的输入实例只有一个。 因此，我们不必担心与最坏、最好或平均情况代价相关的 各种复杂问题。 这正是我们选择首先讨论这个问题的原因之一—我们不会被给定规模 \(n\) 的输入范围 所困扰。

给定一个求解该问题的算法，我们想知道 该算法的代价作为输入规模的函数是什么。 特别是，我们想知道该算法在输入规模增大时的 增长率。 特别是，我们的代价模型说明我们的代价是 为求解问题所做的移动次数。 所以，我们想要按 :math:`n` 的函数来计算所需的移动次数。

要做到这一点，我们需要一个数学模型、某个把 移动次数定义为 \(n\) 的函数的方程。 我们如何得到它？ 我们可以从算法的结构推出它，或通过 观察它的行为得到它。 让我们从行为开始（不过一旦我们建立了一些 递推关系的熟练度，我们将 发现这个特定算法的结构让这个方程 相当直截了当）。 下面是一些事实，帮助我们通过计算算法对少量输入 所做的移动次数来起步。

• \(f(0) = 0\)。

• \(f(1) = 1\)。

• \(f(2) = 3\)。

• \(f(3) = 7\)。

现在，我们如何推广它？ 如果我们查看算法，会发现有两次递归 调用，并做一次移动。 我们不知道递归调用的代价到底是什么。 但如果我们给算法的代价起个名字，我们就可以用 同一个名字来标识子问题的代价。 所以，对任意输入规模 \(n\)，我们可以把代价 推广为：

• \(f(n) = f(n-1) + 1 + f(n-1) = 2f(n-1) + 1, \forall n \geq 4\)。

这用的是 递推关系，我们需要通过 为递推找一个 闭式解 来"求解"它。

实际上，我们可以简化我们的事实清单。 我们只需要 f(1) 和 f(n)，因为事实 f(2) 和 f(3) 是多余 信息。 但把它们写出来也许有助于我们看到这个模式。 这个问题我们只需要一个基例。 下面是为我们算法代价定义数学模型 的正式递推关系：

我们怎样才能为这个递推找到闭式解？ 通常，在这些分析问题中的任一个中，除非我们"弄脏双手" 摆弄一些方程行为的小例子， 否则我们寸步难行。 所以这里有一个包含前几个值的小表。

我们能在这里看到模式吗？ 看起来每加一个圆盘，我们大致加倍代价—就像 \(2^n\) 之类的东西。 如果我们检查一些简单的情形，就会发现它们似乎吻合 精确方程 \(f(n) = 2^n - 1\)。

这确实是找出许多递推关系和求和闭式解的 常见方式： 看看发生了什么，尝试寻找（或猜测）一个模式，然后检验 这个模式。 这太常见了，以至于它有自己专有名称： 猜测与验证。 我们将大量使用它来帮助分析。

现在我们有了一个相当好的猜测， 我们如何证明它 总是 成立？ 这就是"猜测与验证"中的"验证"部分。

让我们 假设 \(f(n-1) = 2^{n-1} - 1\)，看看 发生什么。 取这个递推，简单地用我们的猜测 \(2^{n-1} - 1\) 替换 \(f(n-1)\)。 这样做给出 \(f(n) = 2f(n-1) + 1 = 2(2^{n-1} - 1) + 1 = 2^n - 1\)。

这里的蕴涵是：如果 曾经 存在某个使 \(f(n) = 2^n - 1\) 成立的 \(n\)，那么对所有更大的 \(n\) 值， \(f\) 都遵循这条规则。 这就是 归纳证明 的本质。 要用归纳法证明，我们需要展示两件事：

1. 我们能起步（基例）。

2. 对 \(k\) 为真意味着对 \(k+1\) 也为真。

下面是 Tower1 代价的完整归纳证明：

1.2.4. 问题的下界¶

这是一个好算法吗？ 这取决于什么？ 取决于问题的内在难度！

要判断这个算法好不好，我们需要 问题代价的一个下界。 问题的下界是我们能对 所有可能求解该问题的算法 证明的 最紧（最高）下界。 这可能是一道难题，因为我们不可能知道一个问题的 所有算法——理论上存在无限多。

下界不会给你一个好算法。 它们只帮助你了解何时该停止寻找。 如果问题的下界与算法的上界相符（在常数因子内）， 那么我们知道我们最多能期望的 是找到一个好一个常数因子的算法。 我们通常不为此操心。

下界能告诉我们一个算法是否不是最优的吗？ 不能，抱歉！ 为什么不能？ 因为我们可能没有最紧的可行下界！

让我们来确定汉诺塔的下界。 我们选择首先讨论这个问题，还有一个原因 是问题下界代价是"显然"的。 所以现在我们可以完全专注于证明数学的技巧， 而不是琢磨该分析什么。

对我们第一次尝试下界证明而言，"平凡"下界 是我们必须至少移动每个圆盘一次，最小代价为 \(n\)。 稍好一点的是观察到，要把底层圆盘送到第三根柱子， 我们必须把每个其他圆盘至少移动两次（一次把它们移开 底层圆盘，一次把它们移到第三根柱子）。 这给出 \(2n - 1\) 的代价，这仍然与我们的算法 不太匹配。 问题出在算法里还是下界里？

我们可以通过下面的推理得到正确的下界： 要把最大的圆盘从第一根柱子移到最后一根，我们必须首先 让其他所有 \(n-1\) 个圆盘让出路来，而这样做的唯一 办法是把它们都移到中间的柱子（代价至少是 \(\textbf{T}(n-1)\)）。 然后我们必须移动底层圆盘（代价至少为 1）。 之后，我们必须把 \(n-1\) 个剩余的圆盘从中间的柱子 移到第三根柱子（代价至少是 \(\textbf{T}(n-1)\)）。 因此，任何算法都无法在少于 \(2^n-1\) 步内解决问题。 因此，我们的算法是最优的。

1.2.5. 新模型¶

如果我们决定改变模型，就需要把整个 过程再做一遍。 有时，如果我们的原始问题在某种程度上太难， 而我们能接受求解一个不同（更容易）的问题， 我们就想改变模型。 有时我们想改变模型是因为我们的需求变了。

新模型 #1：我们可以在一次移动中移动一整摞圆盘。 这是个大帮助！\(O(n)\) 甚至 \(O(1)\)。

新模型 #2：不是所有圆盘都从柱子 A 开始。 这似乎不改变问题的代价。（为什么？）

把这两点结合起来，代价看起来是 \(O(n)\)。

新模型 #3：柱子数量不同。

新模型 #4：我们想知道第 \(k\) 次移动是什么。

1.2.6. 把它们放在一起¶

所以现在我们有了问题 "我怎么知道我是否有一个求解问题的好算法？"的答案。 如果一个算法的上界匹配问题的下界，那它就是好算法 （从渐近意义上讲）。 如果它们匹配，那么我们就知道该停止寻找（渐近意义上）更快的 算法了。 如果我们（已知的）算法上界并不匹配 问题的（已知）下界呢？ 在这种情况下，我们可能不知道该怎么办。 是我们的上界有问题，而算法实际上比我们能证明的更快吗？ 是我们的下界太弱，而问题的真正下界更大？ 还是我们的算法根本不是最好的？

注意这与 \(\Theta\) 记法的相似性。 当 \(f(n) \in \Omega(g(n))\) 且 \(f(n) \in O(g(n))\) 时， 我们说 \(f(n) = \Theta(g(n))\)。 换句话说，如果代价函数的上下界 在常数因子内会合，我们就"真正理解了" 这个代价函数。 同样，当问题代价的上下界会合时， 我们就说我们"理解"了那个问题的代价。

现在我们精确地知道设计算法时我们在瞄准什么： 我们要找上界匹配问题下界的算法。 把我们迄今所知的所有关于算法的知识放在一起，我们可以 把我们的思考组织成下面的"设计算法的算法"。

我们可以重复这个过程，直到我们满意或 筋疲力尽。

这让我们迎面撞上分析中最艰巨的任务之一。 下界证明以难以构造而闻名。 问题在于想出真正涵盖 任何 算法 可能 做的一切的论证。 最常见的谬误是从某个好算法 确实那样做的 角度来论证， 并声称任何算法都必须做同样的事。 这根本不对，任何提及必须发生的特定行为的 下界证明都应受到某种怀疑。

这把我们带回用来为汉诺塔下界辩护的论证。 它本质上是对必然行为的论证。 汉诺塔相当罕见，因为确实有一些我们知道 必然发生的具体行为。 在这个特定情况下，这个问题受到如此严格的约束， 以至于对这一连串的事件确实没有（更好的）替代方案。 这种方法对大多数问题都不适用。

我们的"问题求解算法"总是会终止吗？ 不会。 如果你走一遍而没有取得进展，你可能会陷入循环。 那么，它是个算法吗？