算法設(shè)計與分析 動態(tài)規(guī)劃

1、算法設(shè)計與分析第三章 動態(tài)規(guī)劃,楊圣洪,2,3.7 圖像壓縮,將像素點灰度值序列{p1,p2,…,pn}分割成m個連續(xù)段S1, S2 ,… , Sm。 其中0≤pi≤255。0<段內(nèi)點數(shù)<=255Si的點數(shù)記為L[i] ，因L[i]?255，L[i]的2進制之位數(shù)?8Si中各點的pi之2進制使用相同位數(shù)(即最大位數(shù)bmax[i])。pi最大值≤255,故bmax[i]=ceil(log2(max(pi)))?8

2、 3位表示如圖像大塊區(qū)域是淺色則像素值pi <32，bmax[i] ?5段i所占存貯空間L[i]*bmax[i]+點數(shù)(8位)+各點長度(3位)為解壓需要，要保存點數(shù)L[i]、各點像素值的位數(shù)b[i]，共有3+8=11位。故Si的存貯空間為： L[i]*b[i]+11總長(L[1]*bmax[1]+11)+…+(L[m]*bmax[m]+11)=?(L[i]*bmax[i]+11m，i=1~m圖象壓縮問題：確定S1,S

3、2,…,Sm ，使得存儲空間最少。每段b[i]與L[i]如何組合。每段有表示點數(shù)與點長11位,,,,最優(yōu)子結(jié)構(gòu)性質(zhì),設(shè)(L[1],bmax[1])，…, (L[m],b[m])是{p1,p2,…,pn}的最優(yōu)分段。L[i]段i的長度，bmax[i]是段i的各像素值表示位數(shù)如果整體最優(yōu)能導出局部最優(yōu)，否則矛盾(畫示意圖，局部換成最優(yōu)后整體值會縮小,這與整體最優(yōu)矛盾)。為了找出最優(yōu)分段，依次將每個點作為分段點(!!!)，分別計算其區(qū)間

4、長度與存貯空間，然后找出最佳分隔點。設(shè)s[i]是以p[i] 分段點時，該段的存儲位空間值則s[i]=min{s[i-k]+k*bmax(i-k+1, i)}+11 ，1?k?min(i,255) s[i-1]+1*bmax(i-1+1,i)+11, s[i-2]+2*bmax(i-2+1,i)+11,bmax(j,i)=ceil(log2(max{p[k]}+1)) j?k?i ,從點j到點i像素值最大者的位數(shù)，多算幾個s[i

5、]體會計算式i前255點內(nèi)最少存貯空間，以i為結(jié)束點的段最多為255個點或最多包括之前的所有點。算法復雜度分析：由于bmax(s,i)中對k的循環(huán)次數(shù)不超256，故對每一個確定的i，可在時間O(1)內(nèi)完成的計算。因此整個算法所需的計算時間為O(n)。段長不超常量是技巧！,最優(yōu)子結(jié)構(gòu)性質(zhì),設(shè)(L[1],bmax[1])，…, (L[m],b[m])是{p1,p2,…,pn}的最優(yōu)分段。L[i]段i的長度，bmax[i]是段i的各像素值

6、表示位數(shù)如果整體最優(yōu)能導出局部最優(yōu)，否則矛盾(畫示意圖，局部換成最優(yōu)后整體值會縮小,這與整體最優(yōu)矛盾)。設(shè)s[i]是以p[i] 分段點時，該段的存儲位空間值則s[i]=min{s[i-k]+k*bmax(i-k+1, i)}+11 ，1?k?min(i,255) 這個公式是對的，如下公式是錯的！s[i]=min{s[i-k]-11+k*bmax(i-k+1, i)}+11 ，1?k?min(i,255) S[0]=0S[1

7、]=s[0]+1*bmax(1,1)+11=0+8+11=19 呆算8+11S[2]=s[1]+1*bmax(2,2)=27 ,S[0]+2*bmax(1,2)=0+16=16 min(27,16)+11=27 呆算2*8+11=S[3]=S[2]+1*bmax(3,3)=27+8=35,S[1]+2*bmax(2,3)=11+16=27 S[0]+3*bmax(1,3)=0+24=24, m

8、in(35,27,24)+11=35 呆算：3*8+11=35 故這三個結(jié)果是對的,最優(yōu)子結(jié)構(gòu)性質(zhì),設(shè)(L[1],bmax[1])，…, (L[m],b[m])是{p1,p2,…,pn}的最優(yōu)分段。L[i]段i的長度，bmax[i]是段i的各像素值表示位數(shù)如果整體最優(yōu)能導出局部最優(yōu)，否則矛盾(畫示意圖，局部換成最優(yōu)后整體值會縮小,這與整體最優(yōu)矛盾)。設(shè)s[i]是以p[i] 分段點時，該段的存儲位空間值則s[i

9、]=min{s[i-k]+k*bmax(i-k+1, i)}+11 ，1?k?min(i,255) S[0]=0S[1]=s[0]+1*bmax(1,1)+11=0+8+11=19 呆算8+11S[2]=s[1]+1*bmax(2,2)=27 ,S[0]+2*bmax(1,2)=0+16=16 min(27,16)+11=27 呆算2*8+11=S[3]=S[2]+1*bmax(3,3)=27+8=35,S

10、[1]+2*bmax(2,3)=11+16=27 S[0]+3*bmax(1,3)=0+24=24, min(35,27,24)+11=35S[4]=S[4-1]+1*bmax(4,4)=35+7=42,S[4-2]+2*bmax(3,4)=27+16=43 S[4-3]+3*bmax(2,3)=19+24=43, S[4-4]+4*bmax(1,4)=32 min(42,43,32)+11=

11、43,1?k?min(i,255),void compress(int n,int p[],int s[],int l[],int b[],int bmax[]){//點數(shù),像素值,結(jié)點i為終點段存貯空間,段長,本段內(nèi)的素存貯位int Lmax=255,header=11; //L[i]的值占8位，b[i]值占3位s[0]=0;//沒有一個點也要點數(shù)與最大位數(shù)，因此數(shù)組n+1位for (int i=1;is[i-k]+k*b

12、max){s[i]=s[i-k]+k*bmax0;l[i]=k;bmax[i]=bmax0;}} s[i]+=header;//添加固定的長度值 }} //L[i]保存著此點i前多少位共一段,int length(int i){ int k=1;i=(i>>1); //i=i/2; while (i>0){k++; i=(i>>1);} return k;},s

