第 08 章

动态规划——一位数学家为什么给自己的伟大发明起了个奇怪的名字？

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1949—1958年 · RAND 公司、多阶段决策、最优性原理与动态规划1950年，美国，加利福尼亚州圣莫尼卡。一位30岁的数学家，正试图解决一类极其困难的问题。他所研究的并不是一道简单的数学方程。而是一连串相互影响的决策。假设你负责管理一家工厂。你必须决定今天生产多少产品、明天储备多少原料、后天如何安排运输。困难在于：今天的决定会改变明天的资源。明天的决定又会影响后天的选择。如果每一天都有十种可能的决策，连续100天，总共存在多少种决策序列？

10^{100}

这是一个大到难以想象的数字。即使拥有今天的超级计算机，也不可能简单地把所有方案逐一列举出来。于是，这位数学家开始研究：能不能不枚举全部决策序列，却仍然找到整个过程中的最优方案？他的名字叫作 Richard Bellman。他后来将这种研究方法命名为：Dynamic Programming，动态规划。然而，更有趣的事情还在后面。多年之后，他在自传中解释过这个名称的由来，竟然牵涉到美国国防部长、研究经费，以及当时的政治环境。而且，我们今天通常把动态规划理解为“保存计算过的结果，避免重复计算”，这其实只说对了一部分。Bellman 真正想解决的问题，是怎样把一连串相互依赖的决策，拆解成可以逐阶段求解的小问题。

第一幕：一个数学家走进冷战时期的智库

位于加州圣莫尼卡的 RAND 早期办公大楼，1953年前后的历史影像。Richard Bellman 1920年出生于纽约。他年轻时学习数学，后来在普林斯顿大学攻读博士，并于1946年获得博士学位。他的博士导师是著名数学家 Solomon Lefschetz（所罗门·莱夫谢茨）。Bellman 在微分方程、数学分析和应用数学方面接受了严格训练。但20世纪40年代的数学世界，正在发生变化。第二次世界大战期间，大规模工程与军事研究越来越依赖数学。飞机如何分配资源？怎样安排复杂的生产计划？面对不确定的情况，怎样选择最优行动？这些问题催生了运筹学（Operations Research）的发展。1948年，RAND Corporation 成为独立的非营利研究机构，其研究与美国空军有密切联系。RAND 吸引了数学家、经济学家、工程师和其他研究人员，希望利用系统分析解决复杂决策问题。^{[MacTutor History of Mathematics][PubsOnline]}

1949年，Bellman 遇见了一类新的数学问题

Bellman 后来回忆，1949年夏天，他非常希望到 RAND 工作。在那里，他认识了 Edward Paxson。Paxson 建议他研究多阶段决策过程（Multistage Decision Processes）。Bellman 对这个方向产生了兴趣。这个建议，后来成为他研究生涯最重要的转折点之一。^[PubsOnline]我们可以用一个教学情境来理解它。假设 RAND 的研究人员需要为一个复杂系统制定计划。系统共有五个阶段。每个阶段都必须选择一种操作。

一个多阶段决策系统

查看 SVG 配图原件

08-003.svg · 点击查看大图

每次决策都会消耗资源、改变状态。所以，你不能孤立地决定“今天怎样最好”。因为今天最好的选择，可能让明天陷入困境。Bellman 需要一种数学方法，把局部决策与全局最优联系起来。

第二幕：1952年，一篇只有几页的论文揭示了核心思想

1952年，Bellman 在美国科学院院刊发表了一篇论文：On the Theory of Dynamic Programming《论动态规划理论》。论文由 John von Neumann 于1952年6月5日提交给期刊，发表于同年8月。论文开头讨论了这样一类问题：通过一系列操作实现目标，要求最大化收益，或者最小化时间、费用等代价。^{[derongliu.org]}

1952年历史原始文献

Richard Bellman，On the Theory of Dynamic Programming，Proceedings of the National Academy of Sciences，38(8)，716–719。阅读原始论文 PDF

Bellman 意识到，一个复杂的最优决策过程，有时可以通过研究当前最优行动与后续最优行动之间的关系来求解。后来，这种思想被系统化为著名的：最优性原理（Principle of Optimality）。其核心含义可以概括为：在满足适当条件的多阶段决策问题中，一条最优策略从任意后续状态开始，剩余部分也必须是相应后续问题的最优策略。听起来有点抽象。但我们马上就会理解。

