算法電路布線課件

1、算法電路布線動態(tài)規(guī)劃電路布線算法電路布線動態(tài)規(guī)劃算法整體思想 將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。 子問題之間不是相互獨立的 保存已解決的子問題的答案，在需要時再找出已求得的答案，這樣可以避免大量的重復(fù)計算算法電路布線 用一個表格記錄所有已解決的子問題的答案 分解若干子問題 nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法電路布線子問題不相互獨立，被計算很多次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

2、/2T(n/4)T(n/4)T(n/4)T(n/4)算法電路布線保存已解決問題答案，需要時取出，避免重復(fù)計算 子問題之間不相互獨立 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)算法電路布線 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計算出最優(yōu)值。 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。算法電路布線 全是理論？算法電路布線問題描述： 在一塊電路板的上、下兩端分別有n個接線柱。根據(jù)電路設(shè)計，要求用導(dǎo)線(i,(i) 將上端接線柱i與下端接線柱(i)

3、相連，如下圖。其中，(i),1 i n,是1,2,n的一個排列。導(dǎo)線(I, (i)稱為該電路板上的第i條連線。對于任何1 i j n,第i條連線和第j條連線相交的充要條件是(i) (j). （i）=8，7，4，2，5，1，9，3，10，6算法電路布線 在制作電路板時，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets = i，(i)，1 i n的最大不相交子集。算法電路布線1. 最優(yōu)子結(jié)構(gòu)性質(zhì) 記N(i,j) = t|(t, (t) Nets,t i, (t) j . N(i

4、,j)的最大不相交子集為MNS（i,j）Size(i,j)=|MNS(i,j)|。 （1） 當(dāng)i = 1時 （2） 當(dāng)i 1時， j (i)。此時，(i,(i) 不屬于N(i,j)。故在這種情況下，N(i,j) = N(i-1,j)，從而Size(i,j)=Size(i-1,j).) 1 ()1 (, 1() 1 (), 1 (), 1 (jjjNjMNS算法電路布線 j (i)。此時，若(i, (i)MNS(i,j)，則對任意(t, (t)MNS(i,j)有t i且(t) (i)；否則，(t, (t)與(i, (i)相交。在這種情況下MNS(i,j)-(i, (i)是N(i-1, (i)-1

5、)的最大不相交子集。否則，子集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 =1 2 i-1 i(i) =1 2 i-1 i j-2 j-1 j 算法電路布線若(i, (i)不屬于MNS(i,j)，則對任意(t, (t)MNS(i,j)，有t1時) 1 (1) 1 (0), 1 (jjjSize)()(1) 1)(, 1(), 1(max), 1(),(ijijiiSizejiSizejiSi

6、zejiSize 狀態(tài)轉(zhuǎn)移順序狀態(tài)轉(zhuǎn)移順序： 自底向上，先算上排接線柱只有1個，2個的最優(yōu)布線，然后求上排接線柱有多個的最優(yōu)布線。算法電路布線3. 根據(jù)上面遞歸式可以得到二維表：紅色標(biāo)明的就是算法選擇的路徑，向上優(yōu)先。在斜角值改變時可以取得所求的子集。即 9 10,79,55,34 算法電路布線 設(shè)計動態(tài)規(guī)劃算法如下。其中sizeij表示函數(shù)Size（i，j）的值。void MNS(C, n, *size) for (j=0; jC1; j+) size1j=0; for (j=C1; j=n; j+) size1j=0; for (i=2; in; i+) for (j=0; jCi; j+) sizeij=sizei-1j;/jj(i)的情況的情況 for (j=Cj; j1; i-) if (sizeij!=sizei-1j/ 此時此時(i,c(i