計(jì)算機(jī)算法設(shè)計(jì)與分析【王曉東-電子工業(yè)出版社-2版】-第3章.ppt_第1頁(yè)
計(jì)算機(jī)算法設(shè)計(jì)與分析【王曉東-電子工業(yè)出版社-2版】-第3章.ppt_第2頁(yè)
計(jì)算機(jī)算法設(shè)計(jì)與分析【王曉東-電子工業(yè)出版社-2版】-第3章.ppt_第3頁(yè)
計(jì)算機(jī)算法設(shè)計(jì)與分析【王曉東-電子工業(yè)出版社-2版】-第3章.ppt_第4頁(yè)
計(jì)算機(jī)算法設(shè)計(jì)與分析【王曉東-電子工業(yè)出版社-2版】-第3章.ppt_第5頁(yè)
已閱讀5頁(yè),還剩84頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、上海金融學(xué)院信息管理系,1,第3章 動(dòng)態(tài)規(guī)劃,上海金融學(xué)院信息管理系,2,學(xué)習(xí)要點(diǎn): 理解動(dòng)態(tài)規(guī)劃算法的概念。 掌握動(dòng)態(tài)規(guī)劃算法的基本要素 (1)最優(yōu)子結(jié)構(gòu)性質(zhì) (2)重疊子問(wèn)題性質(zhì) 掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。 (1)找出最優(yōu)解的性質(zhì),并刻劃其結(jié)構(gòu)特征。 (2)遞歸地定義最優(yōu)值。 (3)以自底向上的方式計(jì)算出最優(yōu)值。 (4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息,構(gòu)造最優(yōu)解。,上海金融學(xué)院信息管理系,3,通過(guò)應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。 (1)矩陣連乘問(wèn)題; (2)最長(zhǎng)公共子序列; (3)最大子段和 (4)凸多邊形最優(yōu)三角剖分; (5)多邊形游戲; (6)圖像壓縮; (7)電路布線; (8)流水作

2、業(yè)調(diào)度; (9)背包問(wèn)題; (10)最優(yōu)二叉搜索樹(shù)。,上海金融學(xué)院信息管理系,4,動(dòng)態(tài)規(guī)劃算法與分治法類似,其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題,算法總體思想,上海金融學(xué)院信息管理系,5,但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí),有些子問(wèn)題被重復(fù)計(jì)算了許多次。,算法總體思想,上海金融學(xué)院信息管理系,6,如果能夠保存已解決的子問(wèn)題的答案,而在需要時(shí)再找出已求得的答案,就可以避免大量重復(fù)計(jì)算,從而得到多項(xiàng)式時(shí)間算法。,算法總體思想,T(n),上海金融學(xué)院信息管理系,7,動(dòng)態(tài)規(guī)劃基本步驟,找出最優(yōu)解的性質(zhì),并刻劃其結(jié)構(gòu)特征。 遞歸地定義最

3、優(yōu)值。 以自底向上的方式計(jì)算出最優(yōu)值。 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息,構(gòu)造最優(yōu)解。,上海金融學(xué)院信息管理系,8,(1)單個(gè)矩陣是完全加括號(hào)的; (2)矩陣連乘積 是完全加括號(hào)的,則 可 表示為2個(gè)完全加括號(hào)的矩陣連乘積 和 的乘積并加括號(hào),即,16000, 10500, 36000, 87500, 34500,完全加括號(hào)的矩陣連乘積可遞歸地定義為: 設(shè)有四個(gè)矩陣 ,它們的維數(shù)分別是: 總共有五中完全加括號(hào)的方式,完全加括號(hào)的矩陣連乘積,上海金融學(xué)院信息管理系,9,3.1 矩陣連乘問(wèn)題,給定n個(gè)矩陣 , 其中 與 是可乘的, 。考察這n個(gè)矩陣的連乘積 由于矩陣乘法滿足結(jié)合律,所以計(jì)算矩陣的連乘可以

4、有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。 若一個(gè)矩陣連乘積的計(jì)算次序完全確定,也就是說(shuō)該連乘積已完全加括號(hào),則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積,上海金融學(xué)院信息管理系,10,矩陣連乘問(wèn)題,給定n個(gè)矩陣A1,A2,An,其中Ai與Ai+1是可乘的,i=1,2,n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序,使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。,窮舉法:列舉出所有可能的計(jì)算次序,并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù),從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。,算法復(fù)雜度分析: 對(duì)于n個(gè)矩陣的連乘積,設(shè)其不同的計(jì)算次序?yàn)镻(n)。 由于每種加括號(hào)方式都