假设你在规划一场旅行

你需要从城市 A 到城市 D。路线：

查看 SVG 配图原件

08-004.svg · 点击查看大图

示意道路长度：A—B=2，A—C=5，B—C=1，B—D=6，C—D=2。

假设最短路径是：A → B → C → D距离为：

2+1+2=5

那么从 B 到 D 的后半段：B → C → D距离为3。如果 B 到 D 之间实际上还存在一条距离为2的路线，我们就可以替换原路径的后半段，得到一条更短的 A 到 D 路线。这会与原路径已经最短相矛盾。因此：一条最短路径的后续部分，本身也必须是对应子问题的最短路径。这就是最优子结构（Optimal Substructure）。但要注意：并不是所有问题都天然满足这种可以直接分解的性质。有时我们必须把已访问节点、剩余资源等历史信息加入状态，才能正确应用动态规划。

从数学思想到递推公式

假设

F(s)

表示：从状态

s

出发，未来能够获得的最大收益。当前可选择动作

a

。执行后得到即时收益

r(s,a)

，并进入状态

T(s,a)

。那么在确定性、有限阶段且没有额外终止约束的简化模型中：

\boxed{F(s)=\max_a\{r(s,a)+F(T(s,a))\}}

这就是 Bellman 方程最典型的形式之一。读起来其实很简单：当前能得到的最优结果 = 在所有可选行动中，选择“当前收益 + 后续最优收益”最大的那个。你可能已经发现：这与我们之前学过的递归，非常相似。但一个真正重要的差别正在出现。

第三幕：为什么“动态规划”这个名字听起来不像数学？

Bellman 后来写了一本自传，名为 Eye of the Hurricane: An Autobiography（《飓风之眼》），出版于1984年。在书中，他专门解释了为什么使用 Dynamic Programming 这个名称。这是一段真实存在的研究者回忆，而不是后人杜撰的传奇。

名字背后的政治环境

