《动态规划算法》ppt课件

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

1、Chapter7动态规划DynamicProgrammingWhatisdynamicprogramming与分治法类似,动态规划也是通过组合子问题的解来求解问题.分治算法将问题划分成独立子问题,递归地解决这些子问题,然后组合这些子问题的解来求解原始问题.Ifthesesubproblemsarenotindependent,whatwillhappen?8/21/20212算法总体思想动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=8/21/20213但是经分解得到的子问题往往不是

2、互相独立的.不同子问题的数目常常只有多项式量级.在用分治法求解时,有些子问题被重复计算了许多次.算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)8/21/20214算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Thosewhocannotrem

3、emberthepastaredoomedtorepeatit.(无法记取教训者必重蹈覆辙)-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法.8/21/20215Fibonaccisequence(序列)Fibonacci序列定义如下：1.proceduref(n)2.ifn=1orn=2thenreturn13.elsereturnf(n

4、-1)+f(n-2)这种递归形式有简洁、容易书写和容易查错等优点,最主要是它的抽象性.但是它远不是有效的算法.算法复杂性:(n)Why???8/21/20216Fibonaccisequence分析f(n)=f(n-1)+f(n-2)=2f(n-2)+f(n-3)=3f(n-3)+2f(n-4)=5f(n-4)+3f(n-5)8/21/20217二项式系数的计算有效计算上式的方法是按行构造帕斯卡三角形8/21/20218Whatisdynamicprogramming什么是动态规划？当子问题发生重叠时,分治法做了很多不必要的工作——重复对重叠的子问题进行求解.

5、动态规划算法对每个子问题求解一次,然后将结果保存在一张表里面,这样可以避免每个已求解子问题的重复计算.对于Fibonacci序列,一个明显的方法是从f(1)开始自底向上地计算到f(n),只需要(n)时间和(1)空间.和前面的方法相比,可以很大程度降低时间复杂度.8/21/20219Thelongestcommonsubsequenceproblem最长公共子序列问题在字母表上,分别给出两个长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度.这里A=a1a2...an的子序列的一个形式为ai1ai2...aik的字符串,其中每个ij在1到n之间,并

6、且1i1

7、i,j]=L[i-1,j-1]+1若aibj,L[i,j]=max{L[i,j-1],+L[i-1,j]}可得如下公式：8/21/202112现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对i和j的值，0in，0jm，我们用一个(n+1)×(m+1)表来计算L[i,j]的值，只需要用上面的公式逐行地填表L[0…n,0…m]。算法如下：8/21/202113Algorithm7.1LCSInput:TwostringsAandBoflengthnandm,respectively,overanalphabetOutput:Thelengtho

8、fthel