5、可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題:(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下:,上海金融學(xué)院信息管理系,11,矩陣連乘問(wèn)題,窮舉法 動(dòng)態(tài)規(guī)劃,將矩陣連乘積 簡(jiǎn)記為Ai:j ,這里ij,考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣 Ak和Ak+1之間將矩陣鏈斷開(kāi),ikj,則其相應(yīng)完全 加括號(hào)方式為,計(jì)算量:Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量,再加上 Ai:k和Ak+1:j相乘的計(jì)算量,上海金融學(xué)院信息管理系,12,特征:計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。 矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性

6、質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。,分析最優(yōu)解的結(jié)構(gòu),上海金融學(xué)院信息管理系,13,建立遞歸關(guān)系,設(shè)計(jì)算Ai:j,1ijn,所需要的最少數(shù)乘次數(shù)mi,j,則原問(wèn)題的最優(yōu)值為m1,n 當(dāng)i=j時(shí),Ai:j=Ai,因此,mi,i=0,i=1,2,n 當(dāng)ij時(shí), 可以遞歸地定義mi,j為:,這里 的維數(shù)為,的位置只有 種可能,上海金融學(xué)院信息管理系,14,計(jì)算最優(yōu)值,對(duì)于1ijn不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問(wèn)題。因此,不同子問(wèn)題的個(gè)數(shù)最多只有 由此可見(jiàn),在遞歸計(jì)算時(shí),許多子問(wèn)題被重復(fù)計(jì)算多次。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。 用

7、動(dòng)態(tài)規(guī)劃算法解此問(wèn)題,可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中,保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一次,而在后面需要時(shí)只要簡(jiǎn)單查一下,從而避免大量的重復(fù)計(jì)算,最終得到多項(xiàng)式時(shí)間的算法,上海金融學(xué)院信息管理系,15,void MatrixChain(int *p,int n,int *m,int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij =

8、 i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; ,算法復(fù)雜度分析: 算法matrixChain的主要計(jì)算量取決于算法中對(duì)r,i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1),而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。,上海金融學(xué)院信息管理系,16,用動(dòng)態(tài)規(guī)劃法求最優(yōu)解,上海金融學(xué)院信息管理系,17,#include stdafx.h #include void MatrixChain(int* p,i

9、nt n,int m7,int s7); void Traceback(int i,int j,int s7); int main(int argc, char* argv) int n=6; int m66; int s66; int p7; for (int i=0;ipi; MatrixChain(p,n,m,s); Traceback(1,n,s); return 0; ,上海金融學(xué)院信息管理系,18,void MatrixChain(int* p,int n,int m6,int s6) for (int i = 1; i = n; i+) mii = 0; for (int r =

10、 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; ,上海金融學(xué)院信息管理系,19,void Traceback(int i,int j,int s6) if(i=j)return; Traceback(i,sij,s); Traceback(sij+1,j,s); coutMul

11、tiply Ai,sij; coutand Asij+1,jendl; ,上海金融學(xué)院信息管理系,20,#include stdafx.h #include void MatrixChain(int* p,int n,int m6,int s6); void Traceback(int i,int j,int s6); int main(int argc, char* argv) int n=6; int m66; int s66; int p7; for (int i=0;ipi; for (int ii=0;ii=n;ii+) coutpii ; coutendlendlendl; Mat

12、rixChain(p,n,m,s); /coutnendl; Traceback(1,6,s); return 0; ,void MatrixChain(int* p,int n,int m6,int s6) for (int i = 1; i = n; i+) mii = 0; sii = 0; for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk

13、+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; for (int ii = 1; ii = n; ii+) for (int jj = ii; jj = n; jj+) cout.width(10); coutmiijj; coutendl; coutendlendl; for (int iii = 1; iii = n; iii+) for (int jjj = iii; jjj = n; jjj+) cout.width(10); coutsiiijjj; coutendl; coutendlendl; void Traceback(int i

14、,int j,int s6) if(i=j)return; Traceback(i,sij,s); Traceback(sij+1,j,s); coutMultiply Ai,sij; coutand Asij+1,jendl; ,上海金融學(xué)院信息管理系,21,3.2 動(dòng)態(tài)規(guī)劃算法的基本要素,一、最優(yōu)子結(jié)構(gòu),矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。 在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí),所用的方法具有普遍性:首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的,然后再設(shè)法說(shuō)明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解,從而導(dǎo)致矛盾。 利用問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì),以自底