Bellman 回忆说，当时美国国防研究的政治环境并不总是欢迎抽象数学研究。他特别提到一位国防部长 Wilson。按照 Bellman 的说法，Wilson 对 Research（研究）这个词很反感，更不用说 Mathematical Research（数学研究）。因此，Bellman 希望给自己的工作选择一个不容易招致反对的名称。他选择 Programming，是因为自己研究的是计划、决策和行动安排。又选择 Dynamic，是为了体现问题具有动态变化、多个阶段和时间演进的特点。他认为，这样一个听起来积极、实用的名称，很难被人直接反对。于是，Dynamic Programming 就出现了。^{[PubsOnline][Yaoliang Yu's Webpage]}但这里有一个必须仔细核对的历史细节。Bellman 在自传中谈到1950年于 RAND 的研究经历，同时用 Wilson 担任国防部长的环境解释命名。然而，美国国防部官方记录明确显示，Charles Erwin Wilson 的国防部长任期是 1953年1月28日至1957年10月8日。而 Bellman 的动态规划论文在1952年就已经发表。^{[history.defense.gov][derongliu.org]}所以，不能简单写成“1950年 Bellman 因为当时的 Wilson 国防部长而发明了这个名字”。更准确的理解是：

Bellman 的命名故事确实来自本人晚年的回忆。
当时对数学研究与研究经费的政治顾虑可以构成其叙述的一部分。
但自传把不同年份的经历联系起来，存在明显的时间线问题；Wilson 不能直接解释1952年前已经使用的名称。

这也是研究真实算法史时特别值得注意的事情：即使是发明者本人的回忆，也需要与原始论文和官方时间记录相互核对。

Programming 并不意味着写代码

这还关系到一个常见误解。在 Dynamic Programming 这个名称中，Programming 原本更接近“计划编制”“最优化决策”，而不只是今天所说的写程序。所以，动态规划不是因为用了 Python 的循环或者数组才得名。它首先是一种解决多阶段决策问题的数学方法。1957年，Bellman 出版了专著 Dynamic Programming，系统阐述这个领域。这本书讨论的问题包括资源分配、库存管理、随机决策、瓶颈问题，以及多阶段过程等。^{[MacTutor History of Mathematics][Google Books]}接下来，我们先不讨论复杂的运筹学模型。而是从你熟悉的 Python 递归开始，看一个极为简单的数学问题如何暴露出严重的计算浪费。

第四幕：一只兔子，让计算机开始不断重复劳动

1202年，意大利数学家 Fibonacci 在《计算之书》（Liber Abaci）中讨论了一个著名的兔子繁殖问题。后来，这一问题对应的数列以他的名字命名。我们今天熟悉的斐波那契数列是：

0,1,1,2,3,5,8,13,21,\ldots

它满足：

F(n)=F(n-1)+F(n-2)

其中：

F(0)=0,\quad F(1)=1

这是一个非常自然的递归定义。于是我们写出 Python 程序：

def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

代码只有几行。看起来非常优雅。但它存在一个严重问题。

计算 F(5) 时，到底发生了什么？

F(5) 的递归调用树

查看 SVG 配图原件

08-006.svg · 点击查看大图

同一个 F(3) 在不同分支中被重复调用。图示省略了 F(2) 继续展开的少量子分支。

发现没有？为了计算 F(5)，我们计算了一次 F(4) 和一次 F(3)。但 F(4) 又需要计算 F(3)。于是 F(3) 被重复计算。F(2) 被重复计算得更多。这个递归过程仿佛患上了一种“健忘症”：它每次完成一项任务，都会立刻忘记答案。等下次遇到相同问题，又从头开始。这不是递归本身的错误。而是因为许多分支重复依赖相同的子问题。

实验一：究竟重复计算了多少次？

递归调用计数器

朴素递归 vs 记忆化

真实调用次数

计算 F(10)

55

朴素递归调用次数

177

真正不同的子问题

11

每个子问题被计算的次数

F(10)

1 次

F(9)

1 次

F(8)

2 次

F(7)

3 次

F(6)

5 次

F(5)

8 次

F(4)

13 次

F(3)

21 次

F(2)

34 次

F(1)

55 次

F(0)

34 次

这是实际递归调用树的统计，不是根据运行时间估算。图中最多显示 F(0) 至 F(10) 的调用频次。

当你把

n

从10调整到20时，就会看到，调用次数增长得非常快。朴素斐波那契递归的时间复杂度为：

O(\varphi^n)

其中：

\varphi=\frac{1+\sqrt5}{2}\approx1.618

这是一种指数级增长。可是，真正不同的子问题只有：

F(0),F(1),\ldots,F(n)

一共

n+1

个。也就是说：我们实际上只需要解决 $n+1$ 个不同的问题，却因为忘记答案而进行了大量重复计算。于是，一个几乎自然而然的想法出现了。为什么不把计算过的结果保存起来？

第五幕：给递归装上一块记忆

我们创建一个字典：

memo = {}

每次计算前，先检查结果是否已经存在。如果存在，直接返回。如果不存在，计算后把结果保存起来。

def fib(n, memo=None):
    if memo is None:
        memo = {}

    if n <= 1:
        return n

    if n in memo:
        return memo[n]

    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)

    return memo[n]

这一改动看起来非常微小。但它改变了整个算法的复杂度。因为每个子问题只需要真正计算一次。最终：

\boxed{O(n)}

相比指数级递归，这可能是巨大的性能提升。

但是，动态规划不只是缓存

我们必须区分三个概念。递归（Recursion）：函数把问题分解成结构相同、更小的子问题。记忆化（Memoization）：把已经求解过的子问题答案缓存起来，避免重复计算。动态规划（Dynamic Programming）：利用问题的状态、转移关系与最优子结构，组织整个多阶段求解过程；记忆化是实现动态规划的一种常见方式。并不是所有带缓存的递归都属于最优化意义上的动态规划；也不是所有动态规划都必须使用递归。例如，我们还可以从最小的问题开始，一步步向上计算。

自底向上的动态规划

def fib(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)

    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

这里的 dp[i] 就是一张记录子问题答案的表。你可能会问：为什么叫 DP Table？因为我们把不同状态的解按依赖顺序填入表格，后面的状态可以直接使用前面的结果。而且还有一个更有趣的优化。如果求 F(n) 只需要前两个结果，为什么要保存整个数组？

def fib(n):
    a, b = 0, 1

    for _ in range(n):
        a, b = b, a + b

    return a

时间复杂度仍然是

O(n)

，但按固定大小整数运算的常见算法分析，额外空间可以视为

O(1)

。在 Python 中，大整数的位数会随

n

增长，因此如果严格按比特数计算，整数本身占用的空间和算术成本不能忽略。这就引出动态规划中的另一个重要技巧：状态压缩（Space Optimization）。只保留未来计算真正需要的历史状态。

第六幕：1953年，Bellman 研究的远不止一道递归题

我们重新回到 RAND。Bellman 面临的真实问题，不是求斐波那契数列。而是资源分配、最优控制、库存管理、生产计划等多阶段决策问题。1953年，他发表了 Bottleneck Problems and Dynamic Programming（瓶颈问题与动态规划）。1954年，他又发表多篇论文，进一步说明动态规划在不同决策问题中的应用。^{[PubMed][PubsOnline]}如果要找一个最贴近 Bellman 研究精神、同时又适合程序员动手的例子，那么经典背包问题非常合适。但要强调：下面是教学模型，不是复刻 Bellman 当年的某项具体 RAND 项目。

假设你负责一架飞机的物资装载

飞机能够额外携带的重量只有7单位。仓库中有四件物资：

物资	重量	价值
医疗箱	2	6
通信设备	3	10
工具箱	4	12
备用电池	5	15

每件物资最多只能带一件。你希望：总重量不超过7，同时让总价值最大。最简单的方法是枚举所有组合。四件物品有：

2^4=16

种选择。那如果有100件物品呢？

2^{100}

这就是我们在序幕中遇到的指数级决策空间。怎么办？

第七幕：背包问题——把巨大的选择空间压缩成一张表

我们先定义一个状态。

dp[i][w]

表示：只考虑前 $i$ 件物品，在背包容量不超过 $w$ 时，可以获得的最大价值。假设第

i

件物品重量为

weight_i

，价值为

value_i

。我们只有两个选择。不带这件物品：

dp[i-1][w]

如果容量足够，也可以选择带上它：

dp[i-1][w-weight_i]+value_i

取两者最大值：

\boxed{dp[i][w]=\max\big(dp[i-1][w],dp[i-1][w-weight_i]+value_i\big)}

如果物品太重，装不进去，就只能不带。这就是一个非常典型的 Bellman 式决策：每一阶段都比较当前行动与后续状态所带来的整体最优结果。

实验二：你来决定带什么

背包决策实验室

0/1 Knapsack · 每件物品只能选择一次

最大承载重量7

医疗箱

重 2价值 6

通信设备

重 3价值 10

工具箱

重 4价值 12

备用电池

重 5价值 15

当前装载重量0 / 7

你的选择价值

0

动态规划最优价值

22

目前还有改进空间。尝试换一组物资，或者查看动态规划计算出的组合。

你可以试着把容量设成7。最优方案之一是：医疗箱 + 备用电池。重量：

2+5=7

价值：

6+15=21

而通信设备加工具箱也是一种合法方案：重量7，价值22。因此，真正最优的是后者：

\boxed{22}

这很有代表性：只看单件价值，或者只看每单位重量的价值，都不能保证得到0/1背包问题的全局最优解。动态规划却能通过逐状态比较，找到正确答案。

看看 Bellman 方程如何落在 Python 里

def knapsack(weights, values, capacity):
    n = len(weights)

    dp = [[0] * (capacity + 1)
          for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]

        for w in range(capacity + 1):
            # 不选第 i 件物品
            dp[i][w] = dp[i - 1][w]

            # 选择第 i 件物品
            if weight <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - weight] + value
                )

    return dp[n][capacity]

