算法设计与分析讲义chapter4.docx
《算法设计与分析讲义chapter4.docx》由会员分享,可在线阅读,更多相关《算法设计与分析讲义chapter4.docx(20页珍藏版)》请在冰点文库上搜索。
算法设计与分析讲义chapter4
第四章DynamicProgramming技术
4.1DynamicProgramming概述
·优化问题:
一个优化问题可能有很多解,每个解有一
个代价,我们希望选择一个具有最少代价
的解。
一个优化问题可能有多个优化解。
·动态规划方法:
·DynamicProgramming方法适用于:
当一个优化问
题可分为多个子问题,子问题的解被重复使用。
·DynamicProgramming方法求解每个子问题仅一次,
并保存其结果,以后用到时直接存取,不重复计算,
——节省计算时间。
·DynamicProgramming方法自底向上,而divid-
and-conque方法自顶向下。
·动态规划算法的书记步骤
①分析优化解的结构
②递归地定义最优解的代价
③自底向上地计算优化解的代价保存之,
并获取构造最优解的信息。
④根据构造最优解的信息构造优化解
4.2.Matrix-chainMultiplication
4.2.1问题的提出
·矩阵链乘法问题
输入:
Ai是矩阵
输出:
矩阵乘积A1A2…An
·矩阵链乘法的实现
·矩阵乘法满足结合率。
·计算一个矩阵链的乘法可有多种方法:
·例如:
(A1A2A3A4)=(A1(A2(A3A4)))
=((A1A2)(A3A4))
....
=((A1A2)A3)A4)
·两个矩阵的乘法AB的代价依赖于计算的顺序
·复杂性测度:
乘法的次数
·AB的代价:
设A是pq矩阵,B是qr矩阵,
则计算AB的时间是0(pqr).
·矩阵链乘法的代价
设A1=10100矩阵,A2=1005矩阵,A3=550矩阵,则
·T((A1A2)A3)=101005+10550=5000+2500=7500
·T((A1A2)A3)=100550+1010050
=25000+50000=750000.
·结论:
不同解法有不同的代价。
·矩阵链乘法优化问题
输入:
,Ai是pi-1pi矩阵
输出:
代价最小的计算A1A2...An的方法
·矩阵链乘法优化问题的解空间
设p(n)=计算具有n个矩阵的矩阵链乘积的方法数
1ifn=1
p(n)=
ifn2
p(n)=C(n-1)=Catalan数=
=(4n/n
)
*如此之大的解空间是无法用枚举方法求出最优解的!
4.2.2优化解的结构
·几个记号
·Ai-j=AiAi+1....Aj
·cost(Ai-j)=计算Ai-j的代价
·优化解的结构
·对于任意k,1k·cost(A1n)=cost(A1k)+cost(Ak+1n)+cost(A1kAk+1n)
·在A1n的优化解中,子问题A1k的解法必须是A1-k的优化
解,子问题Ak+1n的解必须是Ak+1n的优化解。
--问题的优化解包括子问题优化解
--Dynamic-programming可用的原因
4.2.3.优化解的代价方程
·假设
·m[i,j]=计算Ai-j的最小乘法数
·m[1,n]=计算Ain的最小乘法数
·A1...AkAk+1....An是优化解
·代价方程
m[i,i]=计算Aii=Ai的最小乘法数=0
m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj,其中,pi-1pkpj是计算
Ai-kAi-k所需要完成的乘法数,AI和Ak分别是pI-1pI和
pk-1pk矩阵.
*k实际上是不可预知.
0ifi=j
m[i,j]=
minik*以下令S[i,j]是Aij的优化解对应的k值.
4.2.4优化解代价方程的计算
1.递归计算方法
0ifi=j
m[1,n]=
min1k·算法:
IFi=jTHENReturn0;
m=∞;
Fork=1ton-1Do
x=m[1,k]+m[k+1,n]+popkpn;
IFxReturnm;
·算法复杂性分析
T(n)=
(T(k)+T(n-k)+
(1))
=
(1)+
(T(k)+T(n-k))
=
(1)+2
T(k)
=(n)+2
T(k)
(n)+2T(n-1)
(n)+(n-1)+22T(n-2)
(n)+(n-1)+....+
(1)+2n-1T
(1)
(2n)
*递归算法并不好于枚举算法
2.动态规划算法
·数据结构
·矩阵Ai:
Pi-1Pifori=1,2,...n,
·以为数组p=
·二维数组m[1..n,1..n],存储m[i,j]
·二维年数组s[1..n,1..n],存储计算m[i,j]时确定的
优化解对应的k值.
·基本思想
·对于ik·对于ikm[i,k],m[k+1,j],并加以存储。
·算法
Matrix-Chain-Order(p)
n=length(p)-1;
FORi=1TOnDO
M[i,i]=0;
FOR
=2TOnDO
FORi=1TOn-
+1DO
j=i+
-1;
m[i,j]=∞;
/*以下计算m[i,j]=minikFORkiToj-1DO
q=m[i,k]+m[k+1,j]+pi-1pkpj
IFqReturnmands.
·算法注释
=2:
i=1,2,...,n-
+1=n-1
j=i+
-1=i+1
计算m[k,k+1],1kn-1;
=3:
i=1,2,...,n-
+1=n-2
j=i+
-1=i+3-1=i+2
计算m[k,k+2],1kn-2;
=4:
i=1,2,....,n-
+1=n-3
j=i+l-1=i+4-1=i+3
计算m[k,k+3],1kn-3;
……
=n:
i=1,...n-
+1=n-n+1=1
j=i+
-1=1+n-1=n
计算m[1,n]
=2时:
计算m[i,i+1]需要m[i,k]和m[k+1,i+1],
ik
=3时:
计算m[i,i+2]需要m[i,k],m[k+1,i+2],ik
即m[i,i],m[i+1,i+2],m[i,i+1],m[i+2,i+2].
例:
I
1
2
3
4
5
6
6
5
4
3
2
1
0
5
4
3
2
1
0
4
3
2
1
0
3
2
1
0
2
1
0
1
0
0表示第0步(FORi=1ton)所计算的m[i,j]
1表示第1步(
=2)所计算的m[i,j]
……
5表示第5步(
=6)所计算的m[i,j]。
2.动态规划算法的复杂性分析
时间复杂性T(n)=0(n3)
空间复杂性S(n)=0(n2)
4.2.5.优化解的构造
·基本思想:
·S[i,j]=k,k是优化计算AiAi+1...Aj所需的划分
(Ai…Ak)(Ak+1...Aj).
·A1n的优化解由s[1,n]确定,即A1S[1,n]AS[1,n]+1n
·A1S[1,n]的优化解由s[1,s[1,n]]确定,即A1S[1,s[1,n]]
AS[1,s[1,n]]+1s[1,n]
·AS[1,n]+1n的优化解由s[s[1,n]+1,n]确定,即
As[1,n]+1s[s[1,n]+1,n]As[s[1,n]+1,n]+1n
·如此下去,我们可以递归地得到A1n的优化解。
·算法
Matrix-Chain-Multiply(A,s,i,j)
IFj>i
THENX=Matrix-Chain-Multiply(A,s,i,s[i,j]);
Y=Matrix-Chain-Multiply(A,s,s[i,j]+1,j);
ReturnMatrix-Multiply(X,Y);
ElseReturnAj
4.3动态规划原理
问题:
什么情况下可以应用DynamicProgramming
可用动态规划方法求解的问题必须满足:
1.具有Optimalsubstructure
2.具有Overlappingsub-problems
4.3.1Optimalsubstructure
1.优化结构
定义1.如果一个问题的优化解包含了他的子问题的优化解,
则称此问题具有优化结构。
*优化结构是应用动态规划方法的一个条件,也是应用Greedy
方法的一个条件,是否用动态规划方法,尚需看是否满足
Overlappingsubproblems条件。
例1.Matrix-Chain-Multiply问题具有优化结构,因为
A1...An的优化解(A1...An)(Ak+1...An)包含
子问题(A1...An)和(Ak+1…An)的优化解。
2.子问题空间
·理想情况:
子问题空间越小越好,可减少时间和空间复杂性。
例1.①Matrix-Chain-Multiply问题的子问题是所有子链
的集合。
②我们也可以使子空间为任意的矩阵子序例—太多
的无必要的子问题不得不被求解。
·合适子空间地确定
在分析问题的结构时,用循环方法可以得到一个好的子问题
空间。
例2.(A1…An)=(A1...Ak1)(Ak+1...An)
=((A1...Ak2)(Ak2+1...A1))
((Ak+1...Ak3)((Ak3+1...An))
……
最后得到子问题空间为S={AiAi+1...Aj1ijn}.
我们来计算S的大小。
S包括:
长为1的矩阵子链n个,
长为2的矩阵子链n-1个,……
长为n-1的矩阵子链2个,
长为n的矩阵子链1个.
于是,S的大小为n(n+1)/2。
4.3.2Overlappingsub-problems
1.相交子问题
定义2.如果递归算法求解一个优化问题时,反复求解相同的
子问题,则称该优化问题有相交子问题。
*DynamicProgramming方法利用这种特点,只计算每个子问
题一次并保存,避免反复计算相同子问题多次。
*Divid-and-conguer方法每次都产生新问题并计算之,而不
管是否该子问题已计算过。
2.Matrix-Chain-Multiply的递归分解算法
·算法
Recursive-Matrix-chain(p,i,j)
Ifi=jThenReturn0;
M[i,j]=∞;
Fork=iToj-1Do
q=Recursive-Matrix-chain(p,i,k)+
Recursive-Matrix-chain(p,k+1,j)+pi-1pkpj
IfqReturnm[i,j].
·复杂性分析
求m[1,n]的复杂性:
T
(1)1
T(n)1+
(T(k)+T(n-k)+1)
2
T(k)+n2T(n-1)+n22T(n-2)+2(n-1)+n
23T(n-3)+......2n-1T
(1)=0(2n)
4.3.3.Memoization
·基本思想
使低效的递归算法记忆化—用表记住子问题的解,供以后查
找,控制结构仍然是自顶向下的递归结构。
·Matrix-Chain-Multiply记忆算法
Matrix-Chain-Multiply(p)
1.n=length(p)-1
2.Fori=1TonDo
3.Forj=iTonDo
4.m[i,j]=∞;
5.ReturnLookup-chain(p,1,n).
Lookup-chain(p,i,j)
1.IFm[i,j]<∞THENReturnm[i,j];
2.IFi=jTHENm[i,j]=0;
3.ELSEFORk=iToj-1Do
q=Lookup-china(p,i,k)+Lookupchina(p,k+1,j)+
pi-1pkpj
4.Ifq5.Returnm[i,j].
·Matrix-Chain-Multiply算法的复杂性
共有0(n2)表项,每个表项调用一次Lookup-chain,每次调用
0(n)时间,T(n)=0(n3)
S(n)=0(n2)—m[1:
n,1:
n]
4.4最长公共子序列问题
4.4.1.问题定义
1.子序列
定义1.设x=(x1,x2,...xm)是一个序列,z=(z1,z2,...zm)是x的一个子序列,如果存在1i1例1.X=(A,B,C,B,D,A,B),Z=(B,C,D,B)是X的子序例。
2.公共子序列
定义2.Z是序列X与Y的公共子序列如果Z是X的子序列且Z是Y的子序列。
3.最长公共子序列问题(LCS)
输入:
X=(x1,x2,...xn),Y=(y1,y2,...ym)
输出:
Z=X与Y的最长公共子序列
6.4.2.最长公共子序列结构分析
定义3.设X=(x1,x2,...xn)是一个序列,X的第I前缀Xi是一个序列,定义为Xi=(x1,...xi)
例2.X=(A,B,D,C,A),X1=(A),X2=(A,B),X3=(A,B,D)
1.优化解的结构
定理1(LCS的优化结构)设X=(x1,...xm),Y=(y1,y2,...yn)是两个序列,Z=(z1,z2,...zk)是X与Y的LCS。
下列结论成立:
⑴如xm=yn,则zk=xm=yn,Zk-1是Xm-1和Yn-1的LCS,即,
LCSXY=LCSXm-1Yn-1+.
⑵若xmyn,且zkxm,则Z是Xm-1和Y的LCS,即
LCSXY=LCSXm-1Y
⑶若xm=yn,且zkyn,则Z是X与Yn-1的LCS,即
LCSXY=LCSXYn-1
证明.
⑴设zkxm,则可加xm=yn到Z,得到一个长为k+1的X与Y的公共序列,与Z是X和Y的LCS矛盾。
于是zk=xm=yn。
现在证明Zk-1是Xm-1与Yn-1的LCS。
显然Zk-1是Xm-1与Yn-1的公共序列,我们需要证明Zk-1是LCS。
设不然,则存在X与Y的公共子序列W,W的长大于k-1。
增加xm=yn到W,我们得到一个长大于k的X与Y的公共序列,与Z是LCS矛盾。
于是,Zk-1是Xm-1与Yn-1的LCS。
⑵由于zkxm,Z是Xm-1与Y的公共子序列。
我们来证Z是Xm-1与Y的LCS。
设Xm-1与Y有一个公共子序列W,W的长大于k,则W也是X与Y的公共子序列,与Z是LCS矛盾。
⑶同⑵可证。
证毕
*X和Y的LCS的优化解结构为
LCSXm-1Yn-1+ifxm=yn
LCSXY=LCSXm-1Yifxmyn,zkxm
LCSXYn-1ifxmyn,zkyn
2.相交子问题(见下边的递归图)
LCSXY
LCSXm-1Yn-1LCSXm-1YLCSXYn-1
LCSXm-2Yn-2LCSXm-2Yn-1LCSXm-1Yn-2LCSXm-2Yn-1LCSXm-2YLCSXm-1Yn-1.......
*求LCSXm-1Y和LCSXYn-1时都需要LCSXm-1Yn-1
.......
3.子问题空间
·X与Y的LCS问题空间由求X与Y的前缀的LCS问题构成。
·由于X的前缀个数为m个,Y的前缀个数为n个,求X与Y
的前缀的LCS问题的个数为m*n个。
于是子问题空间的大小
为(m*n)。
4.4.3建立求解LCS长度的递归方程
·定理1说明:
·Ifxm=yn,xm属于X和Y的LCS,须求解Xm-1和Yn-1的LCS。
·Ifxmyn,必须求解须求解Xm-1和Y的LCS以及须求解X和Yn-1
的LCS,长者是X和Y的LCS。
·令C[i,j]=Xi与Yj的LCS的长度,则
0ifi=0或j=0
C[i,j]=C[i-1,j-1]+1ifi,j>0andxi=yj
Max(C[i,j-1],C[i-1,j])ifi,j>0andxiyj
4.4.4LCS长度的计算
1.基本思想
计算C[i,j]需先计算C[i-1,j-1]、C[i,j-1]、C[i-1,j]
C[i-1,j-1]
C[i-1,j]
C[i,j-1]
C[i,j]
先计算出第0行与第0列,然后逐行计算。
2.算法
·数据结构
C[0:
m,0:
n]:
C[i,j]是Xi与Yj的LCS的长度
B[1:
m,1:
n]:
B[i,j]是指针,指向计算C[i,j]时所选择的
子问题的优化解所对应的C表的表项。
·算法
LCS-length(x,y)
mlength(x);nlength(y);
Fori1TomDoC[i,0]0;
Forj1TonDoC[0,j]0;
Fori1TomDo
Forj1TonDo
Ifxi=yj
ThenC[i,j]C[i-1,j-1]+1;B[i,j]“↖”;
ElseIfC[i-1,j]C[i,j-1]
ThenC[i,j]C[i-1,j];B[i,j]“↑”;
ElseC[i,j]C[i,j-1];B[i,j]“←”;
ReturnCandB.
4.4.5.构选优化解-LCS
1.基本思想
从B[m,n]开始按指针搜索,若B[i,j]=“↖”,则xi=yj是LCS的一个元素。
如此找到的“LCS”是X与Y的LCS的Inverse。
2.算法
Print-LCS(B,X,i,j)
IFi=0orj=0THENReturn;
IFB[i,j]=“↖”THENPrint-LCS(B,X,i-1,j-1);Printxi;
ELSEIfB[i,j]=“↑”THENPrint-LCS(B,X,i-1,j);
ELSEPrint-LCS(B,X,i,j-1).
*Print-LCS(B,X,length(X),length(Y))可打印出x与y的LCS。
例2.
Ij
0
1
2
3
4
5
6
7
B
D
C
A
B
A
0
0
0
0
0
0
0
0
1
A
0
0↑
0↑
0↑
↖1
←1
↖1
2
B
0
↖1
←1
←1
1↑
↖2
←2
3
C
0
1↑
1↑
↖2
←2
2↑
2↑
4
B
0
↖1
1↑
2↑
2↑
↖3
←3
5
D
0
1↑
↖2
2↑
2↑
3↑
3↑
6
A
0
1↑
2↑
2↑
↖3
3↑
↖4
7
B
0
↖1
2↑
2↑
3↑
↖4
4↑
4.5优化的多边形三角
4.5.1.基本概念
多边形:
一个多边形可以表示为顶点坐标的集合P=(v0,v1,...vn+1)或顶点序列v0v1,...vn-1vn。
定义1.一个多边形是简单的如果除了顶点以外没有任何边交叉点。
定义2.平面上由多边形封闭的点集合称为多边形的内部,多边形上的点集合称为多边形的边界,平面上除多边形内部和边界以外的点集合称为多边形的外部。
定义3.设P是一个多边形。
若P的边界或内部的任意两点的连线上的所有点都在P的内部或边界上,则称P是凸多边形。
定义4.多边形P上的任意两个不相邻结点vi、vi+1所对应的线段vivi+1称为弦。
定义5.(三角剖分)一个多边形P的三角剖分是将P划分为不相交三角形的弦的集合。
定义6.(优化三角剖分问题)设S是由多边形P的边和弦构成的三角形集合,W是S上的代价函数。
优化三角剖分问题定义为:
输入:
多边形P和代价函数W
输出:
求一个P的三角分T,使得
最小,其中ST是T
所对应的三角形集合。
4.5.2优化三角分的结构分析
设P=(v0,v1,...vn)是n+1点的多边形,
Tx是X的优化三角剖分,
则
TP=T(v0,...,vk)∪T(vk+1,...,vn)∪{v0vk,vkvn}
4.5.3优化三角剖分的代价函数
·代价函数
设t[i,j]=的优化三角剖分的代价,则:
t[i,i]=t[j,j]=0
t[i,j]=minjkj-1{t[i,k]+t[k+1,j]+w(Δvi-1vkvj)}.
·算法
与矩阵链乘法问题一致,把Matrix-chain-Order和Matrix-
chain-Multiply算法略加修改即可计算t[i,j]并构造优化
三角剖分解。