英语原文共 86 页，剩余内容已隐藏，支付完成后下载完整资料

---

附录X 译文

动态规划

我们从贪婪算法开始关于算法技术的研究，贪心法在某种意义上形成了最自然的算法设计方法。面对一个新的计算问题，我们已经看到，不难提出很多种贪心算法；然而，挑战是确定是否这些算法对问题所有的实例提供了一个正确的解决方案。

我们在看到的问题全都是与这个事实一致的，在最后，确实有一个贪心算法，不幸的是，一般来说这与真实情况相差很远；对人们遇到的大多数问题，真正的困难不在于确定哪些贪婪策略是正确的，而是事实上，不存在有效的贪心算法。对于这样的问题，重要的是有其他方法在手。分制策略有时可以作为一种替代的方法，但是我们在前面的章节中看到的往往不够强大，以减少指数蛮力搜索到多项式时间。相反，正如我们在第5章中提到的，那里的应用程序，它们倾向于把不一定很大且已经多项式的运行时间减少到更快的运行时间。

我们现在转向一个更强大和微妙的设计技术，动态规划。可以说正是刻画动态亲编程在我们的行动中看到它，但其基本思想是从直觉背后的分治策略，本质上是相反的贪婪策略：人们通过细心的把事情分解为一系列子问题，然后对越来越大的问题建立正确的解决方案。从而隐含的探查所有可行解的空间，于是我们可以在某种程度上进行系统的工作，把动态规划看作接近蛮力搜索边缘的危险操作：虽然它的系统的工作主要通过指数大集的解决问题的办法，但它没有明确检查所有的了解就做到这一点。正是因为这种谨慎的平衡行为，动态规划可以是一个复杂的技术，在人们完全适应它以前，一般需要进行一定量的实践。

考虑到这一点，我们现在转向的第一个动态规划的例子：带权区间调度问题，我们定义在第1.2节。我们将开发一个动态规划算法在两阶段问题：首先看作一个类似于蛮力搜索的递归过程；然后通过重新解释这个过程，把它作为由建立越来越大的子问题的解而工作的迭代算法。

1.1带权区间调度：一个递归过程

我们已经看到，一个特定的贪心算法产生的区间调度问题的最优解，其目标是在接受最大的不重叠区间的集合。带权区间调度问题严格的说是一个更一般的问题，其中每个区间有一定的值（或者权），并且我们要接收一个最大值的集合。

1.1.1设计一个递归算法

因为初始的区间调度问题只不过是所有值都等于1的特殊情况，我们已经知道很多数贪心算法不能优化地求解这个问题．甚至以前有效的算法（重复选择结束最早的区间）在这个更为一般的环境下也不再是优化的，正如图1.1的例子所示。

图1.1 一个带权区问调度的简单实例

的确，对这个问题还没有过自然的贪心算法，它就是推动我们转向动态规划的问题,正如前面讨论的，我们将对这个问题开始引入带有递归算法类型的动态规划，然后在下一节我们将转向一个多次迭代的方法，它更接近于我们在这一章其余部分所使用的风格。

我们使用在1.2节区间调度讨论中的符号，我们有n个需求，标记为1，2，hellip;，n，每个需求指定一个开始时间与一个结束时间．每个区间i现在还有一个值或者权。如果两个区间不重叠，那么它们是相容的，当前问题的目标是选择一个两两相容的区间的子集S {1，hellip;，n}，以使得所选区间的值之和最大。

• 让我们假设需求按照结束时间非降的次序排列：le;le;hellip;如果ilt;j，我们说需求i在需求j之前来到．这将是自然的从左到右的次序，我们将按照这个次序考虑区间，为了有助于提及这个次序，我们对区间j定义p(i)为使得区间i与j不相交的最大的标记ilt;j．换句话说，i是最右边的在j开始之前结束的区间。如果没有需求ilt;j与j不相交，那么我们定义p(j)=0.p(j)定义的一个例子如图1.2。

图1.2 对于每个区间j具有被定义函数p(j)的一个带权区间调度的实例

