动态规划算法设计及应用课件.ppt

《动态规划算法设计及应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五讲动态规划算法设计及应用一、动态规划的定义动态规划解题方法是一种高效率的解题方法，可以解决相当大的信息量，其时间复杂性通常为O（n2）、O（n3）等。它适用的原则为优化原则，将整体优化可以分解为若干个局部优化。例如：求从A点到D点的最短路径。根据穷举算法，其运行时间复杂性为：n1*n2*n3,如果道路太多则时间复杂性计算值更大，如何优化程序，使时间复杂性能尽可能小。利用动态规划原理，可以使时间复杂性降低，本题优化的基本方法：二、动态规划应用实例1．设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发

2、，可以向左走或向右走，如图所示：从根结点13出发向左、向右的路径长度可以是：13——11——7——14——7其和为5213——11——12——14——13其和为63若要求从根结点开始，请找出一条路径，使路径之和最大，若存在多条请输出任意一条。问题分析：（1）贪心法往往得不到最优解：本题若采用贪心法则：13——11——12——14——13，其和为63但存在另一条路：13——8——26——15——24，其和为86贪心法问题所在：眼光短浅。根据贪心法，则13——11——21和45，而实质是13——8——40和61（2）若用穷

3、举法：从根结点开始，将所有可能的路径求和，找出最大值，但算法时间复杂性使问题解成为不可能。当N=1P=1N=2P=2N=3P=4…………………..N=KP=2K-1当N=50P=249=500万亿条路径。（3）动态规划求解过程分析：动态规划求解问题的过程归纳为：自顶向下的分析，自底向上计算。其基本方法是：A从根结点13出发，选取它的两个方向中的一条支路，选择根据是比较两个支路中其路径和最大的支路；B设X为从11出发到底端的最大路径值，Y为从8到底端的最大路径和CIFX>Ythen选择X且取得最大和为13+XElse选择

4、Y且取得最大和为13+Y这样原先求根结点到底端的最大路径问题，变为从11出发和从8出发求路径和的子问题（递归算法）同理，求从11出发到底端的最大路径问题可以化为从12出发和从7出发的最大路径问题。A．当到倒数第二层时，每个结点其后继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。自底向上计算：l从底层开始，本身数即为最大数；l倒数第二层的计算，取决于底层的数据：12+6=18，13+14=27，24+15=39，24+8=32l最后的路径为：13——8——26——8——24（4）

5、数据结构及算法设计A图形转化：直角三角形，便于搜索：向下、向右B用三维数组表示数塔：G[I，J，1]表示行、列、及结点本身数据，G[I，J，2]能够取得最大值，G[I，J，3]表示前进方向——0向下，1向右C算法：l数组初始化，输入每个结点值及初始的最大路径、前进方向为0l从倒数第二层开始向上一层求最大路径，共循环N-1次l从顶向下，输出路径：关键是J的值，由于行逐渐递增，表示向下，究竟向下还是向右取决于则看列的值。若J值比原先多1则向右否则向下。D．程序高级本P196例题2求一组数列的最长的不下降序列（1）问题描述：

6、设有一个正整数序列b1,b2,b3,……，bn,若下标i1

7、的长度，开始为1，b[i,3]开始为零，表示没有连接。l从倒数第二项开始计算，由于在其后仅有一个数据项，所以计算机做一次比较后保存最大数l同样再从倒数第3项看，其后有两项，因此必须在最后2项中找出最长的作为连接项看书p201页例题3挖地雷问题：P203例题4最小代价子母树设有一堆沙子排成一排，其编号为1，2，3，4…,n,每堆沙子重量如下：13，7，8，16，21，4，18现在将n堆沙子归并,使归并的总代价和最少。归并方法：每次只能将相邻的两堆沙子堆成一堆，经过n-1次后最后成一堆。沙子归并重量的和称为代价，全部代价称

8、为总代价。例如，当n=2时，仅有一种归并方法当n=3时总代价（1）20+24=44，总代价（2）11+24=35当n=4时总代价（1）S=20+34+40=94（2）21+34+40=95总代价是S=20+20+40=80，S=21+27+40=88，S=20+27+40=87当n=4时，有五种方法，总结归并的几种形式：前归并，两