动态规划算法

b

<H3>动态规划与网络流——动态规划是易设计易实现的算法</H3><>由于图的关系复杂而无序，一般难以呈现阶段特征（除了特殊的图如多段图--<a href="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/introduction.htm#example1" target="_blank" >参见例一</A>），因此动态规划在图论中的应用不多。但有一类图，它的点却是有序的，这就是无环有向图。</P><>在有向无环图中，我们可以对点进行拓扑排序，使其体现出有序的特征，从而据此划分阶段。在有向无还图中求最短路径的算法，已经体现出了简单的动态规划思想。请看下面的例子。</P>< align=center><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch7.gif"></P><P><B>[例16]</B> 单源最短路径问题</P><P>已知从A到J的路线及费用如上图，求从A到J的最小费用路线。</P><P><B>问题的分析和解答：</B></P><P>本问题没有明显的阶段划分，各点间没有一定的先后次序（请注意与<a href="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/introduction.htm#example1" target="_blank" >例一</A>不同），不能按照最少步数来决定顺序，如从A到D走捷径需4，但A-C-D只需3，更优。看来图中出现回路，不能实施动态规划。其实不然。细想一下，从A到J的最优策略，它每一部分也是最优的（可以用反证法来证明），换言之，本题也具有<a href="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/chapter3.htm#optimality" target="_blank" >最优化性质</A>，只是阶段不明显而已。</P><P>对于这类问题，我们可以换个角度分析，构造算法。比较一下前面所讲的动态规划法，都是以某个状态为终点，寻找到达次点的路径，然后比较优劣，确定此状态最优值。可是，本题阶段不明显，各状态之间的道路会出现嵌套，故此法不能使用。变一下角度，每次都以某个状态为起点，遍历由它引申出去的路径，等所有已知状态都扩展完了，再来比较所有新状态，把值最小的那个状态确定下来，其它的不动。如上图，先从A出发，找到3个结点B，D，C，费用为F（B）=3，F（D）=4，F（C）=2。因为F（B），F（D）都大于F（C），那么可以确定：不可能再有路线从B或D出发到C，比A-C更优。这样F（C）的最优值便确定了。可是，有没有路线从C出发到B或D，比A-B或A-D更优呢？还不清楚。继续下去，因为A扩展完了，只有从C开始，得到A-C-D=3，A-C-F=3，于是F（D）的值被刷新了，等于3。现在，有F（B）=F（D）=F（F）=3，于是，三点的最优值都确定下来了。然后以分别以三个点为起点，继续找。以次类推，直到J点的最优值确定为止。</P><P>细心观察，其实本题的隐含阶段就是以各结点的最优值的大小来划分的，上述过程就是按最优值从小到大前向动态规划。人们习惯上把此题归入到图论范畴中，并将上述方法称为标号法。这个算法就是图论中著名的<DFN>Dijkstra单源最短路径算法</DFN>。</P><P>事实上，动态规划在图论中还有更多的应用，请看下例：</P><P><B>[例17]</B>  N个人的街道问题</P><P>在<a href="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/chapter7.htm#examp7" target="_blank" >街道问题（参见例7）</A>中，若有N个人要从左下角走向右上角，要求他们走过的边的总长度最大。当然，这里每个人也只能向右或向上走。下面是一个样例，左图是从出发地到目的地的三条路径，右图是他们所走过的边，这些边的总长度为5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。</P><P align=center><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/i51.gif"></P><P>这个题目是对街道问题的又一次扩展。仿照街道问题的解题方法，我们仍然可以用动态规划来解决本题。不过这一次是N个人同时走，状态变量也就需要用N维向量来表示。相应的，决策变量也要变成N维向量：</P><BLOCKQUOTE><P><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch94.gif"></P></BLOCKQUOTE><P>状态转移方程不需要做什么改动：</P><BLOCKQUOTE><P><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch941.gif"></P></BLOCKQUOTE><P>在写规划方程时，需要注意在第k阶段，N条路径所走过的边的总长度的计算，在这里用<img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch943.gif">来表示了：</P><BLOCKQUOTE><P><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch942.gif"></P></BLOCKQUOTE><P>边界条件为</P><BLOCKQUOTE><P><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch944.gif"></P></BLOCKQUOTE><P>可见将原来的动态规划算法移植到这个问题上来，在理论上还是完全可行的。但是，现在的这个动态规划算法的时空复杂度已经是关于N的指数函数，只要N稍微大一点，这个算法就不可能实现了。</P><P>下面我们换一个思路，将N条路径看成是网络中一个流量为N的流，这样求解的目标就是使这个流的费用最大。但是本题又不同于一般的费用流问题，在每一条边e上的流费用并不是流量和边权的乘积<img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/i59.gif">，而是用下式计算：</P><P align=center><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/i61.gif"></P><P>为了使经典的费用流算法适用于本题，需要将模型稍微转化一下：</P><P align=center><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/i63.gif"></P><P>如图，将每条边拆成两条,拆开后一条边上有权w<SUB>0</SUB>，但是容量限制为1；另一条边没有容量限制，但是流过这条边就不计费用。这样我们就把问题转化成了一个标准的最大费用固定流问题。</P><P>这个算法可以套用经典的<B>最小费用最大流算法</B>，在此就不细说了。</P><P>IOI97的“障碍物探测器”比这一题要复杂一些，但是基本思想是相似的。类似的题目还有99年冬令营的“迷宫改造”。从这些题目中都可以看到动态规划和网络流的联系。</P><P>推广到一般情况，任何有向无环图中的费用流问题在理论上说，都可以用动态规划来解决。对于流量为N（如果流量不固定，这个N需要事先求出来）的费用流问题，用N维的向量x<SUB>k</SUB>=(x<SUB>k,1</SUB>,x<SUB>k,2</SUB>,…,x<SUB>k,N</SUB>)来描述状态，其中x<SUB>k,i</SUB>∈V , 1≤i≤N 。相应的，决策也用N维的向量u<SUB>k</SUB>=(u<SUB>k,1</SUB>,u<SUB>k,2</SUB>,…,u<SUB>k,N</SUB>)来表示，其中u<SUB>k,i</SUB>∈E(x<SUB>k,i</SUB>) , 1≤i≤N ，E(v)表示指向v的弧集。则状态转移方程可以这样表示：</P><BLOCKQUOTE><P><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch946.gif"></P></BLOCKQUOTE><P>规划方程为</P><BLOCKQUOTE><P><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch945.gif"></P></BLOCKQUOTE><P>边界条件为</P><BLOCKQUOTE><P><img src="http://algorithm.myrice.com/algorithm/technique/dynamic_programming/images/ch944.gif"></P></BLOCKQUOTE><P>在大多数情况下，动态规划的实现比网络流要简单的多。但是，由于N维动态规划算法是指数级算法，因而在实现中的局限性很大，仅可用于一些N非常小的题目适用。</P><!-- #EndEditable -->

b

<H2>动态规划的数学理论模型</H2><>在动态规划算法发展的初期，Bellman从纯粹的逻辑出发给出了<DFN>最优性原理 --Principle of Optimality</DFN>:</P><BLOCKQUOTE><I>"An optimal policy has the property that whatever the initial state and initial decision are, then remaining decisions must constitute an optimal policy with regard to the state resulting from first decision."</I> </BLOCKQUOTE><>他给出这个原理作为动态规划适用的条件，后来Morin在1982年证明了这只是一个充分条件而非必要条件。</P><>动态规划开始只是应用于多阶段决策性问题，后来渐渐被发展为解决离散最优化问题的有效手段，进一步应用于一些连续性问题上。然而，动态规划更像是一种思想而非算法，它没有固定的数学模型，没有固定的实现方法，其正确性也缺乏严格的理论证明。因此，一直以来动态规划的数学理论模型是一个研究的热点。</P><P>目前比较流行的主要有两种理论模型：<DFN>关系计算模型(relational calculus model)</DFN>和<DFN>估价网络模型(valuation network model)。</DFN></P><P>关于这两种流行理论，感兴趣的朋友可以参看以下论文：</P><UL><LI><B>关系计算模型:</B>
<a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/VIEW.PDF" target="_blank" ><CITE>Dynamic Programming: a different perspective</CITE> , Sharon Curtis </A>
<a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/VIEW.ZIP" target="_blank" >(下载压缩的PDF文档, English , 137KB)</A> <LI><B>估价网络模型:</B>
<a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/CLPR96.PDF" target="_blank" ><CITE>AXIOMS FOR DYNAMIC PROGRAMMING</CITE> , Prakash P. Shenoy</A>
<a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/CLPR96.ZIP" target="_blank" >(下载压缩的PDF文档, English , 81KB)</A> </LI></UL><!-- #EndEditable -->

b