如果共有

n

件物品，背包容量为整数

W

，那么时间复杂度是：

O(nW)

空间复杂度是：

O(nW)

这里有一个值得深入思考的问题。

O(nW)

看起来像多项式时间。但如果

W

是一个非常大的数，比如

10^{12}

，算法仍然可能无法实际运行。因此，这类按数值大小而非输入位数呈多项式增长的算法，被称为伪多项式时间算法（Pseudo-polynomial Time）。这是算法分析中非常重要的一层认识：动态规划不保证所有问题都变成真正意义上的多项式时间。它能否高效，取决于状态空间到底有多大。

第八幕：1958年，Bellman 与 Dijkstra 走上了不同的道路

上一章，我们讲过1956年 Dijkstra 在阿姆斯特丹咖啡馆中构思最短路径算法的故事。现在，一个很有意思的历史交汇发生了。Dijkstra 在1956年提出算法，1959年发表论文。而 Bellman 于1958年发表了：On a Routing Problem（论一个路径规划问题）。其中，他研究的同样是城市之间的最短路径。^{[数字对象标识符]}但 Bellman 与 Dijkstra 采用了不同的思想。

Dijkstra：不断确定当前最短的节点

前一章我们学过：在非负权图中，Dijkstra 每次选择暂定距离最小的节点，将它的距离确定下来。这种方法非常适合贪心策略。可是，如果边权允许为负数呢？例如：

