THE THEORY OF DYNAMIC PROGRAMMING
RICHARD BELLMAN
- Introduction. Before turning to a discussion of some representa-tive problems which will permit us to exhibit various mathematical features of the theory, let us present a brief survey of the funda-mental concepts, hopes, and aspirations of dynamic programming.
To begin with, the theory was created to treat the mathematical problems arising from the study of various multi-stage decision processes, which may roughly be described in the following way: We have a physical system whose state at any time / is determined by a set of quantities which we call state parameters, or state variables. At certain times, which may be prescribed in advance, or which may be determined by the process itself, we are called upon to make de-cisions which will affect the state of the system. These decisions are equivalent to transformations of the state variables, the choice of a decision being identical with the choice of a transformation. The out-come of the preceding decisions is to be used to guide the choice of future ones, with the purpose of the whole process that of maximizing some function of the parameters describing the final state.
Examples of processes fitting this loose description are furnished by virtually every phase of modern life, from the planning of indus-trial production lines to the scheduling of patients at a medical clinic ; from the determination of long-term investment programs for universities to the determination of a replacement policy for ma-chinery in factories; from the programming of training policies for skilled and unskilled labor to the choice of optimal purchasing and in-ventory policies for department stores and military establishments.
It is abundantly clear from the very brief description of possible applications that the problems arising from the study of these processes are problems of the future as well as of the immediate present.
Turning to a more precise discussion, let us introduce a small amount of terminology. A sequence of decisions will be called a policy, and a policy which is most advantageous according to some preassigned criterion will be called an optimal policy.
The classical approach to the mathematical problems arising from the processes described above is to consider the set of all possible
An address delivered before the Summer Meeting of the Society in Laramie on September 3, 1953 by invitation of the Committee to Select Hour Speakers for An-nual and Summer meetings; received by the editors August 27,1954.
503
504 RICHARD BELLMAN [November
sequences of decisions, which is to say, the set of all feasible policies, compute the return from each such feasible policy, and then maximize the return over the set of all feasible policies.
It is evident that, straightforward and reasonable as such a pro-cedure is, it is often not practical. For processes involving even a moderate number of stages and a moderate range of choices at each stage, the dimension of the resultant maximization problem will be uncomfortably high, with continuous processes requiring maximiza-tion over function space.
If we momentarily re-examine the situation, not as a mathe-matician, but as a 'practical man,' we see that this price of exces-sive dimensionality—a price that occasionally makes even a modern computing machine cringe—arises from a demand for too much in-formation. How much information is actually required to carry out a multi-stage decision process?
Do we require a knowledge of the complete sequence of decisions, those to be performed at the present stage, those at the next stage, and so on? Not at all! It is sufficient to furnish a general prescription which determines at any stage the decision to be made in terms of the current state of the system. In other words, if at any particular time we know what to do, it is never necessary to know the decisions re-quired at subsequent times.
Donning our mathematical cap again, we see that this common-sense attitude reduces the dimension of the problem to its proper level, namely the dimension of the decision problem that confronts one at any particular time.
For the case of deterministic processes, which is to say, those where the initial state and the decision uniquely determine the outcome, both viewpoints are possible. For the case of stochastic processes, where a decision determines only a distribution of outcome states, the classical enumerative approach is virtually impossible.
- The fundamental approach. As stated above, the basic idea of the theory of dynamic programming is that of viewing an optimal policy as one determining the decision required at each time in terms of the current state of the system. Following this line of thought, the basic functional equations given below describing the quantitative aspects of the theory are uniformly obtained from the following intuitive
P R I N C I P LE OF OPTIMALITY. An optimal policy has the property that whatever the initial state and initial decisions are, the remaining de-cisions must constitute an optimal policy with regard to the state resulting from the first decisions.
i954] THE THEORY OF DYNAMIC PROGRAMMING 505
The functional equations we shall derive are of a difficult and fascinating type, wholly different from any encountered previously in analysis. Nonetheless, as we shall see below, they may be utilized to provide an entirely new approach to some classical problems.
-
Mathematical formulation—I. A discrete deterministic process. To illustrate the type of functio
剩余内容已隐藏，支付完成后下载完整资料
动态规划理论
RICHARD BELLMAN
1.简介。在讨论一些可以让我们展示理论的各种数学特征的代表性问题之前，让我们简要介绍一下动态规划的基本概念，希望和愿望。
首先，创建该理论是为了处理因研究各种多阶段决策过程而产生的数学问题，这些问题大致可以用以下方式描述：我们有一个物理系统，其状态在任何时间/由一个我们称之为状态参数或状态变量的数量集。在某些时候，可以提前规定，或者可以由过程本身确定，我们被要求做出影响系统状态的决策。这些决策等同于状态变量的变换，决策的选择与变换的选择相同。前面决定的结果将用于指导未来决策的选择，其目的在于最大化描述最终状态的参数的某些功能的整个过程。
从工业生产线的规划到医疗诊所患者的安排，几乎现代生活的每个阶段都提供适合这种松散描述的过程的例子。从确定大学的长期投资计划到确定工厂机械的替代政策;从针对熟练和非熟练劳动力的培训政策的规划，到为百货商店和军事机构选择最佳采购和政策。
从对可能的应用的简短描述中可以清楚地看出，研究这些过程所产生的问题是未来和现在的问题。
谈到更精确的讨论，让我们介绍一些术语。一系列决策将被称为策略，根据某些预先指定的标准最有利的策略将被称为最优策略。
由上述过程引起的数学问题的经典方法是考虑所有可能的集合
1953年9月3日，在年度和夏季会议选拔小时发言人委员会的邀请下，在拉勒米协会夏季会议之前发表的讲话;编辑于1985年8月27日收到。
决策序列，也就是说，所有可行策略的集合，计算每个这样的可行策略的回报，然后最大化所有可行策略集合的回报。
显而易见的是，这种程序直截了当且合理，通常是不实际的。对于涉及甚至适度阶段和每个阶段的适度选择范围的过程，所得最大化问题的维度将令人不舒服地高，连续过程需要在功能空间上最大化。
如果我们暂时重新审视这种情况，不是作为一个数学家，而是作为一个“实用的人”，我们会看到这种过度维度的价格 - 即使现代计算机偶尔会让人感到畏缩的价格 - 也来自于对太多信息的需求。实施多阶段决策过程实际需要多少信息？
我们是否需要了解完整的决策顺序，现阶段的决策，下一阶段的决策等等？一点也不！提供一般处方就足够了，该处方在任何阶段确定根据系统的当前状态做出的决定。换句话说，如果在任何特定时间我们知道该做什么，就不必知道随后时间所需的决定。
再次使用我们的数学上限，我们看到这种常识态度将问题的维度降低到适当的水平，即在任何特定时间面临的决策问题的维度。
对于确定性过程的情况，也就是说，初始状态和决策唯一确定结果的过程，两个观点都是可能的。对于随机过程的情况，其中决策仅确定结果状态的分布，经典的枚举方法实际上是不可能的。
2.基本方法。如上所述，动态规划理论的基本思想是将最优策略视为根据系统的当前状态确定每次所需的决策。按照这一思路，下面给出的描述理论定量方面的基本函数方程式均可从以下直观得到
P R I N C I P LE OF OPTIMALITY。最优策略具有以下属性：无论初始状态和初始决策是什么，剩余的de-c
让
（7.1）f（x）=采用最优政策获得的总回报，
如上所述，很容易看出f（x）满足函数方程
（7.2）fnof;（*）= Sup [g（y） h（x-y） f {ay b（x-y））L xgt; 0，
/（0）= 0。
为了讨论这个方程可以出现的各种方式，以及可以获得的一些分析结果，我们将读者引用到[4; 6; 11; 12。
处理密切相关的最优库存问题可以在[2; 29; 15]。
8.一些例子 - 二：随机金矿开采。现在让我们考虑以下示例：
问题2.我们有幸拥有两个金矿，Anaconda和Bonanza，以及具有以下特征的敏感金矿机：如果机器用于Anaconda，它将以概率p挖掘固定分数r那里的黄金并没有损坏;概率（1-p）它将不会挖掘任何东西并且损坏无法修复。如果机器在Bonanza中使用，它将以概率q挖掘那里的黄金的固定分数5并且没有损坏;有概率（1克），它将挖掘任何东西，并损坏无法修复。
在每个阶段，只要机器没有损坏，我们就可以选择在Anaconda或Bonanza中使用机器。给定每个矿山的初始量x和y，选择的顺序最大化了机器损坏前开采的预期量？
让
（8.1）f（x，y）=使用最优政策在机器损坏之前开采的预期金量，从Anaconda的x开始，在Bonanza开始。
很容易看出f（x，y）满足函数方程
：fi 0，。,, _，rA：p [rx f（（l-r）x，y）] l
（8.2）f（x，y）=最大。
LB：q [sy f（x，（1-s）y）\ A.
1954年]动态规划理论509
该解决方案具有以下简单结构：
一个。对于prx /（l - r）gt; qsy /（l - s），选择A，
（8.3）湾对于prx /（l - r）lt;qsy /（l - s），选择B，
C。对于prx /（l - r）= qsy /（l - s），选择其中之一。
使用这个处方，可以反复计算fnof;（＃，; y）。两个决策区域之间的边界曲线是两个选择的立即预期收益与即时预期损失相同的点的轨迹。不幸的是，正如Karlin和Shapiro [36]的一个反例所示，这个简单直观的规则在更复杂的决策过程中通常无效。
有关离散和连续类型的进一步结果和扩展的讨论，请参见[3; 9; 11; 25; 26。
9.一些例子 - III：变化微积分中的一个问题。变量计算中的以下问题提供了连续决策过程的简单示例：
问题3.在所有y上最大化f％F（x，y）dt，其中x和y可通过关系dx / dt = G（x，y），x（0）= c连接。
变换微积分中的经典技术，在有限维空间中的最大化问题中使用的技术之后直接构图，包括考虑产生极值作为函数空间中的点的函数。这一点现在通过变分性质来表征，其中最重要的是欧拉方程。
这种方法对应于找到y作为L的函数。相反，我们将该问题视为一个连续的决策过程，并试图随时确定y作为两个状态参数c和T的函数。让我们设置
（9.1）f（c，T）=最大fI F（x，y y）dt。
vJ o
我们将在接下来的内容中完全正式地进行，假设达到最大值，所有函数都具有必需数量的连续导数，依此类推。使用最优性原理，我们看到fnof;（c，T）满足等式
f（c，S T）= Max T f F（x，y）dl f F（x，y）dt \
（9.2）
- Maxi“f F（x，y）dt MS），T）]，
其中c（S）在t = S时为x。假设y是连续的，我们在简单计算后得到（9.2）的极限形式为5-gt; 0
（9.3）fT = Max [F（c，v） G（G，v）fe]，
其中v = y（0）。正式进行，我们有最大限度的决心
（9.4）Fv Gvfc = 0。
消除（9.3）和（9.4）之间的fnof;，我们得到一阶偏微分方程
（9 5）（ - \ v =（FGv ~~ GFv \ v （FGv~GFv \
\ Gv / v \ Gv / v \ Gv / c
该等式的特征直接导致通过常规变分方法获得的欧拉方程：
（9.6）Gy - （ - ）r x ry
= GV）Gx
在多维问题中也是如此，其中x，y和G（x，y）是向量而F（x，y）是标量函数。通过引入新的因变量，可以总是将被积函数明确包含t的情况简化为上述情况。
如果我们在原始问题中添加一个约束，例如O ^ y ^ x，一个经常出现与分配和投资问题相关的约束，则函数方程式被替换为
（9.7）fT = Max [F（c，v） G（c，v）fe]。
在[17]中给出了该问题具有特别简单结构的解决方案的各种条件。我们可能顺便提一下
为什么没有更多的量子算法被发现？
PETER W. SHOR
1994年我发现的量子因子分解算法引起了理论计算机科学家的极大兴趣。量子计算机为计算理论提供了一个全新的范式，这是第一次证明量子计算能够有效地解决这个领域中已经确立的重要问题。许多人期待着其他有趣的算法的成功。事实令人失望，特别是与量子信息处理领域其他领域的进展相比。实验物理学家一直在提出和探索量子计算机可能的物理实现，其速度远远超过任何人的预期，但最乐观的研究人员最初的预期。量子密码学正在走向成熟，其安全性的若干理论证明被重新发现，商业量子密码学系统预计将在明年左右出现。量子信息理论和量子复杂性的研究领域得到了迅猛的发展，产生了一系列有趣而重要的理论成果。同时，算法发展滞后，近五年来几乎没有发现任何重要的新算法。
到目前为止，所有已知的量子算法都提供了实质性的加速。同样问题的经典算法分为三类。第一类使用傅立叶变换来寻找周期性。该类包含因子分解和离散对数算法[shor 1997]、Simon算法[Simon 1997]（该类的第一个成员将被发现），以及Hallgren的Pell方程和某些其他数论问题算法[Hallgren 2002]。事实上，有一种不同的方法来看待因子分解算法，虽然它产生了基本相同的算法，但将其置于强调光谱方法而不是周期性的设置中[Kitaev 1996]，但这种方法尚未产生任何新算法。第二类包含grradic;over的搜索算法，其中可以在n时间内对n个项目执行详尽的搜索[Grover 1997]，以及该算法的扩展数（见Grover和Sengupta[2002]）。这些扩展都具有在优化或搜索问题的速度上给予平方根改进的一般风格。第三类包括模拟或解决量子物理问题的算法
这门课包含了费曼的原始想法（费曼1982年），即使用量子计算机加速量子物理的模拟。虽然还没有很多关于这类算法的理论论文，但很明显，如果量子计算机被开发出来，这类算法在实践中会非常有用。费曼在1982年提出了用量子计算机模拟量子物理的想法，1993年和1994年开发了西蒙算法和因子分解算法，1995年格罗夫提出了他的原始搜索算法。从那时起，每一类算法都有了进一步的理论发展，但还没有发现新的量子算法。
作为量子因子分解算法的发现者，我经常被问到的一个问题是，为什么已知的量子算法很少能够提供比经典算法更快的速度。我通常给出的答案是我不知道，但我能想到两个可能的原因，这可能是事实。第一个可能的原因是量子计算机的运行方式与经典计算机的运行方式大不相同，以至于我们设计算法的技术和理解计算过程的直觉不再起作用。第二个原因是，量子计算机能够提供比经典计算机更快的速度的真正问题可能相对较少，而且我们可能已经发现了许多或所有构建量子算法的重要技术。本文对这些思想进行了扩展。
这两种解释都解决了一个问题，那就是为什么我们没有看到量子算法有更多的加速，我相信这两种解释在很大程度上都是正确的。当然，全图姆电脑很难用经典直觉来解释。物理学家们花了几十年的时间来发展他们对量子现象的直觉，他们使用的许多技术都是在量子力学最初发展几十年之后出现的。另一方面，计算机科学家们对量子力学的思考还不到十年。任何能加快经典计算速度的量子算法都必须使用干扰；这种phe-诺门子在经典计算机科学中是未知的，大多数理论计算机科学家都不习惯对此进行推理。因此，很有可能几个新的和重要的量子算法技术尚未被发现。
另一方面，许多对新量子计算机算法的研究一直在寻找超自然的加速。虽然这些不出现在格罗弗算法及其扩展中，但它们可以出现在使用周期性发现和模拟量子物理的量子算法类中。超线性加速不能由具有多项式时间经典算法的问题引起，因此研究人员一直专注于不属于经典计算类P的问题。首先想到的不属于P的问题是NP完全问题。在多项式时间内求解NP-完全问题的量子算法将是一个重大发现，但我相信最有可能的情况是这是不可能的。已经证明存在一个预言，与之相关的NP完全问题在多项式时间内无法解决。1997年），虽然支持量子计算机不能解决NP完全问题的理由比支持经典计算机不能解决NP完全问题的几乎普遍的信念少，但许多研究人员仍然对量子计算机能够解决NP完全问题感到悲观。
如果我们假设NP完全问题在量子计算机上不能有效地解决，那么为了达到一个超线性加速，我们必须研究既不是NP硬问题也不是P中的问题。在这类问题中，只有相对较少的被研究得很好的问题被怀疑是存在的。这些问题不存在一般性的理论，相对较少的问题是可以互相还原的，所以必须单独考虑。可能这些问题中的许多在量子计算机上并没有多项式时间算法。到目前为止，人们必须集中精力解决那些似乎具有周期性结构的问题，从而提供一种可能的攻击手段。这些问题包括图同构问题和格中短向量的近似问题。这些问题都还没有屈服于全图姆人的攻击。
对发现许多量子加速的部分期望可能是由于与经典计算历史的类比。在确定了NP的完整性之后【库克1971年，卡普1972年，莱文1973年】，随后出现了大量的论文，将问题分类为多项式时间（给出有效算法）或NP硬问题。这可能使我们的期望值过高，因为分类工作的成功现在只留下了相对较少的研究得很好的问题，而这些问题在这两个类中尚不清楚。通过寻找超自然的加速，我们可能也在尝试一个太困难的任务。与量子计算领域的研究人员相比，经典算法的研究人员不仅花时间试图将更多的问题放入P类，而且还试图为已知的P类问题找到更快的算法。通过尝试发现解决已知的P类问题的新方法，研究人员已经十人能够找到新的、富有成果的技术，然后可以用来帮助解决其他问题，有时包括有效解决P中未知问题的方法。
一个值得探索的研究领域是试
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[441416]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
