gusucode.com > 十大算法matlab程序说明 > 十大算法matlab程序说明/动态规划/中国数学建模-编程交流-动态规划算法_1.txt
中国数学建模-编程交流-动态规划算法
wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出
>> VC++,C,Perl,Asp...编程学习,算法介绍. 我的收件箱 (0)
中国数学建模 → 学术区 → 编程交流 → 动态规划算法
您是本帖的第 640 个阅读者
* 贴子主题：动态规划算法
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
鲜花(0) 鸡蛋(0) 楼主
动态规划算法
动态规划
Dynamic Programming
Starfish (starfish.h@china.com)
摘要
本文介绍了动态规划的基本思想和基本步骤，通过实例研究了利用动态规划设计算法的具体途径，讨论了动态规划的一些实现技巧，并将动态规划和其他一些算法作了比较，最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:39:12
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 2 楼
目录
引言
动态规划的基本概念
动态规划的基本定理和基本方程
动态规划的适用条件
动态规划的基本思想
动态规划的基本步骤
动态规划的实例分析
动态规划的技巧
动态规划实现中的问题
动态规划与其他算法的比较
动态规划的理论基础
其他资料
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:41:31
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 3 楼
引言——由一个问题引出的算法
考虑以下问题
[例1] 最短路径问题
现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试找出从结点A到结点E的最短距离。
图 1
我们可以用深度优先搜索法来解决此问题，该问题的递归式为
其中是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。
具体算法如下：
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:42:19
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 4 楼
function MinDistance(v):integer;
begin
if v=E then return 0
else
begin
min:=maxint;
for 所有没有访问过的节点i do
if v和i相邻 then
begin
标记i访问过了;
t:=v到i的距离+MinDistance(i);
标记i未访问过;
if t<min then min=t;
end;
end;
end;
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:42:36
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 5 楼
开始时标记所有的顶点未访问过，MinDistance(A)就是从A到E的最短距离。
这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O(n!)，这是一个“指数级”的算法，那么，还有没有更好的算法呢？
首先，我们来观察一下这个算法。在求从B1到E的最短距离的时候，先求出从C2到E的最短距离；而在求从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两遍。同样可以发现，在求从C1、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同时将求得的最短距离"记录在案"，随时调用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从v到E的最短距离记录下来，在算法中递归地求MinDistance(v)时先检查以前是否已经求过了MinDistance(v)，如果求过了则不用重新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有n个，因此不同的状态数目有n个，该算法的数量级为O(n)。
更进一步，可以将这种递归改为递推，这样可以减少递归调用的开销。
请看图1，可以发现，A只和Bi相邻，Bi只和Ci相邻,...，依此类推。这样，我们可以将原问题的解决过程划分为4个阶段，设S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3}，Fk(u)表示从Sk中的点u到E的最短距离，则
并且有边界条件
显然可以递推地求出F1(A)，也就是从A到E的最短距离。这种算法的复杂度为O(n)，因为所有的状态总数（节点总数）为n，对每个状态都只要遍历一次，而且程序很简洁。
具体算法如下：
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:43:07
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 6 楼
procedure DynamicProgramming;
begin
F5[E]:=0;
for i:=4 downto 1 do
for each u ∈Sk do
begin
Fk[u]:=无穷大;
for each v∈Sk+1∩δ(u) do
if Fk[u]>w(u,v)+Fk+1[v] then Fk[u]:=w(u,v)+Fk+1[v];
end;
输出F1[A];
end;
这种高效算法，就是动态规划算法。
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:44:07
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 7 楼
动态规划的基本概念
动态规划的发展及研究内容
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision
process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep
decision process)的优化问题时，提出了著名的最优化原理(principle of
optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic
Programming，这是该领域的第一本著作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
多阶段决策问题
多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。
例1是一个多阶段决策问题的例子，下面是另一个多阶段决策问题的例子：
[例2] 生产计划问题
工厂生产某种产品，每单位(千件)的成本为1(千元)，每次开工的固定成本为3(千元)，工厂每季度的最大生产能力为6(千件)。经调查，市场对该产品的需求量第一、二、三、四季度分别为
2，3，2，4(千件)。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本(少付固定成本费)，但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5(千元)。还规定年初和年末这种产品均无库存。试制订一个生产计划，即安排每个季度的产量，使一年的总费用(生产成本和存储费)最少。
决策过程的分类
根据过程的时间变量是离散的还是连续的，分为离散时间决策过程(discrete-time decision
process)，即多阶段决策过程和连续时间决策过程(continuous-time decision
process)；根据过程的演变是确定的还是随机的，分为确定性决策过程(deterministic decision
process)和随机性决策过程(stochastic decision process)，其中应用最广的是确定性多阶段决策过程。
动态规划模型的基本要素
一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：
1.阶段
阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示。在例1中由A出发为k=1，由Bi(i=1,2)出发为k=2，依此下去从Di(i=1,2,3)出发为k=4，共n=4个阶段。在例2中按照第一、二、三、四季度分为k=1,2,3,4，共4个阶段。
2.状态
状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。
描述状态的变量称状态变量(state variable)。变量允许取值的范围称允许状态集合(set of admissible
states)。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在例1中x2可取B1，B2，X2={B1,B2}。
n个阶段的决策过程有n+1个状态变量，xn+1表示xn演变的结果，在例1中x5取E。
根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。
状态变量简称为状态。
3.决策
当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)，在最优控制问题中也称为控制(control)。
描述决策的变量称决策变量(decision variable)。变量允许取值的范围称允许决策集合(set of admissible
decisions)。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示了xk的允许决策集合。在例1中u2(B1)可取C1,C2,C3。
决策变量简称决策。
4.策略
决策组成的序列称为策略(policy)。由初始状态x1开始的全过程的策略记作p1n(x1)，即p1n(x1)={u1(x1),u2(x2),...，un(xn)}。由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pkn(xk)，即pkn(xk)={uk(xk),uk+1(xk+1),...，un(xn)}。类似地，由第k到第j阶段的子过程的策略记作pkj(xk)={uk(xk),uk+1(xk+1),...，uj(xj)}。对于每一个阶段k的某一给定的状态xk，可供选择的策略pkj(xk)有一定的范围，称为允许策略集合(set
of admissible policies)，用P1n(x1),Pkn(xk),Pkj(xk)表示。
5.状态转移方程
在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equation of
state)表示这种演变规律，写作
在例1中状态转移方程为：xk+1=uk(xk)
6.指标函数和最优值函数
指标函数(objective
function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k到阶段n的指标函数用Vkn(xk,pkn(xk))表示，k=1,2,...,n。
能够用动态规划解决的问题的指标函数应具有可分离性，即Vkn可表为xk,uk,Vk+1 n 的函数，记为：
其中函数是一个关于变量Vk+1 n单调递增的函数。这一性质保证了最优化原理(principle of
optimality)的成立，是动态规划的适用前提。
过程在第j
阶段的阶段指标取决于状态xj和决策uj，用vj(xj,uj)表示。阶段k到阶段n的指标由vj(j=k,k+1,..n)组成，常见的形式有：
阶段指标之和，即
阶段指标之积，即
阶段指标之极大(或极小)，即
这些形式下第k到第j阶段子过程的指标函数为Vkj(xk,uk,xk+1,...,xj+1)。可以发现，上述(3)-(5)三个指标函数的形式都满足最优性原理。在例1中指标函数为(3)的形式，其中vj(xj,uj)是边<xj,uj(xj)>的权（边的长度）,uj(xj)表示从xj出发根据决策uj(xj)下一步所到达的节点。
根据状态转移方程，指标函数Vkn还可以表示为状态xk和策略pkn的函数，即Vkn(xk,pkn)。在xk给定时指标函数Vkn对pkn的最优值称为最优值函数(optimal
value function)，记作fk(xk)，即
其中opt可根据具体情况取max或min。上式的意义是，对于某个阶段k的某个状态xk，从该阶段k到最终目标阶段n的最优指标函数值等于从xk出发取遍所有能策略pkn所得到的最优指标值中最优的一个。
7.最优策略和最优轨线
使指标函数Vkn达到最优值的策略是从k开始的后部子过程的最优策略，记作pkn*={uk*,..un*},p1n*又是全过程的最优策略，简称最优策略(optimal
policy)。从初始状态x1(=x1*)出发，过程按照p1n*和状态转移方程演变所经历的状态序列{x1*,x2*,..,xn+1*}称最优轨线(optimal
trajectory)。
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:44:39
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 8 楼
动态规划的基本定理和基本方程
动态规划发展的早期阶段，从简单逻辑出发给出了所谓最优性原理，然后在最优策略存在的前提下导出基本方程，再由这个方程求解最优策略。后来在动态规划的应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价，二者之间也不存在任何确定的蕴含关系。基本方程在动态规划中起着更为本质的作用。
[基本定理]
对于初始状态x1∈X1，策略p1n*={u1*,..un*}是最优策略的充要条件是对于任意的k,1<k<=n,有
[推论]
若p1n*∈P1n(x1)是最优策略，则对于任意的k,1<k<n，它的子策略pkn*对于由x1和p1,k-1*确定的以xk*为起点的第k到n后部子过程而言，也是最优策略。
上述推论称为最优化原理，它给出了最优策略的必要条件，通常略述为：不论过去的状态和决策如何，对于前面的决策形成的当前的状态而言，余下的各个决策必定构成最优策略。
根据基本定理的推论可以得到动态规划的基本方程：
其中是决策过程的终端条件，为一个已知函数。当xn+1只取固定的状态时称固定终端；当xn+1可在终端集合Xn+1中变动时称自由终端。最终要求的最优指标函数满足(10)式：
(9)式是一个递归公式，如果目标状态确定，当然可以直接利用该公式递归求出最优值（这种递归方法将在后文介绍，称作备忘录法），但是一般在实际应用中我们通常将该递归公式改为递推公式求解，这样一般效率会更高一些。
<!-- #EndEditable -->
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:45:48
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 9 楼
动态规划的适用条件
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
1.最优化原理（最优子结构性质）
最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
图2
例如图2中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J'是B到C的最优路径，则A到C的路线取I和J'比I和J更优，矛盾。从而证明J'必是B到C的最优路径。
最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。动态规划的最优化理在其指标函数的可分离性和单调性中得到体现。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。
可以看出，例1是满足最优化原理的。
2.无后向性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
如果用前面的记号来描述无后向性，就是：对于确定的xk，无论p1,k-1如何，最优子策略pkn*是唯一确定的，这种性质称为无后向性。
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:46:20
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 10 楼
[例3] Bitonic旅行路线问题
欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的最短游历路线问题。图3(a)给出了七个点问题的解。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图3（b）给出了七个点问题的解。
图3
这两个问题看起来很相似。但实质上是不同的。为了方便讨论，我将每个顶点标记了号码。由于必然经过最右边的顶点7，所以一条路(P1-P2)可以看成两条路（P1-7）与(P2-7)的结合。所以，这个问题的状态可以用两条道路结合的形式表示。我们可以把这些状态中，两条路中起始顶点相同的状态归于一个阶段，设为阶段[P1,P2]。
那么，对于Bitonic旅行路线问题来说，阶段[P1,P2]如果可以由阶段[Q1,Q2]推出，则必须满足的条件就是:P1<Q1或P2<Q2。例如，阶段[3,4]中的道路可以由阶段[3,5]中的道路加一条边4-5得出，而阶段[3,5]的状态却无法由阶段[3,4]中的状态得出，因为Bitonic旅行路线要求必须严格地由左到右来旅行。所以如果我们已经知道了阶段[3,4]中的状态，则阶段[3,5]中的状态必然已知。因此我们可以说，Bitonic问题满足无后向性，可以用动态规划来解决。
有些问题乍一看好像有后向性，但如果按照某种合理的方式重新划分阶段，就可以发现其本质上是无后向性的，所以关键是阶段的合理划分，这一点将在动态规划的技巧中详细阐述。
3.子问题的重叠性
在例1中我们看到，动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。以Bitonic旅行路线问题为例，这个问题也可以用搜索算法来解决。动态规划的时间复杂度为O(n2)，搜索算法的时间复杂度为O(n!)
，但从空间复杂度来看，动态规划算法为O(n2)，而搜索算法为O(n)，搜索算法反而优于动态规划算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。
设原问题的规模为n，容易看出，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。
<!-- #EndEditable -->
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:46:32
本主题贴数 27 分页：9 1 2 3 : 跳转论坛至...╋数学建模 ├数模竞赛 ├新手入门 ├数学工具 ├资源与检索╋学术区
├数学思想 ├编程交流 ├学术杂谈 ├English Fans╋休闲专区 ├灌水搞笑专区 ├神秘园╋本站站务 ├站务讨论
├数模管理区 ├回收站
*快速回复：动态规划算法
发贴表情
段落格式 普通格式标题 1标题 2标题 3标题 4标题 5标题 6标题 7已编排格式地址
字体宋体黑体楷体仿宋隶书幼圆新宋体细明体ArialArial BlackCourierVerdanaWide
LatinWingdings 字号1234567
第 1 页,共 7 页， 49 个
显示签名 内容限制：字节.
管理选项： 专题管理 | 修复 | 锁定 | 解锁 | 提升 | 跟贴管理 | 删除 | 移动 | 设置固顶 | 奖励 | 惩罚 | 发布公告
Copyright ©2002 - 2004 Shumo.Com
执行时间：562.50000毫秒。查询数据库5次。
当前模板样式：[默认模板]