15、向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。,同一個(gè)問(wèn)題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu),有些表示方法的求解速度更快(空間占用小,問(wèn)題的維度低),上海金融學(xué)院信息管理系,22,動(dòng)態(tài)規(guī)劃算法的基本要素,二、重疊子問(wèn)題,遞歸算法求解問(wèn)題時(shí),每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題,有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)。 動(dòng)態(tài)規(guī)劃算法,對(duì)每一個(gè)子問(wèn)題只解一次,而后將其解保存在一個(gè)表格中,當(dāng)再次需要解此子問(wèn)題時(shí),只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。 通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間,從而獲

16、得較高的解題效率。,上海金融學(xué)院信息管理系,23,上海金融學(xué)院信息管理系,24,動(dòng)態(tài)規(guī)劃算法的基本要素,三、備忘錄方法,備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同,區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看,避免了相同子問(wèn)題的重復(fù)求解。,上海金融學(xué)院信息管理系,25,int LookupChain(int i,int j) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(i,i) + LookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k

17、= i+1; k j; k+) int t = LookupChain(i,k) + LookupChain(k+1,j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; ,上海金融學(xué)院信息管理系,26,#include stdafx.h #include int LookupChain(int p,int i,int j,int m6,int s6); int MMatrixChain(int p,int n,int m6,int s6); void Traceback(int i,int j,int s6); int ma

18、in(int argc, char* argv) int n=6; int m66; int s66; int p7; for (int i=0;ipi; MMatrixChain(p,n,m,s); Traceback(1,6,s); return 0; int MMatrixChain(int p,int n,int m6,int s6) for (int i = 1; i = n; i+) for (int j = i; j = n; j+)mij = 0; return LookupChain(p,1,n,m,s); ,int LookupChain(int p,int i,int j

19、,int m6,int s6 ) if (mij 0) return mij; if (i = j) return 0; int u = LookupChain(p,i,i,m,s) + LookupChain(p,i+1,j,m,s) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(p,i,k,m,s) + LookupChain(p,k+1,j,m,s) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; void Traceback(

20、int i,int j,int s6) if(i=j)return; Traceback(i,sij,s); Traceback(sij+1,j,s); coutMultiply Ai,sij; coutand Asij+1,jendl; ,上海金融學(xué)院信息管理系,27,3.3 最長(zhǎng)公共子序列,若給定序列X=x1,x2,xm,則另一序列Z=z1,z2,zk,是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有:zj=xij。例如,序列Z=B,C,D,B是序列X=A,B,C,B,D,A,B的子序列,相應(yīng)的遞增下標(biāo)序列為2,3,5,7。 給定2個(gè)序列X和Y,當(dāng)另一序

21、列Z既是X的子序列又是Y的子序列時(shí),稱Z是序列X和Y的公共子序列。,j,上海金融學(xué)院信息管理系,28,最長(zhǎng)公共子序列,問(wèn)題:給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn,找出X和Y的最長(zhǎng)公共子序列。 例如:X=A,B,C,B,D,A,B, Y=B,D,C,A,B,A 則序列B,C,A是X和Y的一個(gè)公共子序列。但它不是X和Y的一個(gè)最長(zhǎng)公共子序列。序列B,C,B,A是X和Y的一個(gè)公共子序列,它的長(zhǎng)度是4,而且它是X和Y的一個(gè)最長(zhǎng)公共子序列。因?yàn)?,X和Y沒(méi)有長(zhǎng)度大于4的公共子序列。它的另一個(gè)解是B,C,A,B。該問(wèn)題的答案不唯一。,j,上海金融學(xué)院信息管理系,29,最長(zhǎng)公共子序列的結(jié)構(gòu),設(shè)

22、序列X=x1,x2,xm和Y=y1,y2,yn的最長(zhǎng)公共子序列為Z=z1,z2,zk ,則 (1)若xm=yn,則zk=xm=yn,且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。 (2)若xmyn且zkxm,則Z是xm-1和Y的最長(zhǎng)公共子序列。 (3)若xmyn且zkyn,則Z是X和yn-1的最長(zhǎng)公共子序列。,由此可見(jiàn),2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此,最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,上海金融學(xué)院信息管理系,30,子問(wèn)題的遞歸結(jié)構(gòu),由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用cij記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中

23、, Xi=x1,x2,xi;Yj=y1,y2,yj。當(dāng)i=0或j=0時(shí),空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)Cij=0。其它情況下,由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下:,上海金融學(xué)院信息管理系,31,計(jì)算最優(yōu)值,由于在所考慮的子問(wèn)題空間中,總共有(mn)個(gè)不同的子問(wèn)題,因此,用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。,上海金融學(xué)院信息管理系,32,void LCSLength(int m,int n,char *x,char *y,int *c,int *b) int i,j; for (i = 1; i =cij-1) cij=ci-1j; bij=2; else cij=c

