中国数学建模-编程交流-动态规划算法
wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出
>> VC++,C,Perl,Asp...编程学习,算法介绍. 我的收件箱 (0)
中国数学建模 → 学术区 → 编程交流 → 动态规划算法
您是本帖的第 641 个阅读者
* 贴子主题：动态规划算法
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 11 楼
动态规划的基本思想
前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的
(即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:46:48
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 12 楼
动态规划算法的基本步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。
动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：
标准动态规划的基本框架
1. 对fn+1(xn+1)初始化; {边界条件}2. for k:=n downto 1 do 3. for 每一个xk∈Xk do4. for 每一个uk∈Uk(xk) do begin5. fk(xk):=一个极值; {∞或－∞}6. xk+1:=Tk(xk,uk); {状态转移方程}7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}8. if t比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值} end; 9. t:=一个极值; {∞或－∞}10. for 每一个x1∈X1 do11. if f1(x1)比t更优 then t:=f1(x1); {按照10式求出最优指标}12. 输出t;但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：
分析最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
根据计算最优值时得到的信息，构造一个最优解。
步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。
<!-- #EndEditable -->
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:47:05
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 13 楼
动态规划的实例分析
下面我们将通过实例来分析动态规划的设计步骤和具体应用。例1已经在前文介绍过了。例1和例2是标准的动态规划，有明显的阶段和状态转移方程；例3、例4、例5、例6是没有明显阶段划分的动态规划，也是一般常见的形式，其中对例4、例5、例6作了比较详细的分析；例7是比较特殊的动态规划，例8是两重动态规划（即为了解决问题要进行两次动态规划）的例子。
例1 最短路径问题
例2 生产计划问题
例3 Bitonic旅行路线问题
例4 计算矩阵连乘积
例5 最长公共子序列
例6 凸多边形的最优三角剖分问题
例7 多边形计算
例8 字符识别
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 19:47:32
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 14 楼
动态规划的技巧——阶段的划分和状态的表示
在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的两步，这两步会直接影响该问题的计算复杂性，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。
[例9] 街道问题
在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。
这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的：
按照图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量xk表示当前处于这一阶段上的哪一点。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走，uk=1表示向上走，则状态转移方程如下：
(这里的row是地图竖直方向的行数）
我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做的，而代之以下面方法：
（这里Distance表示相邻两点间的边长）
这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的"状态转移"就不全是在两个阶段之间进行的了。
也许这没什么大不了的，因为实践比理论更有说服力。但是�
