算法-電路布線課件

動(dòng)態(tài)規(guī)劃電路布線動(dòng)態(tài)規(guī)劃電路布線1動(dòng)態(tài)規(guī)劃算法整體思想將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。子問(wèn)題之間不是相互獨(dú)立的保存已解決的子問(wèn)題的答案，在需要時(shí)再找出已求得的答案，這樣可以避免大量的重復(fù)計(jì)算動(dòng)態(tài)規(guī)劃算法整體思想將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子2用一個(gè)表格記錄所有已解決的子問(wèn)題的答案

分解若干子問(wèn)題

nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=3子問(wèn)題不相互獨(dú)立，被計(jì)算很多次nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)子問(wèn)題不相互獨(dú)立，被計(jì)算很多次nT(n)=n/2T(n/4)4保存已解決問(wèn)題答案，需要時(shí)取出，避免重復(fù)計(jì)算

子問(wèn)題之間不相互獨(dú)立

n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)保存已解決問(wèn)題答案，需要時(shí)取出，避免重復(fù)計(jì)算n=n/2T(n5找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。6全是理論？全是理論？7問(wèn)題描述：

在一塊電路板的上、下兩端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,π(i))將上端接線柱i與下端接線柱π(i)相連，如下圖。其中，π(i),1≤i≤n,是｛1,2,…,n｝的一個(gè)排列。導(dǎo)線(I,π(i))稱為該電路板上的第i條連線。對(duì)于任何1≤i≤j≤n,第i條連線和第j條連線相交的充要條件是π(i)>π(j).

π（i）=｛8，7，4，2，5，1，9，3，10，6｝問(wèn)題描述：8在制作電路板時(shí)，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。電路布線問(wèn)題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說(shuō)，該問(wèn)題要求確定導(dǎo)線集Nets=｛i，π(i)，1≤i≤n｝的最大不相交子集。在制作電路板時(shí)，要求將這n條連線分布到若干絕緣層上。在91.最優(yōu)子結(jié)構(gòu)性質(zhì)

記N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}.N(i,j)的最大不相交子集為MNS（i,j）Size(i,j)=|MNS(i,j)|。（1）當(dāng)i=1時(shí)（2）當(dāng)i>1時(shí)，①j<π(i)。此時(shí)，(i,π(i))不屬于N(i,j)。故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j).1.最優(yōu)子結(jié)構(gòu)性質(zhì)10

②j≥π(i)。此時(shí)，若(i,π(i))∈MNS(i,j)，則對(duì)任意(t,π(t))∈MNS(i,j)有t<i且π(t)<π(i)；否則，(t,π(t))與(i,π(i))相交。在這種情況下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。否則，子集MNS(i-1,π(i)-1)∪{(i,π(i))}包含于N(i,j)是比MNS(i,j)更大的N(i,j)的不相交子集。這與MNS(i,j)的定義相矛盾。

1：(i,π(i))∈MNS(i,j)，有Size(i,j)=Size(i-1,π(i)-1)+1i=｛12…i-1i｝π(i)=｛12…i-1ij-2j-1j｝②j≥π(i)。此時(shí)，若(i,π(i))∈MNS11若(i,π(i))不屬于MNS(i,j)，則對(duì)任意(t,π(t))∈MNS(i,j)，有t<i。從而MNS(i,j)包含于N(i-1,j)，因此，Size(i,j)≤Size(i-1,j).

另一方面，MNS(i-1,j)包含于N(i,j),故又有Size(i,j)≥Size(i-1,j)，從而Size（i,j）=Size(i-1,j).