查看 SVG 配图原件

08-007.svg · 点击查看大图

从 A 直接到 C，代价是2。但如果走：A → B → C总代价是：

4+(-5)=-1

显然更短。因此，假如过早确定 C 的距离，就会得到错误结论。Bellman 的思路更接近于：不断利用已经知道的路径信息，改进其他节点的距离。

一次又一次地放松边

定义：

dist[v]

表示当前已知从起点到顶点

v

的最小路径代价估计。对于边

u\rightarrow v

，权重为

w

：如果：

dist[u]+w<dist[v]

那么更新：

dist[v]=dist[u]+w

这个过程叫作松弛（Relaxation）。只要图中不存在从起点可达的负权环，最短路径可以通过反复松弛得到。对于拥有

V

个顶点的图，经典 Bellman–Ford 算法通常进行至多

V-1

轮完整松弛，再通过额外一轮检查可达负权环。时间复杂度：

O(VE)

历史上，这类方法并非仅由 Bellman 一个人发明。Lester Ford 在1956年研究网络问题时提出过相关方法，Alfonso Shimbel 更早也有相近工作。1958年 Bellman 则从动态规划的思想出发给出了重要形式。^{[dml.cz][research.engineering.nyu.edu]}这段历史非常值得玩味。两位数学家研究同一个最短路径问题，却采用了不同的组织方式：

	Dijkstra	Bellman–Ford
核心策略	贪心确定最近节点	反复松弛边
允许负权边	一般不支持	支持
可达负权环	不适用	可以检测
常见复杂度	$O((V+E)\log V)$	$O(VE)$
历史路线	图搜索与贪心	多阶段递推与动态规划

不存在一位永远胜利的发明者。只有不同问题约束下更适合的方法。

第九幕：Bellman 后来发现，动态规划也有一个可怕的敌人

1957年，Bellman 的著作《Dynamic Programming》正式出版。在这本书中，他系统阐述了最优性原理及其在控制、库存、资源配置和多阶段随机决策中的应用。但他也越来越清楚地认识到一个困难。动态规划能够避免重复求解相同状态。可是，如果状态本身太多怎么办？假设一个系统需要记录两个状态变量，每个变量有100种可能：

100^2=10,000

如果有五个变量：

100^5=10^{10}

如果有十个变量：

100^{10}=10^{20}

即使每种状态只计算一次，也根本存不下这么庞大的状态表。这种随着维度增加、状态空间迅速膨胀的现象，被 Bellman 称为：维度灾难（Curse of Dimensionality）。它后来成为控制理论、数值优化、机器学习与强化学习中的重要难题。

看看状态空间如何爆炸

维度灾难模拟器

状态变量数量3

每个变量的可选值10

全部状态组合数量

1,000

状态数 = 10^3

即使没有重复计算，如果每个状态必须保存一个结果，维度增加仍可能让动态规划无法实际运行。

这也是我们今天理解动态规划时必须记住的边界：它没有消除复杂性。它把原问题的复杂性转化为状态空间与状态转移的复杂性。如果状态设计得不好，或者状态本身过多，动态规划也可能非常昂贵。因此，一个真正优秀的动态规划解法，往往最难的不是写代码，而是：找到足够少、又包含全部必要信息的状态。

第十幕：为什么我们今天学习的 DP，与 Bellman 当年研究的并不完全一样？

现在我们可以把这段历史与现代算法教学连接起来了。Bellman 当年研究的是多阶段决策、最优控制和运筹学。我们今天在算法课程或编程题中遇到的 DP，则经常是：

爬楼梯。
最长公共子序列。
最长递增子序列。
编辑距离。
0/1背包。
矩阵链乘法。
区间 DP。
树形 DP。

它们看起来千差万别。但核心联系都是：把原问题表达成一组具有依赖关系的状态，再以正确的顺序计算状态之间的转移。就像前面七章的学习一样，我们不应该只记住某一段 Python 代码。而应该尝试回答四个问题。