13、[i]=min{s[i-k]+k*bmax(i-k+1, i)}+11bmax(i,j)=ceil(log2(max{p[k]}+1)),1?k?min(i,255),s[i]=min{s[i-k]+k*bmax(i-k+1, i)}+11kmax(i,j)=ceil(log2(max{p[k]}+1)),l[n]最后一段長度，分隔點為n倒數(shù)第1分隔點t2=n-l[n],倒數(shù)第2分隔點t3=t2-l[t2]……,int Tb(

14、int n,int sp[],int l[]){ int i=n; //最后一段結(jié)束位置 m=1; while (i>=1){ sp[m]=i;//段i的結(jié)束位置如500 m++; //逆向記錄其位置 i=i-l[i]; } //前段結(jié)束位置如500-11 return m-1;}//返回段數(shù)void Output(int l[],int b

15、[],int n){int sp[]=new int[n+1]; int m=Tb(n,sp,l); //計算各段結(jié)束點for (int j=m;j>=1;j--){cout<<l[sp[j]]<<' '<<bmax[sp[j]]<<' '<<s[sp[j]]<<endl; }},3.7 圖像壓縮,遞歸計算最優(yōu)值與構(gòu)造

16、最優(yōu)解,遞歸計算最優(yōu)值算法描述：P70-71構(gòu)造最優(yōu)解算法描述：P71-72Compress：S(n)=O(n)，T(n)=O(n),3.8 電路布線,如下圖所示，上方的點僅與下方一點相連點i的對應點記為?(i)，其連線記為(i, ?(i)),稱為第i條連線制板時將線分布到若干絕緣層上，同層上的連線不許相交，為節(jié)約成本要使層次減少，每層不相交的連線增多為此要求出某個電路不相交連線的最大值？，即求導線集Nets={(i, ?(

17、i)),1?i?n}的最大不相交子集。相交判斷：任何1?i?(j)。,∏=｛8，7，4，2，5，1，9，3，10，6｝,此圖板書,各點的對象,最優(yōu)子結(jié)構(gòu)性質(zhì),記N(i,j)={(t, ?(t))|(t, ?(t))∈Nets,t≤i, ?(t)≤j}起點≤i,終點≤j.N(1,1)= {起≤1,終≤1} ={}=N(1,2)…=N(1,7)=MNS(1,1) N(1,8)= {起≤1,終≤8} ={(1,8)}N(2,1)= {

18、起≤2,終≤1} ={}=N(2,2)=N(2,3)…=N(2,6)N(2,7)={起≤2,終≤7}={(2,7)}N(2,8)={起≤2,終≤8}={(1,8),(2,7)} 相交N(3,9)={起≤3,終≤9}={(1,8),(2,7),(3,4)} 相交N(7,9)={起≤7,終≤9}={(1,8),(2,7),(3,4),(4,2),(5,5),(6,1),(7,8)}不相交={(3,4),(5,5),(7,8)}，是

19、最大嗎？ nextN(i,j)的最大不相交子集記為MNS(i,j)，Size(i,j)=|MNS(i,j)|。(1)當i=1時，(2)當i>1時，板N(i,j),MNS(i,j),Size(i,j),MNS(1,j),MNS(i>1,j),12,最優(yōu)子結(jié)構(gòu)性質(zhì),(2)當i>1時， a) 終點j?(i)則(i, ?(i))與(t, ?(t))相交故矛盾) ? MNS(i,j)-{(i, ?(i)

20、)}=N(i-1, ?(i)-1)最大不相交子集MNS(i-1, ?(i)-1) ? Size(i,j)-1=Size(i-1,j-1) ( 假設(shè)MNS(i,j)-{(i, ?(i))}?MNS(i-1, ?(i)-1) ?MNS(i,j)?MNS(i-1, ?(i)-1)?{(i, ?(i))}, 而MNS(i-1, ?(i)-1)?{(i, ?(i))}是不相交子集,故MNS(i,j)不是最大，

21、矛盾，故假設(shè)錯。)② (i, ?(i))?MNS(i,j)即新邊不在最大不相交子集中： ??(t, ?(t))?MNS(i,j)，其起點t<i?MNS(i,j)?N(i-1,j) ? MNS(i,j)?MNS(i-1,j) ?Size(i,j)≤Size(i-1,j)。 又MNS(i-1,j)?MNS(i,j)?Size(i-1,j)?Size(i,j)?Size(i,j)=Size(i-1,j)。電路

