基本算法设计策略动态规划

《基本算法设计策略动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IV.动态规划1§4.1引言50年代1951年，R.Bellman等人提出多阶段决策问题;1957年，出版“动态规划”。优点：对许多问题，比线性规划或非线性规划更有效。弱点：（1）得出函数方程后，尚无统一处理方法；（2）维数屏蔽:变量个数（维数）太大时无法解决。模型分类时间参量确定随机离散：离散决策过程连续：连续决策过程确定性决策过程随机性决策过程2§4.2确定连续性问题（1）例4.2.1．在的约束下，或的极大值。对应递推关系令3§4.2确定连续性问题（2）故得x=a/3，用归纳法可证明当4例4.2.2.最短距离（1）求O到T的最短距离(只沿正向前进)。解

2、：O到T的最短路径，也是该路径上点到T的最短路径3345例4.2.2.最短距离（2）6例4.2.2.最短距离（3）故O到T的最短距离为11，路径为O→B→D/E→H→K→N→R→T一般地，从（0，0）到（m，n）最短距离：穷举法加法：比较：动态规则法：加法：2mn＋（m＋n－2）比较：mn即穷举法是n的指数级，而动态规则是平方级。7§4.3动态规则的基本概念8§4.4典型应用—最优二叉查找树(1)例：最优二叉查找树简化的情形：只考虑找到的情形；LRi12345keysC1C2C3C4C50.30.050.080.450.12LRCk9最优二叉查找树(2)计

3、算矩阵（由查找树的特点可知）1234510．30．420．0530．0840．4550．1210最优二叉查找树(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个顶点问题，迭代次

4、数不超过n－1次。求两者最短距离时k≥1最佳原理：不论前面地状态和策略如何，以后的最优策略只取决于由最初策略所决定的当前状态。17整数规划问题(1)例：某工厂购进1000台机器，准备生产甲、乙两种产品，若生产产品甲，每年收入4500元，损坏率达65％；若生产产品乙，每年收入3500元，但损坏率为35％；估计3年后有新机器购进，旧机器全部淘汰。问应如何安排生产，使3年内收入最多？（计划以一年为周期）该问题为整数规划问题：该生产产品甲的机器数分别为，三年中生产产品乙的机器数分别为，则为整数，i＝1，2，3。设为n台机器在i年后的最大收益，若安排一年生产为生产产

5、品甲的数目，则一年后最大收益:18整数规划问题(2)考虑两年生产，为两年中第一年生产产品甲的机器数目：三年中第一年生产机器甲的数目为故第一年全部生产产品乙；第二年继续生产乙；第三年生产产品甲实际产品收入为19从顶点出发，经回到的最短路径。可能路径：n！令表示从出发，经V中各点一次，最后返回的最短路径；其中V为一顶点集合，则货郎担（旅行商）问题(1)20货郎担（旅行商）问题(2)21货郎担（旅行商）问题(3)22复杂性分析（1）一般情况：令结点为，为起始点，23复杂性分析（2）第1层1第2层第3层第k层故如果利用一个单元存储一个，则存储单元数为空间当为24时

6、间复杂度第1层n第2层n-1第3层n-2第k层n－k＋1该问题目前有效解法基本上为各式概率算法:25习题求：(1)maxz=110x1+160x2+260x3+210x42x1+3x2+5x3+4x4≤20为零或正整数(2)x1+x2+x3≥100x1，x2，x3>026背包问题(1)maxz=c1x1+c2x2+…+cnxna1x1+a2x2+…+anxn≤bxi=0,1.i=1,2,…,n.令计算：27背包问题(2)28背包问题(3)故最优解为maxz=6，当x1＝x3＝1,x2＝0时若取实数，则应当使单位容量获利最大三种物品1232/13/24/5取

7、x1＝1，x2＝1，x3＝（6－1•x1－2•x2）/5=3/5。29Viterbi译码算法30状态转移1/101/010/010/101/001/110/110/001110010031状态：输入1或0时，进入新状态，产生输出译码时CodeTrellis考虑所收到码字：1110111101011132矩阵链积可能的方法123456789101112115144213242914304862167965878620801233例：考虑个矩阵的积，每个的为[10*20][20*50][50*1][1*100]M1*（M2*（M3*M4））：125，000（M

8、1*（M2*M3））*M4：2200M[i,i]=0Forl=1t