文档介绍：该【算法设计与分析动态规划 】是由【知识徜徉土豆】上传分享，文档一共【247】页，该文档可以免费在线阅读，需要了解更多关于【算法设计与分析动态规划 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法设计与分析
The Design and Analysis of Computer Algorithms
段明秀
吉首大学信息科学与工程学院计算机教研室
The Design and Analysis of Computer Algorithms
第5章 动态规划
本章学习目标：
熟练掌握利用动态规划方法解决问题的基本思想 ；
学会如何将问题化为多阶段图的方法；
并能对具体问题写出正确的递推公式。
第5章 动态规划
动态规划概述
什么是动态规划
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态“的含义，称这种解决多阶段决策最优化的过程为动态规划方法。
第5章 动态规划
动态规划的基本思想
动态规划的思想在于，假若问题的各个子问题不是独立的，不同的子问题的个数只是多项式量级，假若能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。解决此类问题的过程：首先将问题分为许多阶段，然后再对每一阶段做出决策，而前一阶段的决策恰好又为后一阶段决策的制定提供了有用的信息。在作前一阶段的决策时，根据某些条件，舍弃那些肯定不能得到最优解的局部解，直到做出最后一个阶段的决策并得到问题的解。每一步部经过这样的选取与舍弃后，就可以大大减少计算量。
如果有一个问题，它的过程可以分为若干阶段，而且对于任一阶段i，过程在i阶段以后的行为仅仅依赖于i阶段的状态，而与过程如何达到此种状态（即达到的方式）无关，则称之为一个多阶段的决策过程。解决此类问题的依据是Bellman提出的所谓“最佳（优）性原理（principle of optimality）”：无论过程初始的状态和策略如何，其余的决策必须相对于初始决策所造成的状态构成一个最优的决策序列。最优性原理又被称为最优子结构特性。
1. 与分治法的关系
分治法的基本思想是将问题分解成若干个相互独立的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。在用分治法求解时，由于分解得到的子问题数目太多，有些子问题被重复计算了许多次，以至于最后解决原问题需要耗费指数时间。
动态规划法基本思想也是将待求解问题分解成若干个子问题，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，它们可能共享更小的子问题，被称为重叠子问题（overlapping subproblem）。
第5章 动态规划
2. 与贪心法的关系
动态规划法与贪心法既有相同的地方也有区别。共同点是二者所解决的问题都有很强的步骤性，都要经过多步决策，最终得到最优解。区别在于，贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易做到，而动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解。所以，动态规划法可以处理不具备贪心准则的问题，这类问题使用贪心法不容易解决。
3. 设计动态规划算法
通常，设计一个动态规划算法可以按以下4个步骤进行。
（1）找出最优解的性质，并刻画最优解的结构特性；
（2）递归定义最优解值；
（3）以自底向上方式计算最优解值；
（4）根据计算得到的信息构造一个最优解。
第5章 动态规划
要统计计算fib(n)需要递归调用fibonacci函数的次数，只要增加一个全局变量即可。
Num=0;
int fibonacci(int n)
{Num++;
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
如果我们调用fib(5)，将产生一棵对于同一值重复计算多次的调用树：
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
特别是，fib(2)计算了3次。在更大规模的例子中，还有更多fib的值被重复计算，将消耗指数级时间。
从上图可知，同一个值被计算了多次，如fib(3)计算了3次，fib (2)计算了5次，也就是说随着程序的运行，进行了很多冗余的计算，也就是计算那些已经知道答案的值，这就产生了重叠，相互之间共享了一些数据，实际上，它们之间共享了很多数据。这种情况很普遍。解决的方法之一是(称为memoization方法或缓存方法)
：在第一次计算出函数值时就把值记下，然后以后需要时进行查找。这种方法在知道会重复使用某个值时很有用。
用这种方法求fib（6）只要调用函数11次。
Fib（30）=1346269
Fib（30）=59 （缓存方法）
该方法的具体做法是设置一个全局数组A[N+1],初始值都为0；
对每个I，其A[i]为0表示它的值还没计算出来。
/*备忘录方法求解斐波那契数列, 首先去查是否已经被计算出来
过，如果已经计算出来了（其值大于0），则不递归求解其值 ，直
接返回其值即可，否则（其值为0）递归求解其值 */