22、布線問題整體最優(yōu)Size(i,j)導出局部最優(yōu) Size(i-1,j-1),N(i,j)={(t, ?(t))|(t, ?(t))∈Nets,t≤i, ?(t)≤j} 起點≤i,終點≤j.,,,,,,,,13,遞歸計算最優(yōu)值,8,板書,∏=｛8，7，4，2，5，1，9，3，10，6｝,Size[1,1]=…=size[1,7]=0,size[1,8]=size[1,9]=1size[2,1]=size[1,1],…,size[2,

23、6]=size[1,6]size[2,7]=max(size[1,7],size[1,6]+1)=1,…size[3,1]=size[2,1],…size[3,3]=size[2,3]size[3,4]=max(size[2,4],size[2,3]+1)=1size[4,1]=size[3,1],size[4,2]=max(size[3,2],size[3,1]+1)=1size[5,1]=size[5,2]=size[5

24、,3]=size[5,4]=上行值size[5,5]=max(size[4,5],size[4,4]+1)……,,,行i的終點,遞歸計算最優(yōu)值,,void MNS(int C[], int n, int **size) //數(shù)組元素n+1{ //每個i的連接邊?(i)用數(shù)組C表示,如{8,7,4,2,5,1,9,3,10,6} ,size要返回! for (int j=1; j=?(1)即結(jié)點1的終點 for (i

25、nt i=2; i= ?(i) size[i][j]=max(size[i-1][j], size[i-1][C[i]-1]+1); }//起i終i范圍為最后點n,j>= ?(n) size[n][n]==max(size[n-1][n], size[n-1][C[n]-1]+1);},板書,15,遞歸計算最優(yōu)值,,板書,∏=｛8，7，4，2，5，1，9，3，10，6｝,i=2 j=C[3]-1=3 size

26、[2][3]=size[1][3] i=3 j=4 size[3][4]size[2][4] net[3]=(3,C[3])i=4 j=C[5]-1=4 size[4][4]=size[3][4] 不變i=5 j=8 size[5][8]size[4][8] net[2]=(5,C[5])i=6 j=C[7]-1=8 size[6][8]=size[5][8] j不變 i=7 j=9 size[7][9]size[6][9]

27、net[1]=(7,C[7])i=8 j=C[9]-1=9 size[8][9]=size[7][9] j不變i=9 j=10 size[i][j]size[i-1][j] net[0]=(9,C[9])i=n=10 j=n=10 size[i][j]=size[i-1][j] j不變,,,,,,,,,,,,當size[i,j]size[i-1,j]才加邊,跟蹤路徑,,void Traceback(int C[],int **

28、size, int n, int **Net, int &m){ int j=n; m=0; for (int i=n; i>1; i--) { if (size[i][j]!=size[i-1][j]){ Net[m][0]=i; Net[m][1]=C[i]; m++; j=C[i]-1;

29、 } } if (j>=C[1]) { Net[m][0]=1; Net[m][1]=C[i]; m++ }},(i, ?(i))?MNS(i,j)時 Size(i,j)=Size(i-1,j-1)+1 若size[i][j]=size[i-1][j-1]+1即size[i][j]!=size[i-1][j]就往MNS中加邊(i, ?(i)).

30、保存該邊起始號i,終止號?(i)即C[i].,遞歸計算最優(yōu)值,算法復雜性：MNS算法：T(n)=O(n2)，S(n)=(n2)Traceback算法：T(n)=O(n),void MNS(int C[], int n, int **size) //數(shù)組元素n+1{ //每個i的連接邊?(i)用數(shù)組C表示,如{8,7,4,2,5,1,9,3,10,6} ,size要返回! for (int j=1; j=?(1) fo

31、r (int i=2; i= ?(i) size[i][j]=max(size[i-1][j], size[i-1][C[i]-1]+1); }//起i終i范圍為最后點n,j>= ?(n) size[n][n]==max(size[n-1][n], size[n-1][C[n]-1]+1);},void Traceback(int C[],int **size, int n, int **Net, int

32、&m){ int j=C[n]; m=0; for (int i=n; i>1; i--) { if (size[i][j]!=size[i-1][j]){ Net[m][0]=i; Net[m][1]=C[i]; m++; j=C[i]-1; } } if (j>=C[1]) { Net[m][0]=1; Ne