<H2>其他资料</H2><>关于动态规划的应用，请参阅<a href="http://algorithm.myrice.com/problems/index.html?by_strategy/dynamic_programming.htm" target="_blank" >动态规划问题集</A></P><>关于递归法，请参阅<a href="http://algorithm.myrice.com/algorithm/technique/recursion/index.htm" target="_blank" >递归技术</A></P><>关于分治法，请参阅<a href="http://algorithm.myrice.com/algorithm/technique/divide_and_conquer/index.htm" target="_blank" >分治法</A></P><P>关于动态规划的更多技巧和知识，请参阅以下资料：</P><UL><LI>以下是来自IOI国家集训队的论文： <UL><LI><I>动态规划</I> ，方奇 <a href="http://algorithm.myrice.com/resources/technical_artile/thesis_form_ioi/thesis2000_fangqi.zip" target="_blank" >(Zipped MS Word document)</A> <LI><I>把握本质，灵活运用——动态规划的深入探讨</I> ，来煜坤 <a href="http://algorithm.myrice.com/resources/technical_artile/thesis_form_ioi/thesis99_laiyukun.zip" target="_blank" >(Zipped MS Word document)</A> <LI><I>动态规划的深入讨论</I> ，李刚 <a href="http://algorithm.myrice.com/resources/technical_artile/thesis_form_ioi/thesis2000_ligang.zip" target="_blank" >(Zipped MS Word document)</A> <LI><I>动态规划的特点及其应用</I> ，张辰 <a href="http://algorithm.myrice.com/resources/technical_artile/thesis_form_ioi/thesis2000_zhangchen.zip" target="_blank" >(Zipped MS Word document)</A><FONT color=#ff0000><I> 推荐</I></FONT> </LI></UL><LI><I><a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/CLPR96.PDF" target="_blank" >AXIOMS FOR DYNAMIC PROGRAMMING</A></I> , Prakash P. Shenoy ,1996 <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/CLPR96.ZIP" target="_blank" >(Zipped .pdf document)</A><FONT color=#ff0000><I> 推荐</I></FONT> <LI><I><a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/VIEW.PDF" target="_blank" >Dynamic Programming: a different perspective</A></I> , Sharon Curtis     , <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/VIEW.ZIP" target="_blank" >(Zipped .pdf document)</A> <FONT color=#ff0000><I>推荐</I></FONT> <LI><I>How to Design Dynamic Programming Algorithms Sans Recursion </I>, Kirk Pruhs <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/DYNPROG.ZIP" target="_blank" >(Zipped .ps document)</A> <FONT color=#ff0000><I>推荐</I></FONT> <LI><I>Dynamic Programming via Static Incrementalization </I>, Yanhong A. Liu, Scott D. Stoller <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/TR514.ps.Z" target="_blank" >(Zipped .ps document)</A> <I><FONT color=#ff0000>推荐</FONT></I> <LI><I>Dynamic Programming in a Generalized Decision Mode </I>, Ulrich Huckenbeck, December, 1993 <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/tr-93-080.ps.gz" target="_blank" >(Zipped .ps document)</A> <FONT color=#ff0000><I>推荐</I></FONT> <LI><I>Between Dynamic Programming and Greedy: Data Compression</I> , Richard S. Bird , Oege de Moor, September 14 ,1995 <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/COMPACT.ZIP" target="_blank" >(Zipped .pdf document)</A> <LI><I>Using Local Trajectory Optimizers To Speed Up Global Optimization In Dynamic Programming </I>, Christopher G. Atkeson , July 28,1995 <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/ATKESON.ZIP" target="_blank" >(Zipped .ps document)</A> <LI><I>A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming</I> , Gene Myers,March 27, 1998 <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/bit.mat.zip" target="_blank" >(Zipped .ps document)</A> <LI><I>Soft Dynamic Programming Algorithms: Convergence Proofs </I>, Satinder P. Singh ,1993 <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/CLNL93.ps.gz" target="_blank" >(Zipped .ps document)</A> <LI><I>Speeding up Dynamic Programming without Omitting any Optimal Solution and some Applications in Molecular Biology</I>, Norbert Blum ,January 18, 2000 <a href="http://algorithm.myrice.com/resources/refrence/dynamic_programming/rspeedup5.ps.Z" target="_blank" >(Zipped .ps document)</A> </LI></UL><!-- #EndEditable -->

1. &lt;SCRIPT src="../../../lib/footer.js"&gt;
   
2. 
   
3. &lt;script&gt;

复制代码

zxb1373

好东西

zhangchi123

<>前辈：</P><>我为啥看不到你的方程？</P>

heihei

对对对，这到是好东东，但是看不到方程，就不好了

wujin304

好呀教教我好吗？

光辰

<>怎么没有递归算法啊</P>
<>能不能帮我一下</P>

cjx__2008

厉害~~~~~<BR>  告诉我们这么多辛苦了啊~~~~