资源描述：
《数据结构与算法 动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章动态规划动态规划概述数塔最小代价子母树非优化问题实例单起点最短路径问题Warshall传递闭包算法完全最短路径问题的Floyd算法最优二叉查找树01背包问题本章习题动态规划概述动态规划概述动态规划（DynamicProgramming），在20世纪50年代由美国数学家RichardBellman（理查德.贝尔曼）提出，作为多阶段决策过程最优化的一种通用算法设计法，不仅解决特定类型的最优化问题，也包括某些非最优化问题。多阶段决策过程最优化诸多实际问题：有多个解，但要找到最优解。穷举法通过找出全部解，再从中找出最优解。对于那些计算复杂度高的如组合问题，找出其全部解所耗费的计算时间往
2、往不可接受！为降低求解难度，把求解过程分为一系列阶段，各个阶段按最优性原则计算，在最后阶段可得最优解。包括：分段、求解两大步。——不能段化的问题不能用动态规划法求解。最优性原则阶段1阶段2......阶段n求解算法求解算法求解算法多阶段决策过程动态：求解算法施加的状态是变化的。当前状态只与直接前趋有关，对直接前趋施加求解算法，成为当前状态。最优性原则(PrincipleofOptimality):问题的最优解，是由其子问题的最优解组成。特定问题该原则不一定满足（罕见），因此，有必要检查该原则的适用性。某些多阶段决策问题本身没有最优化要求，如后面的中国象棋马从棋盘上一点移到另一点的全路
3、径问题，又如计算裴波那契序列的动态规划算法，都属于非最优化问题的动态规划法。动态规划法的特点：1.分阶段计算。对最优化问题，各阶段满足最优性原则。2.一般用自顶向下分析（规模减小），自底向上实现（规模增加）。计算过程：一阶段一阶段地向前推进，直到最终状态。数塔数塔有一个三角形数塔如图。求一条自塔顶到塔底的路径，该路径上节点值之和最大。（注意动态规划法与穷举法、贪婪法的区别）贪婪算法：从塔顶到塔底，13+12+16+15+24=80问题分段：每一级台阶划分为一个阶段——多阶段决策优化问题。逐段计算：当前问题的最优解由各子问题的最优解组成。如：max(12+6,7+6)=18，max(4
4、0+18,40+27)=67,......5级4级3级2级1级1827393267465578679113111274014161582467131211数塔问题：动态规划法与穷举法效率比较数塔：动态规划法与穷举法的时间效率比较输入规模：为便于分析，选数塔层数k,k>0基本操作：加法运算效率类别：无最佳、最差（均从塔顶到塔底）增长函数T(k)：各层节点数：1,2,3,4,5,......节点的总数：1,3,6,10,15,......数塔层数k：1,2,3,4,5,......路径总数t：0,2,4,8,16,......t=2k-1,k>01.穷举法：T(k)=(k-1)2k-1，
5、k>0指数型本例k=5，每条路径5个节点做k-1=4次加法，共64次。2.动态规划法：（层节点数=层数）塔底向塔顶计算，第k层加法总数为第k-1层的节点数×2：T(k)=2×(k-1+...+3+2+1)=k(k-1),k>0平方型本例k=5，加法总数2×(4+3+2+1)=20次最小代价子母树最小代价子母树有n≥2堆沙子，重量向量W=(w1,...wn)，将它们归并为1堆。规则：只能将相邻2堆归为1堆，经过n-1次归并后成为1堆。要求：找到代价最小的归并方案。代价：新产生沙堆的质量和。代价最小的归并树即最小代价子母树。动态规划法求解：问题分段：将每次归并划分为一个阶段，共n-1个阶
6、段。逐段计算：自底向上（规模增大n=2,3,...,n-1）n=2：1种归并法即2合1.n=3：2种归并法，第1种归并法如图，前1堆后2堆c(i,j)——从第i堆到第j堆的代价和w(i,j)——从第i堆到第j堆的重量和c(1,3)=15+28=43=c(2,3)+w(1,3)13781528序号12313781621418n=7最小代价子母树(续1)n=4n=3：第2种归并法，前2堆后1堆n=4：有3大类归并法。前1堆后3堆、前2堆后2堆、前3堆后1堆3堆又有2种归并法，共5小类归并法。前1堆情况1：78163115序号12341344c(1,4)=15+31+44=90=c(2,4
7、)+w(1,4)c(1,3)=20+28=48=c(1,2)+w(1,3)n=3最优归并方案：c(1,3)=min{c(2,3),c(1,2)}+w(1,3)13782028序号123最小代价子母树(续2)n=4n=4：前1堆情况2：781624311344序号1234c(1,4)=24+31+44=99=c(2,4)+w(1,4)n=4：前2堆781624201344序号1234c(1,4)=20+24+44=88=c(1,2)+c(3,4)+w(1,4