24、ij-1; bij=3; ,上海金融學(xué)院信息管理系,33,構(gòu)造最長(zhǎng)公共子序列 void LCS(int i,int j,char *x,int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1,j-1,x,b); coutxi; else if (bij= 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); ,上海金融學(xué)院信息管理系,34,例如:設(shè)所給的2個(gè)序列為X=A,B,C,B,D,A,B和Y=B,D,C,A,B,A 由算法LCSLength和LCS計(jì)算出的結(jié)果如圖3-3所示。,上海金融學(xué)院信息管理系,35,計(jì)算最優(yōu)

25、值,LCS: 另一個(gè)解B,C,A,B,上海金融學(xué)院信息管理系,36,#include stdafx.h #include void LCSLength(int m,int n,char *x,char *y,int c7,int b7); void LCS(int i,int j,char *x,int b7); int main(int argc, char* argv) int m=7; int n=6; char x8= ,A,B,C,B,D,A,B; char y7= ,B,D,C,A,B,A; /coutx0endly0endl; int c87; int b87; LCSLengt

26、h(m,n,x,y,c,b); cout序列x為:endl; for (int i=1; i= m; i+) coutxi; coutendl; cout序列y為:endl; for (int j=1; j= n; j+) coutyj; coutendl; cout序列x和y的最長(zhǎng)公共子序列為:endl; LCS(7,6,x,b); coutendl; cout矩陣c為:endl; for (int ii = 0; ii = m; ii+) for (int jj = 0; jj = n; jj+) cout.width(2); coutciijj; coutendl; cout矩陣b為:e

27、ndl; for (int iii = 0; iii = m; iii+) for (int jjj = 0; jjj = n; jjj+) cout.width(2); coutbiiijjj; coutendl; return 0; , void LCSLength(int m,int n,char *x,char *y,int c7,int b7) int i,j; for (i = 0; i =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i,int j,char *x,int b7) if (i=0|j=0)

28、 return; if (bij=1) LCS(i-1,j-1,x,b); coutxi; else if (bij=2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); ,上海金融學(xué)院信息管理系,37,算法的改進(jìn),在算法lcsLength和lcs中,可進(jìn)一步將數(shù)組b省去。事實(shí)上,數(shù)組元素cij的值僅由ci-1j-1,ci-1j和cij-1這3個(gè)數(shù)組元素的值所確定。對(duì)于給定的數(shù)組元素cij,可以不借助于數(shù)組b而僅借助于c本身在時(shí)間內(nèi)確定cij的值是由ci-1j-1,ci-1j和cij-1中哪一個(gè)值所確定的。,上海金融學(xué)院信息管理系,38,算法的改進(jìn),如果只需要計(jì)算最長(zhǎng)

