基本算法设计策略动态规划.ppt
IV.IV.动态规划动态规划14.1引言50年代1951年，R.Bellman等人提出多阶段决策问题;1957年，出版“动态规划”。优点：对许多问题，比线性规划或非线性规划更有效。弱点：（1）得出函数方程后，尚无统一处理方法；（2）维数屏蔽:变量个数（维数）太大时无法解决。模型分类时间参量确定随机离散：离散决策过程连续：连续决策过程确定性决策过程随机性决策过程24.2 确定连续性问题确定连续性问题（1）例在的约束下，或的极大值。对应递推关系令34.2 确定连续性问题确定连续性问题（2）故得x=a/3，用归纳法可证明当4例例4.2.2.最短距离（最短距离（1）求O到T的最短距离(只沿正向前进)。解：O到T的最短路径，也是该路径上点到T的最短路径3345例例4.2.2.最短距离（最短距离（2）6例例4.2.2.最短距离（最短距离（3）故O到T的最短距离为11，路径为OBD/EHKNRT一般地，从（0，0）到（m，n）最短距离：穷举法加法：比较：动态规则法：加法：2mn（mn2）比较：mn即穷举法是n的指数级，而动态规则是平方级。74.3动态规则的基本概念动态规则的基本概念84.4典型应用典型应用最优二叉查找树(1)例：最优二叉查找树简化的情形：只考虑找到的情形；LRi12345keysC1C2C3C4C50.30.050.080.450.12LRCk9最优二叉查找树最优二叉查找树(2)计算矩阵（由查找树的特点可知）1234510304200530084045501210最优二叉查找树最优二叉查找树(3)计算过程：根：1对应于：2112同样可得根：3根：4根：411最优二叉查找树最优二叉查找树(4)计算含有三个点的情形：根：1根：4根：412最优二叉查找树最优二叉查找树(5)四个点：根：4根：4最后：根：41345132得到的最优查找树如下得到的最优查找树如下14图上的最短路径图上的最短路径(1)例：图上的最短路径令为到终点的最短距离，为与相邻点集合：，则一般地15图上的最短路径图上的最短路径(2)动态规则算法:k=1:k=2:16图上的最短路径图上的最短路径(3)k=3:k=4:k=5:即k=5时已无改变。对n个顶点问题，迭代次数不超过n1次。求两者最短距离时k1最佳原理：不论前面地状态和策略如何，以后的最优策略只取决于由最初策略所决定的当前状态。17整数规划问题整数规划问题(1)例：某工厂购进1000台机器，准备生产甲、乙两种产品，若生产产品甲，每年收入4500元，损坏率达65；若生产产品乙，每年收入3500元，但损坏率为35；估计3年后有新机器购进，旧机器全部淘汰。问应如何安排生产，使3年内收入最多？（计划以一年为周期）该问题为整数规划问题：该生产产品甲的机器数分别为，三年中生产产品乙的机器数分别为，则为整数，i1，2，3。设为n台机器在i年后的最大收益，若安排一年生产为生产产品甲的数目，则一年后最大收益:18整数规划问题整数规划问题(2)考虑两年生产，为两年中第一年生产产品甲的机器数目：三年中第一年生产机器甲的数目为故第一年全部生产产品乙；第二年继续生产乙；第三年生产产品甲实际产品收入为19从顶点出发，经回到的最短路径。可能路径：n！令表示从出发，经V中各点一次，最后返回的最短路径；其中V为一顶点集合，则货郎担（旅行商）问题货郎担（旅行商）问题(1)20货郎担（旅行商）问题货郎担（旅行商）问题(2)21货郎担（旅行商）问题货郎担（旅行商）问题(3)22复杂性分析复杂性分析（1）一般情况：令结点为，为起始点，23复杂性分析复杂性分析（2）第1层1第2层第3层第k层故如果利用一个单元存储一个，则存储单元数为空间当为24时间复杂度时间复杂度 第1层n第2层n-1第3层n-2第k层nk1该问题目前有效解法基本上为各式概率算法:25习题习题求：(1)maxz=110 x1+160 x2+260 x3+210 x42x1+3x2+5x3+4x420为零或正整数(2)x1+x2+x3100 x1，x2，x3026背包问题背包问题(1)maxz=c1x1+c2x2+cnxna1x1+a2x2+anxnbxi=0,1.i=1,2,n.令计算：27背包问题背包问题(2)28背包问题背包问题(3)故最优解为maxz=6，当x1x31,x20时若取实数，则应当使单位容量获利最大三种物品1232/13/24/5取x11，x21，x3（61x12x2）/5=3/5。29Viterbi译码算法30状态转移1/101/010/010/101/001/110/110/001110010031状态：输入1或0时，进入新状态，产生输出译码时CodeTrellis考虑所收到码字：1110111101011132矩阵链积可能的方法1 2 3456789101112115144213242914304862167965878620801233例：考虑个矩阵的积，每个的为10*2020*5050*11*100M1*（M2*（M3*M4）：125，000（M1*（M2*M3）*M4：2200Mi,i=0Forl=1tonForI=1ton-1j=i+1;Mij=mini=kj(mik+mk+1j+(ri-1*rk*rj)34项目文档要求文档应包含如下几部分：（1）问题的说明、动态（2）问题的若干种解法、复杂度分析（3）算法的具体实现描述，给出主要的流程图（4）可能的改进或更有效的方法附：源程序截止时间：2004年12月28日35