识别动态规划的四个关键问题

状态是什么？ 需要记录哪些信息，才能完整描述当前子问题？
状态怎样转移？ 当前答案依赖哪些更小的子问题？
边界条件是什么？ 最小的问题应该如何直接求解？
怎样安排计算顺序？ 使用记忆化递归，还是自底向上填表？能否压缩空间？

如果这四个问题回答清楚了，动态规划的代码通常就不难写。反过来，如果根本没有定义清楚状态，那么代码写得再多，也只能是在碰运气。

终章挑战：Bellman 会怎样选择？

假设你要爬上6级台阶。每次只能爬1级或2级。问：共有多少种不同的爬法？我们先不直接给出结果。考虑最后一步。如果最后一步爬了1级，那么此前必须已经到达第5级。如果最后一步爬了2级，那么此前必须已经到达第4级。因此：

dp[6]=dp[5]+dp[4]

一般地：

dp[n]=dp[n-1]+dp[n-2]

并设：

dp[0]=1,\qquad dp[1]=1

这里

dp[0]=1

表示“不采取任何步骤”也算一种完成零级台阶的方法。

第6级台阶共有多少种爬法？

8种13种21种32种

仔细观察这个问题：它与斐波那契数列几乎完全一样。只不过状态的含义发生了变化。在斐波那契数列中，

F(n)

表示第

n

个数值。在爬楼梯问题中，

dp[n]

表示到达第

n

级的不同方法数量。但状态转移方程具有同样的形式。这说明：不同现实问题，有时可以共享同一个数学结构。而识别这种结构，正是算法能力提高的重要标志。

尾声：一位数学家留下的，不只是“记忆化”技巧

1965年，Bellman 离开 RAND，加入南加州大学。后来，他继续研究控制理论、数学分析和各种实际决策问题。1979年，他获得 IEEE 荣誉奖章，表彰其在决策过程与控制系统理论方面的贡献。1984年，Bellman 去世，享年63岁。^{[MacTutor History of Mathematics][Dover Publications]}

回顾这一章，我们见证了一个重要思想的成长。Bellman 最初并不是为了让 Python 递归跑得更快。他研究的是多阶段决策，是如何把一个庞大的优化问题拆解成可以组织、分析和求解的部分。后来，动态规划逐渐进入更多领域。今天，它不仅用于算法竞赛和软件开发，也深刻影响着最优控制、经济决策、运筹学以及强化学习。其中强化学习中的价值函数和 Bellman 最优方程，更是直接继承了他的数学思想。但这门方法的核心依然可以浓缩为一句话：不要反复求解已经解决过的问题，也不要孤立地做眼前的决策；要理解当前状态如何依赖未来或过去的最优结果。

第八章知识总结

概念	核心思想
多阶段决策	当前行动影响后续状态
最优性原理	最优策略的后续部分也必须最优
状态 State	完整描述一个子问题
状态转移	使用其他状态的答案求解当前状态
Memoization	缓存已计算的子问题
Bottom-up DP	按依赖顺序填表
状态压缩	只保存必要的中间结果
维度灾难	状态数量随维度迅速膨胀

本章真实历史资料

Bellman 1952年原始论文《On the Theory of Dynamic Programming》Stuart Dreyfus：Bellman 对动态规划诞生过程的回忆（2002）MacTutor 数学史档案：Richard Bellman 生平美国国防部官方历史：Charles E. Wilson 任期 Bellman 1958年论文《On a Routing Problem》

下一章预告

第九章：贪心算法——为什么眼前最好的选择，有时能创造全局最优？

上一章我们了解到，多阶段问题往往需要考虑未来的影响。但有些时候，数学家发现一个令人惊讶的事实：只需要在每一步选择当前最好的行动，就能够获得整个问题的最优解。1956年，Joseph Kruskal 发表最小生成树算法。1957年，Robert Prim 发表相关算法的重新发现与应用研究；这一方法还有更早的历史来源，可以追溯到1930年的捷克数学家 Vojtěch Jarník。这一次，我们将研究为什么要把很多城市连接成一张网络，既保证所有城市互相连通，又让铺设线路的总成本尽可能低。更令人惊讶的是，某些局部最优选择竟然可以被严格证明永远不会妨碍最终的全局最优。这就是贪心算法真正迷人的地方：它看起来像是在冒险，但数学证明让它变得可靠。