下载此文档

算法设计与分析.ppt


文档分类:中学教育 | 页数:约70页 举报非法文档有奖
1/70
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/70 下载此文档
文档列表 文档介绍
算法设计与分析
山东师范大学计算机系
授课:徐连诚,软件工程研究所(3432)
2005年9月5日—2006年1月20日
主页:http://lchxu./ 邮箱:lchxu@
镜像:http://lchxu1./(迅腾) http://lchxu2./(网易)
第三章动态规划
本章主要知识点:(11)
矩阵连乘问题
动态规划算法的基本要素
最长公共子序列问题
最大子段和
凸多边形的最优三角剖分
多边形游戏
图像压缩
电路布线
流水作业调度
0-1背包问题
最有二叉搜索树
动态规划加速原理>
2
引言
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
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)
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)
Those who cannot remember the past are doomed to repeat it.
——e Santayana,
The life of Reason,
Book I: Introduction and Reason
mon Sense (1905)
3
动态规划基本步骤
找出最优解的性质,并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息,构造最优解。
4
矩阵连乘问题
给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的,i=1,2,...,n-1。考察这n个矩阵的连乘积A1A2...An。
由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。
完全加括号的矩阵连乘积可递归地定义为:
单个矩阵是完全加括号的;
矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号,即A=(BC)。
设有四个矩阵A,B,C,D,它们的维数分别是:A=50×10,B=10×40,C=40×30,D=30×5
总共有五种完全加括号的方式:(A((BC)D)) (A(B(CD))) ((AB)(CD)) (((AB)C)D) ((A(BC))D)
其数乘次数分别为:16000, 10500, 36000, 87500, 34500
5
穷举搜索法
问题描述:给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。
算法复杂度分析:
对于n个矩阵的连乘积,设其不同的计算次序为P(n)。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:

也就是说,P(n)是随n的增长成指数增长的。
6
动态规划法——
下面我们考虑用求解。
预处理:
将矩阵连乘积A1A2...An简记为A[i:j],这里i≤j。
考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开,i≤k<j,则其相应完全加括号方式为(A1A2... Ak)(Ak+1 Ak+2... An )。
计算量:A[i:k]的计算量加上A[k+1:j]的计算量,再加上A[i:k]和A[k+1:j]相乘的计算量。
分析最优解的结构
特征:计算A[i:j

算法设计与分析 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数70
  • 收藏数0 收藏
  • 顶次数0
  • 上传人825790901
  • 文件大小556 KB
  • 时间2018-03-17