文档介绍：该【计算机算法贪心算法PPT课件】是由【书犹药也】上传分享，文档一共【57】页，该文档可以免费在线阅读，需要了解更多关于【计算机算法贪心算法PPT课件】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第5讲动态规划
1
1/57
学****关键点:
了解动态规划算法概念。
掌握动态规划算法基本要素
(1)最优子结构性质
(2)重合子问题性质
掌握设计动态规划算法步骤。
(1)找出最优解性质,并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上方式计算出最优值。
(4)依据计算最优值时得到信息,结构最优解。
2
2/57
经过应用范例学****动态规划算法设计策略。
(1)矩阵连乘问题;
(2)最长公共子序列;
(3)最大子段和
(4)凸多边形最优三角剖分;
(5)多边形游戏;
(6)图像压缩;
(7)电路布线;
(8)流水作业调度;
(9)背包问题;
(10)最优二叉搜索树。
3
3/57
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题
算法总体思想
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
4
4/57
不过经分解得到子问题往往不是相互独立。不一样子问题数目经常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许屡次。
算法总体思想
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
5
5/57
假如能够保留已处理子问题答案,而在需要时再找出已求得答案,就能够防止大量重复计算,从而得到多项式时间算法。
算法总体思想
n
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
n/2
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
T(n/4)
T(n)
6
6/57
动态规划基本步骤
找出最优解性质,并刻划其结构特征。
递归地定义最优值。
以自底向上方式计算出最优值。
依据计算最优值时得到信息,结构最优解。
7
7/57
完全加括号矩阵连乘积可递归地定义为:
设有四个矩阵,它们维数分别是:
总共有五中完全加括号方式
(1)单个矩阵是完全加括号;
(2)矩阵连乘积是完全加括号,则可
表示为2个完全加括号矩阵连乘积和
乘积并加括号,即
16000,10500,36000,87500,34500
完全加括号矩阵连乘积
8
8/57
矩阵连乘问题
给定n个矩阵,其中与是可乘,。考查这n个矩阵连乘积
因为矩阵乘法满足结合律,所以计算矩阵连乘能够有许多不一样计算次序。这种计算次序能够用加括号方式来确定。
若一个矩阵连乘积计算次序完全确定,也就是说该连乘积已完全加括号,则能够依此次序重复调用2个矩阵相乘标准算法计算出矩阵连乘积
9
9/57
矩阵连乘问题
给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘,i=1,2…,n-1。怎样确定计算矩阵连乘积计算次序,使得依此次序计算矩阵连乘积需要数乘次数最少。
穷举法:列举出全部可能计算次序,并计算出每一个计算次序对应需要数乘次数,从中找出一个数乘次数最少计算次序。
算法复杂度分析:
对于n个矩阵连乘积,设其不一样计算次序为P(n)。
因为每种加括号方式都能够分解为两个子矩阵加括号问题:(A1...Ak)(Ak+1…An)能够得到关于P(n)递推式以下:
10
10/57