第六章基本算法设计策略动态规划.pptVIP

IV.动态规划 §4.1引言 50年代 1951年，R.Bellman 等人提出 多阶段决策问题; 1957年， 出版“动态规划”。 优点：对许多问题，比线性规划或非线性规划更有效。 弱点： （1）得出函数方程后，尚无统一处理方法； （2）维数屏蔽:变量个数（维数）太大时无法解决。 模型分类 时间参量 确定随机 §4.2 确定连续性问题 （1） 例4.2.1．在 的约束下，或 的极大值。 对应递推关系 令 §4.2 确定连续性问题 （2） 故 得x=a/3， 用归纳法可证明 当 例4.2.2.最短距离（1） 求O到T的最短距离(只沿正向前进)。 解：O到T的最短路径，也是该路径上点到T的最短路径 例4.2.2.最短距离（2） 例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的指数级，而动态规则是平方级。 §4.3动态规则的基本概念 §4.4典型应用 —最优二叉查找树 (1) 例：最优二叉查找树 简化的情形：只考虑找到的情形； LR 最优二叉查找树 (2) 计算矩阵 （由查找树的特点可知） 最优二叉查找树 (3) 计算过程： 根：1 对应于： 2 1 1 2 同样可得 根：3 根：4 根：4 最优二叉查找树 (4) 计算含有三个点的情形： 根：1 根：4 根：4 最优二叉查找树 (5) 四个点： 根：4 根：4 最后： 根：4 图上的最短路径 (1) 例：图上的最短路径 令 为 到终点的最短距离， 为与 相邻点集合： ，则一般地 图上的最短路径 (2) 动态规则算法 : k=1: k=2: 图上的最短路径 (3) k=3: k=4: k=5: 即k=5时已无改变。对n个顶点问题，迭代次数不超过n－1次。 求两者最短距离时 k≥1 最佳原理：不论前面地状态和策略如何，以后的最优策 略只取决于由最初策略所决定的当前状态。 整数规划问题 (1) 例：某工厂购进1000台机器，准备生产甲、乙两种产品，若生产产品甲，每年收入4500元，损坏率达65％；若生产产品乙，每年收入3500元，但损坏率为35％；估计3年后有新机器购进，旧机器全部淘汰。问应如何安排生产，使3年内收入最多？（计划以一年为周期） 该问题为整数规划问题：该生产产品甲的机器数分别为 ， 三年中生产产品乙的机器数分别为 ，则 为整数，i＝1，2，3。 设 为n台机器在i年后的最大收益，若安排一年生产为生产产品甲的数目，则一年后最大收益: 整数规划问题 (2) 考虑两年生产， 为两年中第一年生产产品甲的机器数目： 三年中第一年生产机器甲的数目为 故第一年全部生产产品乙；第二年继续生产乙；第三年生产产品甲 实际产品收