现在，给定一个带权区间调度问题的实例，让我们考虑一个最优解O，尽管到现在我们还不知道它是什么．这里是我们关于O可说的完全显而易见的东西：区间n（最后一个区间）属于O或者不属于O）．假设我们进一步检查一下这种二分的两个方面．如果，nisin;O．那么很清楚没有标记严格处于p(n)与n之间的区间能够属于O，因为根据P(n)的定义，我们知道区间p（n） 1，p（n） 2．hellip;，n-1全都与区间n重叠．此外，如果，nisin;O，那么O一定包含对于由需求{1，hellip;，p(n)}所组成问题的一个最优解。若不然，我们可以把O对{1．hellip;，p(n)}中需求所做的选择换成一个更好的选择，这并不构成与需求n重叠的危险。

另一方面，如果nO，那么O只等于对需求{1．hellip;，n-1}所组成问题的最优解。这是由完全类似的推理：我们假定O不包含需求n；于是如果它不从{1．hellip;，n-1}选择最优的需求集合，那么我们可以用更好的集合替换它。

所有这些都使人想到求区间{1，2，hellip;，n）上的最优解包括查看形如{1，2，hellip;，j}的较小问题的最优解。于是，对于任意在1与n之间的j值，令表示对于由需求{1，hellip;，j}所组成问题的最优解，并且令OPT(j)表示这个解的值（基于对于区间的空集上的最优解的约定，我们定义OPT(0)=0)．我们正在寻找的最优解正好是，对于{l，2，hellip;，j}上的最优解，我们上面的推理（从j=n的情况加以推广）说，或者jisin;，在这种情况下，

OPT(j)=OPT(j-1)，由于这些正好是两种可能的选择（jisin;），我们可以进一步说：

我们怎样决定j是否属于最优解？这也是容易的：它属于最优解当且仅当上述第一个最优至少与第二个一样好；换句话说，

定理1.2 需求j属于集合{1，2，hellip;，j}上的最优解当且仅当

这些事实构成动态规划求解基础的最重要的部分：按照对于较小子问题的最优解（或者它的值）的一个递推的等式。

先不管导致这一点的简单推理．1.1式 已经是一个重要的改进．假定我们已经按照结束时间对需求排好序并且对每个j计算了p(j)的值，那么它已经给出一个计算OPT（n）的递归算法。

Compute-Opt (j)

If j=0 then

返回O

Else

返回max( Compute-Opt( p(j)) ,Compute-Opt(j-1))

End if

算法的正确性直接由在j上的归纳得到。

定理1.3 对每个j=1，2，hellip;，n，Compute-Opt(j)正确的计算了OPT（j）

证 用归纳法，OPT(0)=0．现在，取某个jgt;0．并且根据归纳法假设我们知道Compute-Opt(i)对于所有的ilt;j正确计算了OPT(i)。由归纳假设，我们知道Compute-Opt（p(j)）=OPT（j）且Compute-Opt(j-1)=OPT( j-l)；因此由定理1.1得：

OPT (j) = max ( Compute- Opt (p (j)), Compute- Opt (j-1))

= Compute-Opt (j).

遗憾的是，如果我们真按所写的实现这个算法Compute—Opt，在最坏情况下它将用指数时间运行．例如，看图6.3的调用树，这是由图1.2的实例生成的：由于递归分支，快速加宽．为了取一个更大的例子，在像图1.4中那个良好分层的实例上，其中对每个j=2，3，4，hellip;，n．p(j)=j-2，我们看到Compute-Opt(j)在规模j-1与j-2的问题上生成单独的递归调用．换句话说，在这个实例上对Compute-Opt所做的调用总数将像指数增长的F bonacci数，于是我们没得到一个多项式时间的解。

图1.3 由Compute-Opt在图1.2的实例上所调用的子问题树

图1.4 带权区间调度的一个实例，其中简单的Compute-Opt递归将用指数 时间．在这个实例中所有区间的值都等于1

1.1.2 递归的备忘录形式

可是事实上我们并不是没有一个多项式时间的算法。一个基本观察构成了动态规划求解的第二个重要的部分，那就是我们的递归算法Compute-Opt实际上只求解了n 1个不同的子问题：Compute-Opt(0)，Compute-Opt (1)，hellip;，Compute-Opt（n）．上面所写的它运行在指数时间的事实只是由于它产生每个这种调用的次数有巨大的冗余。