29、公共子序列的長(zhǎng)度,則算法的空間需求可大大減少。事實(shí)上,在計(jì)算cij時(shí),只用到數(shù)組c的第i行和第i-1行。因此,用2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。進(jìn)一步的分析還可將空間需求減至O(min(m,n)。,上海金融學(xué)院信息管理系,39,3.4 最大子段和,上海金融學(xué)院信息管理系,40,3.5 凸多邊形最優(yōu)三角剖分,用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形,即P=v0,v1,vn-1表示具有n條邊的凸多邊形。 若vi與vj是多邊形上不相鄰的2個(gè)頂點(diǎn),則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個(gè)多邊形vi,vi+1,vj和vj,vj+1,vi。,上海金融學(xué)院信息管理系,41,多邊形的

30、三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。,上海金融學(xué)院信息管理系,42,三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題,一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹(shù),稱為表達(dá)式的語(yǔ)法樹(shù)。例如,完全加括號(hào)的矩陣連乘積(A1(A2A3)(A4(A5A6)所相應(yīng)的語(yǔ)法樹(shù)如圖 (a)所示。 凸多邊形v0,v1,vn-1的三角剖分也可以用語(yǔ)法樹(shù)表示。例如,圖 (b)中凸多邊形的三角剖分可用圖 (a)所示的語(yǔ)法樹(shù)表示。,上海金融學(xué)院信息管理系,43,三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題,矩陣連乘積中的每個(gè)矩陣Ai對(duì)應(yīng)于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj,ij,對(duì)應(yīng)于矩陣連乘積Ai+1:j

31、。,上海金融學(xué)院信息管理系,44,最優(yōu)子結(jié)構(gòu)性質(zhì),凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。 事實(shí)上,若凸(n+1)邊形P=v0,v1,vn-1的最優(yōu)三角剖分T包含三角形v0vkvn,1kn-1,則T的權(quán)為3個(gè)部分權(quán)的和:三角形v0vkvn的權(quán),子多邊形v0,v1,vk和vk,vk+1,vn的權(quán)之和。可以斷言,由T所確定的這2個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲衯0,v1,vk或vk,vk+1,vn的更小權(quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。,上海金融學(xué)院信息管理系,45,最優(yōu)三角剖分的遞歸結(jié)構(gòu),定義tij,1ijn為凸子多邊形vi-1,vi,vj的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值,即

32、其最優(yōu)值。為方便起見(jiàn),設(shè)退化的多邊形vi-1,vi具有權(quán)值0。據(jù)此定義,要計(jì)算的凸(n+1)邊形P的最優(yōu)權(quán)值為t1n。 tij的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i1時(shí),凸子多邊形至少有3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì),tij的值應(yīng)為tik的值加上tk+1j的值,再加上三角形vi-1vkvj的權(quán)值,其中ikj-1。由于在計(jì)算時(shí)還不知道k的確切位置,而k的所有可能位置只有j-i個(gè),因此可以在這j-i個(gè)位置中選出使tij值達(dá)到最小的位置。由此,tij可遞歸地定義為:,上海金融學(xué)院信息管理系,46,3.6 多邊形游戲,多邊形游戲是一個(gè)單人玩的游戲,開(kāi)始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予

33、一個(gè)整數(shù)值,每條邊被賦予一個(gè)運(yùn)算符“+”或“*”。所有邊依次用整數(shù)從1到n編號(hào)。 游戲第1步,將一條邊刪除。 隨后n-1步按以下方式操作: (1)選擇一條邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2; (2)用一個(gè)新的頂點(diǎn)取代邊E以及由E連接著的2個(gè)頂點(diǎn)V1和V2。將由頂點(diǎn)V1和V2的整數(shù)值通過(guò)邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。 最后,所有邊都被刪除,游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。 問(wèn)題:對(duì)于給定的多邊形,計(jì)算最高得分。,上海金融學(xué)院信息管理系,47,多邊形游戲,例如:四邊形 設(shè)-7為1號(hào)頂點(diǎn),4為2號(hào)頂點(diǎn),2為3號(hào)頂點(diǎn),5為4號(hào)頂點(diǎn)。 按游戲規(guī)則,該四邊形的游戲結(jié)果為:得分最高是33

34、。首次被刪去的邊為1號(hào)邊和2號(hào)邊。,上海金融學(xué)院信息管理系,48,上海金融學(xué)院信息管理系,49,上海金融學(xué)院信息管理系,50,上海金融學(xué)院信息管理系,51,上海金融學(xué)院信息管理系,52,上海金融學(xué)院信息管理系,53,上海金融學(xué)院信息管理系,54,最優(yōu)子結(jié)構(gòu)性質(zhì),在所給多邊形中,從頂點(diǎn)i(1in)開(kāi)始,長(zhǎng)度為j(鏈中有j個(gè)頂點(diǎn))的順時(shí)針鏈p(i,j) 可表示為vi,opi+1,vi+j-1。 如果這條鏈的最后一次合并運(yùn)算在opi+s處發(fā)生(1sj-1),則可在opi+s處將鏈分割為2個(gè)子鏈p(i,s)和p(i+s,j-s)。 設(shè)m1是對(duì)子鏈p(i,s)的任意一種合并方式得到的值,而a和b分別是在

35、所有可能的合并中得到的最小值和最大值。m2是p(i+s,j-s)的任意一種合并方式得到的值,而c和d分別是在所有可能的合并中得到的最小值和最大值。依此定義有am1b,cm2d (1)當(dāng)opi+s=+時(shí),顯然有a+cmb+d (2)當(dāng)opi+s=*時(shí),有minac,ad,bc,bdmmaxac,ad,bc,bd 換句話說(shuō),主鏈的最大值和最小值可由子鏈的最大值和最小值得到。,上海金融學(xué)院信息管理系,55,構(gòu)造遞歸函數(shù),由前面的分析可知,為了求鏈合并的最大值,必須同時(shí)求子鏈合并的最大值和最小值。因此,在整個(gè)計(jì)算過(guò)程中,應(yīng)同時(shí)計(jì)算最大值和最小值。,上海金融學(xué)院信息管理系,56,構(gòu)造遞歸函數(shù),設(shè)mij0

36、 是鏈p(i,j)合并的最小值,而mij1是最大值。若最優(yōu)合并在 opi+s 處將p(i,j)分為2個(gè)長(zhǎng)度小于j的子鏈 p(i,s)和 p(i+s,j-s),且從頂點(diǎn)i開(kāi)始的長(zhǎng)度小于j的子鏈的最大值和最小值均已計(jì)算出。為敘述方便,記 a=mis0,b=mis1, c=i+sj-s0,d=i+sj-s1,上海金融學(xué)院信息管理系,57,構(gòu)造遞歸函數(shù),(1)當(dāng)opi+s=+時(shí), mij0=a+c mij1=b+d (2)當(dāng)opi+s=*時(shí), mij0=minac,ad,bc,bd mij1=maxac,ad,bc,bd 綜合(1)和(2),將 p(i,j)在opi+s出斷開(kāi)的最大值記為maxf(i,

37、j,s),最小值記為minf(i,j,s),則 minf(I,j,s)有兩種可能: opi+s=+時(shí),a+c opi+s=* 時(shí),minac,ad,bc,bd maxf(I,j,s) 有兩種可能: opi+s=+時(shí), b+d opi+s=*時(shí), maxac,ad,bc,bd,上海金融學(xué)院信息管理系,58,構(gòu)造遞歸函數(shù),由于最優(yōu)斷開(kāi)位置s有1n時(shí),頂點(diǎn)i+s實(shí)際編號(hào)為(i+s)mod n。按上述遞推式計(jì)算出的min1即為游戲首次刪去第i條邊后得到的最大得分。,上海金融學(xué)院信息管理系,59,計(jì)算最優(yōu)值及構(gòu)造最優(yōu)解,Void Min_Max (int n, int i,int s,int j,int

38、 ,上海金融學(xué)院信息管理系,60,計(jì)算最優(yōu)值及構(gòu)造最優(yōu)解,Int Poly_Max(int n) int minf,maxf; for(int j=2;jminf) mij0=minf; If(mij1maxf) mij1=maxf; int temp=m1n1; for(int i=1;i=n;i+) if(tempmin1) temp=min1; return temp; ,上海金融學(xué)院信息管理系,61,#include stdafx.h #include void Min_Max(int n, int i,int s,int j,int ,上海金融學(xué)院信息管理系,62,void Min_

39、Max (int n, int i,int s,int j,int ,上海金融學(xué)院信息管理系,63,int Poly_Max(int n,int m52,char op) int i,j,s,minf,maxf,k; for(j=2;jminf) mij0=minf; if(mij1maxf) mij1=maxf; k=s; coutm(i,j,0)=mij0, m(i,j,1)=mij1endl; coutkendl; int temp=m1n1; k=1; for(int ii=2;ii=n;ii+) if(tempmiin1) temp=miin1; k=ii; coutkendl; r

40、eturn temp; ,上海金融學(xué)院信息管理系,64,課后作業(yè),習(xí)題 3-1,3-2,3-3,上海金融學(xué)院信息管理系,65,3.7 圖像壓縮,圖象的變位壓縮存儲(chǔ)格式將所給的象素點(diǎn)序列p1,p2,pn,0pi255分割成m個(gè)連續(xù)段S1,S2,Sm。第i個(gè)象素段Si中(1im),有l(wèi)i個(gè)象素,且該段中每個(gè)象素都只用bi位表示。設(shè) 則第i個(gè)象素段Si為 設(shè) ,則hibi8。因此需要用3位表示bi,如果限制1li255,則需要用8位表示li。因此,第i個(gè)象素段所需的存儲(chǔ)空間為li*bi+11位。按此格式存儲(chǔ)象素序列p1,p2,pn,需要 位的存儲(chǔ)空間。 圖象壓縮問(wèn)題要求確定象素序列p1,p2,pn的

41、最優(yōu)分段,使得依此分段所需的存儲(chǔ)空間最少。每個(gè)分段的長(zhǎng)度不超過(guò)256位。,上海金融學(xué)院信息管理系,66,圖像壓縮,設(shè)li,bi,是p1,p2,pn的最優(yōu)分段。顯而易見(jiàn),l1,b1是p1,pl1的最優(yōu)分段,且li,bi,是pl1+1,pn的最優(yōu)分段。即圖象壓縮問(wèn)題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。 設(shè)si,1in,是象素序列p1,pn的最優(yōu)分段所需的存儲(chǔ)位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知: 其中,算法復(fù)雜度分析: 由于算法compress中對(duì)k的循環(huán)次數(shù)不超這256,故對(duì)每一個(gè)確定的i,可在時(shí)間O(1)內(nèi)完成的計(jì)算。因此整個(gè)算法所需的計(jì)算時(shí)間為O(n)。,上海金融學(xué)院信息管理系,67,3.8 電路布線,在一塊電路板的

42、上、下2端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì),要求用導(dǎo)線(i,(i)將上端接線柱與下端接線柱相連,如圖所示。其中(i)是1,2,n的一個(gè)排列。導(dǎo)線(i,(i)稱為該電路板上的第i條連線。對(duì)于任何1i(j)。 電路布線問(wèn)題要確定將哪些連線安排在第一層上,使得該層上有盡可能多的連線。換句話說(shuō),該問(wèn)題要求確定導(dǎo)線集Nets=(i,(i),1in的最大不相交子集。,上海金融學(xué)院信息管理系,68,記 。N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。 (1)當(dāng)i=1時(shí), (2)當(dāng)i1時(shí), 2.1 j(i)。此時(shí), 。故在這種情況下,N(i,j)=N(i-1,j),從

43、而Size(i,j)=Size(i-1,j)。 2.2 j(i),(i,(i)MNS(i,j) 。 則對(duì)任意(t,(t) MNS(i,j)有ti且(t)(i)。在這種情況下MNS(i,j)-(i,(i)是N(i-1,(i)-1)的最大不相交子集。 2.3 若 ,則對(duì)任意(t,(t) MNS(i,j)有 ti。從而 。因此,Size(i,j)Size(i-1,j)。 另一方面 ,故又有Size(i,j)Size(i-1,j), 從而Size(i,j)=Size(i-1,j)。,電路布線,(1)當(dāng)i=1時(shí) (2)當(dāng)i1時(shí),上海金融學(xué)院信息管理系,69,3.9 流水作業(yè)調(diào)度,n個(gè)作業(yè)1,2,n要在由

44、2臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工,然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi。 流水作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序,使得從第一個(gè)作業(yè)在機(jī)器M1上開(kāi)始加工,到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。,分析: 直觀上,一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒(méi)有空閑時(shí)間,且機(jī)器M2的空閑時(shí)間最少。在一般情況下,機(jī)器M2上會(huì)有機(jī)器空閑和作業(yè)積壓2種情況。 設(shè)全部作業(yè)的集合為N=1,2,n。SN是N的作業(yè)子集。在一般情況下,機(jī)器M1開(kāi)始加工S中作業(yè)時(shí),機(jī)器M2還在加工其它作業(yè),要等時(shí)間t后才可利用。將這種情況下完成S中作業(yè)所需的

45、最短時(shí)間記為T(mén)(S,t)。流水作業(yè)調(diào)度問(wèn)題的最優(yōu)值為T(mén)(N,0)。,上海金融學(xué)院信息管理系,70,流水作業(yè)調(diào)度,設(shè)是所給n個(gè)流水作業(yè)的一個(gè)最優(yōu)調(diào)度,它所需的加工時(shí)間為 a(1)+T。其中T是在機(jī)器M2的等待時(shí)間為b(1)時(shí),安排作業(yè)(2),(n)所需的時(shí)間。 記S=N-(1),則有T=T(S,b(1)。,證明:事實(shí)上,由T的定義知TT(S,b(1)。若TT(S,b(1),設(shè)是作業(yè)集S在機(jī)器M2的等待時(shí)間為b(1)情況下的一個(gè)最優(yōu)調(diào)度。則(1), (2), (n)是N的一個(gè)調(diào)度,且該調(diào)度所需的時(shí)間為a(1)+T(S,b(1)a(1)+T。這與是N的最優(yōu)調(diào)度矛盾。故TT(S,b(1)。從而T=T(

46、S,b(1)。這就證明了流水作業(yè)調(diào)度問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。,由流水作業(yè)調(diào)度問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知,,上海金融學(xué)院信息管理系,71,Johnson不等式,對(duì)遞歸式的深入分析表明,算法可進(jìn)一步得到簡(jiǎn)化。 設(shè)是作業(yè)集S在機(jī)器M2的等待時(shí)間為t時(shí)的任一最優(yōu)調(diào)度。若(1)=i, (2)=j。則由動(dòng)態(tài)規(guī)劃遞歸式可得: T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij) 其中,,如果作業(yè)i和j滿足minbi,ajminbj,ai,則稱作業(yè)i和j滿足Johnson不等式。,上海金融學(xué)院信息管理系,72,流水作業(yè)調(diào)度的Johnson法則,交換作業(yè)i和作業(yè)j的加

47、工順序,得到作業(yè)集S的另一調(diào)度,它所需的加工時(shí)間為T(mén)(S,t)=ai+aj+T(S-i,j,tji) 其中, 當(dāng)作業(yè)i和j滿足Johnson不等式時(shí),有,上海金融學(xué)院信息管理系,73,流水作業(yè)調(diào)度的Johnson法則,由此可見(jiàn)當(dāng)作業(yè)i和作業(yè)j不滿足Johnson不等式時(shí),交換它們的加工順序后,不增加加工時(shí)間。對(duì)于流水作業(yè)調(diào)度問(wèn)題,必存在最優(yōu)調(diào)度 ,使得作業(yè)(i)和(i+1)滿足Johnson不等式。進(jìn)一步還可以證明,調(diào)度滿足Johnson法則當(dāng)且僅當(dāng)對(duì)任意ij有 由此可知,所有滿足Johnson法則的調(diào)度均為最優(yōu)調(diào)度。,上海金融學(xué)院信息管理系,74,算法描述,流水作業(yè)調(diào)度問(wèn)題的Johnson算

48、法 (1)令 (2)將N1中作業(yè)依ai的非減序排序;將N2中作業(yè)依bi的非增序排序; (3)N1中作業(yè)接N2中作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)度。,算法復(fù)雜度分析: 算法的主要計(jì)算時(shí)間花在對(duì)作業(yè)集的排序。因此,在最壞情況下算法所需的計(jì)算時(shí)間為O(nlogn)。所需的空間為O(n)。,上海金融學(xué)院信息管理系,75,3.10 0-1背包問(wèn)題,給定n種物品和一背包。物品i的重量是wi,其價(jià)值為vi,背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品,使得裝入背包中物品的總價(jià)值最大? 0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。,上海金融學(xué)院信息管理系,76,0-1背包問(wèn)題,設(shè)所給0-1背包問(wèn)題的子問(wèn)題,的

49、最優(yōu)值為m(i,j),即m(i,j)是背包容量為j,可選擇物品為i,i+1,n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì),可以建立計(jì)算m(i,j)的遞歸式如下。,算法復(fù)雜度分析: 從m(i,j)的遞歸式容易看出,算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí),算法需要的計(jì)算時(shí)間較多。例如,當(dāng)c2n時(shí),算法需要(n2n)計(jì)算時(shí)間。,上海金融學(xué)院信息管理系,77,算法改進(jìn),由m(i,j)的遞歸式容易證明,在一般情況下,對(duì)每一個(gè)確定的i(1in),函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下,函數(shù)m(i,j)由其全部跳躍點(diǎn)唯一確定。如圖所示。,對(duì)每一個(gè)確定的i(1in),用一個(gè)表pi存儲(chǔ)函數(shù)m(i,j)的全部跳躍點(diǎn)。表pi可依計(jì)算m(i,j)的遞歸式遞歸地由表pi+1計(jì)算,初始時(shí)pn+1=(0,0)。,上海金融學(xué)院信息管理系,78,一個(gè)例子,n=3,c=6,w=4,3,2,v=5,2,1。,上海金融學(xué)院信息管理系,79,函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運(yùn)算得到的。因此,函數(shù)m(i,j)的全部跳躍點(diǎn)包含于函數(shù)m(i+1,j)的跳躍點(diǎn)集pi+1與函數(shù)m(i

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論