2：(i,π(i))不屬于MNS(i,j)，有Size(i,j)=Size(i-1,j)i=｛12…i-1i｝π(i)=｛12…i-1ij-1j｝若(i,π(i))不屬于MNS(i,j)，則對(duì)任意(t,122.遞歸計(jì)算最優(yōu)值電路布線問(wèn)題的最優(yōu)值為Size(n,n)。由該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，子問(wèn)題最優(yōu)值的遞歸關(guān)系如下：

(1)當(dāng)i=1時(shí)(2)當(dāng)i>1時(shí)

狀態(tài)轉(zhuǎn)移順序：自底向上，先算上排接線柱只有1個(gè)，2個(gè)的最優(yōu)布線，然后求上排接線柱有多個(gè)的最優(yōu)布線。關(guān)鍵一步，寫出遞歸表達(dá)式2.遞歸計(jì)算最優(yōu)值(1)當(dāng)i=1時(shí)狀態(tài)轉(zhuǎn)移順133.根據(jù)上面遞歸式可以得到二維表：

紅色標(biāo)明的就是算法選擇的路徑，向上優(yōu)先。在斜角值改變時(shí)可以取得所求的子集。即9→10,7→9,5→5,3→43.根據(jù)上面遞歸式可以得到二維表：

紅色標(biāo)明的14設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法如下。其中size[i][j]表示函數(shù)Size（i，j）的值。voidMNS(C[],n,**size){

for(j=0;j<C[1];j++)size[1][j]=0;for(j=C[1];j<=n;j++)size[1][j]=0;for(i=2;i<n;i++){for(j=0;j<C[i];j++)size[i][j]=size[i-1][j];//j<π(i)的情況for(j=C[j];j<=n;j++)//j〉=π(i)的情況

size[i][j]=max{size[i-1][j],size[i-1][C[i]-1]+1};}size[n][n]==max{size[n-1][n],size[n-1][C[n]-1]+1};}算法——電路布線課件154.構(gòu)造最優(yōu)解voidTraceback(C[],**size,n,Net[],m){intj=n;m=0;for(inti=n;i>1;i--)if(size[i][j]!=size[i-1][j]//此時(shí)(i,c(i))是最大不相交子集中的一條邊{Net[m++]=i;j=C[i]-1;//更新擴(kuò)展連線柱區(qū)間}if(j>=C[1])//處理i=1的情形Net[m++]=1;}4.構(gòu)造最優(yōu)解voidTraceback(C[],**s16動(dòng)態(tài)規(guī)劃電路布線動(dòng)態(tài)規(guī)劃電路布線17動(dòng)態(tài)規(guī)劃算法整體思想將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。子問(wèn)題之間不是相互獨(dú)立的保存已解決的子問(wèn)題的答案，在需要時(shí)再找出已求得的答案，這樣可以避免大量的重復(fù)計(jì)算動(dòng)態(tài)規(guī)劃算法整體思想將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子18用一個(gè)表格記錄所有已解決的子問(wèn)題的答案

分解若干子問(wèn)題

nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=19子問(wèn)題不相互獨(dú)立，被計(jì)算很多次nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)子問(wèn)題不相互獨(dú)立，被計(jì)算很多次nT(n)=n/2T(n/4)20保存已解決問(wèn)題答案，需要時(shí)取出，避免重復(fù)計(jì)算

子問(wèn)題之間不相互獨(dú)立

n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)保存已解決問(wèn)題答案，需要時(shí)取出，避免重復(fù)計(jì)算n=n/2T(n21找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。22全是理論？全是理論？23問(wèn)題描述：

在一塊電路板的上、下兩端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,π(i))將上端接線柱i與下端接線柱π(i)相連，如下圖。其中，π(i),1≤i≤n,是｛1,2,…,n｝的一個(gè)排列。導(dǎo)線(I,π(i))稱為該電路板上的第i條連線。對(duì)于任何1≤i≤j≤n,第i條連線和第j條連線相交的充要條件是π(i)>π(j).

π（i）=｛8，7，4，2，5，1，9，3，10，6｝問(wèn)題描述：24在制作電路板時(shí)，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。電路布線問(wèn)題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說(shuō)，該問(wèn)題要求確定導(dǎo)線集Nets=｛i，π(i)，1≤i≤n｝的最大不相交子集。在制作電路板時(shí)，要求將這n條連線分布到若干絕緣層上。在251.最優(yōu)子結(jié)構(gòu)性質(zhì)

記N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}.N(i,j)的最大不相交子集為MNS（i,j）Size(i,j)=|MNS(i,j)|。（1）當(dāng)i=1時(shí)（2）當(dāng)i>1時(shí)，①j<π(i)。此時(shí)，(i,π(i))不屬于N(i,j)。故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j).1.最優(yōu)子結(jié)構(gòu)性質(zhì)26

②j≥π(i)。此時(shí)，若(i,π(i))∈MNS(i,j)，則對(duì)任意(t,π(t))∈MNS(i,j)有t<i且π(t)<π(i)；否則，(t,π(t))與(i,π(i))相交。在這種情況下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。否則，子集MNS(i-1,π(i)-1)∪{(i,π(i))}包含于N(i,j)是比MNS(i,j)更大的N(i,j)的不相交子集。這與MNS(i,j)的定義相矛盾。

1：(i,π(i))∈MNS(i,j)，有Size(i,j)=Size(i-1,π(i)-1)+1i=｛12…i-1i｝π(i)=｛12…i-1ij-2j-1j｝②j≥π(i)。此時(shí)，若(i,π(i))∈MNS27若(i,π(i))不屬于MNS(i,j)，則對(duì)任意(t,π(t))∈MNS(i,j)，有t<i。從而MNS(i,j)包含于N(i-1,j)，因此，Size(i,j)≤Size(i-1,j).

另一方面，MNS(i-1,j)包含于N(i,j),故又有Size(i,j)≥Size(i-1,j)，從而Size（i,j）=Size(i-1,j).

2：(i,π(i))不屬于MNS(i,j)，有Size(i,j)=Size(i-1,j)i=｛12…i-1i｝π(i)=｛12…i-1ij-1j｝若(i,π(i))不屬于MNS(i,j)，則對(duì)任意(t,282.遞歸計(jì)算最優(yōu)值電路布線問(wèn)題的最優(yōu)值為Size(n,n)。由該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，子問(wèn)題最優(yōu)值的遞歸關(guān)系如下：

(1)當(dāng)i=1時(shí)(2)當(dāng)i>1時(shí)

狀態(tài)轉(zhuǎn)移順序：自底向上，先算上排接線柱只有1個(gè)，2個(gè)的最優(yōu)布線，然后求上排接線柱有多個(gè)的最優(yōu)布線。關(guān)鍵一步，寫出遞歸表達(dá)式2.遞歸計(jì)算最優(yōu)值(1)當(dāng)i=1時(shí)狀態(tài)轉(zhuǎn)移順293.根據(jù)上面遞歸式可以得到二維表：

紅色標(biāo)明的就是算法選擇的路徑，向上優(yōu)先。在斜角值改變時(shí)可以取得所求的子集。即9→10,7→9,5→5,3→43.根據(jù)上面遞歸式可以得到二維表：

紅色標(biāo)明的30設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法如下。其中size[i][j]表示函數(shù)Size（i，j）的值。void