我们怎样能删除所有这些冗余？我们可以在第一次计算它时就Compute-Opt值存在一个大家都可访问的地方，然后在所有后来的递归调用中只是使用这些预先算好的值．这个存储已算好的值的技术叫做备忘录。

我们用一个更“聪明”的过程M-Compute-Opt改进上述策略．这个过程将用到一个数组M[0hellip;n]；开始M[j]将具有值“空”，但是一旦Compute-Opt(j)的值被确定，就把它保留起来，为确定OPT(n)，我们调用M-Compute-Opt（n）。

M- Compute- Opt (j)

If j = 0 then

返回 0

Else if M[j] is not empty then

返回 M[j]

Else

定义M[j] = max( M- Compute- Opt (p(j)), M- Compute- Opt (j-1))

返回M[j]

End if

1.1.3 分析备忘录方法

显然这看起来与我们前面的算法实现非常相似；但是，备忘录已经把运行时间大大地降下来了。

定理1.4 M-Compute-Opt(n)的运行时间是O(n)（假定输入区间按他们的最后存时间存储）

证 若不计它生成的递归调用中的时间，对M-Compute-Opt的一次调用所用的时间是O(1)．因此运行时间由对M-Compute-Opt所产生的调用次数的常数倍来界定．因为实现本身没有明确给出这个调用次数的上界，我们尝试通过寻找一个好的“进展”度量来求一个界。

这里最有用的进展度量就是在M中不“空”的项数．初始这个数是0；但是每次过程调用这个递推式，产生两个对M-Computer-Opt的递归调用，它填入一个新项，因此填入的项数增加1．由于M只有n 1个项，从而得出至多存在O(n)次对M-Compute-Opt的调用，于是M-Compute-Opt的运行时间是O(n)，正如所求。

1.1.4 除了值之外再计算一个解

至此我们只是计算了一个最优解的值；大概我们也想要一组最优的区问．容易将M-Computer-Opt算法扩充以便除了值之外再记住一个最优解：我们可以维护另一个数组S使得S[i]包含{1,2．hellip;．i）中的最优的一组区间，但是，缺乏技巧地增加代码来维护数组S中的解会由于一个O(n)的附加因子增加运行时间：当M数组中的一个位置可以在O(1)时间内被修改时，在S数组中写下一个集合用O(n)时间．我们可以通过不明显地维护S而避免这个O(n)时间的增加，但这是在最优的值已经被计算之后通过从存储在数组M中的值重新获得这个最优解。

我们从定理1.2知道j属于一个关于区间集合{1，hellip;，j}的最优解当且仅当 OPT((p(j))ge;OPT（j-1）．使用这个观察，我们得到下面的简单过程，它通过数组M“反向追踪”来找出在最优解中的区间集合。

Find- Solution (j)

If j = 0 then

什么也不输出

Else

If M [p(j)] M[j-1] then

输出 j 与 Find- Solution( p(j))的结果

Else

输出Find- Solution( j -1)的结果

End if

End if

由于Find-Solution 只在确实更小的值上调用自己，它总的产生O(n)次递归调用；并且由于它每次调用用常数时间，我们有：

定理1.5 给定这些子问题的最优值的数组Find-Solution在O(n)时间内返回一个最优解。

1.2 动态规划原理：备忘录或者子问题迭代

我们现在使用在前一节开发的带权区间调度问题的算法来概述一下动态规划的基本原理，并且还要提出一个不同的观点：在子问题上迭代，而不是递归地计算解，它将作为本章其余部分的基础。

在前一节，我们开发了一个带权区间调度问题的多项式时间的解法，它先设计一个指数时间的递归算法，然后（通过备忘录）把它转换成一个有效的递归算法，这个算法考虑一个对于子问题最优解的全局数组M．但是为了实际上理解这里要做的事，把与这个算法基本等价的一个方法形式化是有用的．就是这个新的形式化最直接抓住了动态规划技术的本质，它也将作为后面各节我们开发算法的一般模板。

1.2.1 设计算法

有效算法的关键实际上

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[613618]，资料为PDF文档或Word文档，PDF文档可免费转换为Word