交叉分布問題

11.5.3交叉分布在交叉分布問題中.從一個布線通道開始.通道的頂部和底部各有片個甘腳.圖11?32給出了,Q10的情況.布線區(qū)城足圖中帶陰影的氏方形區(qū)域，針腳的洋號從】到m在通逋的頂部和底部從左至右分布.另外.有⑴2,3■….川的一個排列C.必歩用一根電線將頂部前針伽與底部的針I(yè)WC,連接起來?在圖11?32的例戶札C=〔8.7,425丄93.10.6h需要連接的”根線被編號為1到比第i根找連接頂部的，和底部的C,?當比僅當ivj時，連線i在連純的左邊。23456789 10C=[&7.4.2,5,1.9?23456789 10C=[&7.4.2,5,1.9?3.10.6)圖11?32布線舉例圖11?32顯示了任布線區(qū)域中無淪線路9和10如何設(shè)買?它們…定會在某一點相交?我們不希望交叉的岀現(xiàn).以免出現(xiàn)短路，為此對以在交叉點放置絕緣物或?qū)蓷l線路布設(shè)在不同層?閔也.必須尋找熾小的交叉點數(shù)【1?？梢则炞C?十線路是按圖1卜32中的直線布設(shè)時?交叉慮的數(shù)fit是故少的.毎個交又點用（ij）表示.i和/是通過該交叉點的兩條線路?識別所有交叉點的一種方法是檢査線路的征一個（/＞；）并且檢驗其中炳條託線是否相交。為避免對同一交叉點檢驗兩次?可以要求ivj（即交叉點（10.9）與（9、10）是一樣的）。設(shè)/是（Lj）的數(shù)雖.iv幾在圖11?32的例f?中，人"札=0.在圖11?33中，列出了圖11?32中所有的交叉及&的值。該表的第i行首先給出了《的值，然后給出力的值‘7其中i與丿是相交的，相交的總數(shù)K由所桃的和確定。在本例中K=22.由干匕只記錄了線路i與其右邊線路（即Y力相交的數(shù)矢因此〈給事二礫分數(shù)躱煒構(gòu)出的是線路，右側(cè)相交的數(shù)雖。為了降低菱雜性，要求在通道的毎一半?yún)^(qū)域中都含有犬約相冋的交叉點（一部分含以/2」個交叉點，另一部分含rk/2］個交叉點）.圖11?34給出了圖11?32中的另一種布線方法，在這種方法中.在通道的上、下部分各有1】個交義點.匕半部分的連接由排列E1.463J29.5.10.8］給出，即頂部的針腳i與中間的針旳。相連.下半部分的連按由排列〃二［8.1.2.7.3.4.569?⑹給出.中間的針腳i與底部的針腳Q相連.可以看出C,=By1?＜札要完成C給出的連接.這個等式是必不可少的。通過檢査QJ）,在8（d）的時間內(nèi)可以計算出相交數(shù)肚匕及總的相交數(shù)fitK。町采用程序11“0中的線性表從C計算出A和乩1 23456789 10fflll-34分制交叉程^11-10使用線性表的交叉分布程序LinearList<int>L(n);intr=K/2：//匕半部分為耍的交義數(shù)"從右至左知描線路intw^n;〃w是當前線幽while(r){//上半部分省耍里各的交％if(Mw)vr){//ftf用w的所何交義L.lnsert(k(w),w);r-?k[w];}else{//僅便用w血個交義L.lnsert(r.w)：r=0;}w??;}"在屮線匕《?定線路非列//詢*條線的排列次序不變for(iftti=1;i<=w：U+)X(i]=i；第〃索找倉樹361n代余線路的徘刊次序來nlfor(i=w+1;i<?n;i??)L.Delete(1,X(i]);〃什覧上半部分的怡列for(i?1;i<?n;i++)A(x(iHJ；//imI；半部分的排列for(i=1：I<=n;i++)B|i]=C(X仙;在while循環(huán)中，從右至左掃描這些線路，確定它們在布線通道中央的相關(guān)次序.目標是在通道中部產(chǎn)生一個布線次序，使得在布線通道上半部分的中間正好有uk?2個交叉。線性表L用于記錄通道中部當前所得到的次序。當考察線路w時，把w右側(cè)與w相交的線路中的最多k[w)個交叉分配到上半部分.第一個交點足與L中的第?條線路相交產(chǎn)生的.第二個交點是與L中第二條線路相交產(chǎn)生的，如此往貨。如果將與w相交的條線路中的c條分配到上半部分，那么這條線路必定與L中的詢c條線路相交。另外從w到n的次序也可以通過將w插入到L中的第C條線之后而得到.當在程序11J0的while循環(huán)中考察線路w時.線路wX至n已經(jīng)在L中。而IL由Tk[w)不會趙過線路w右邊的線路數(shù).因此在考察w時.L中至少已有k[w)條線路。當在程序1】"0中的while循環(huán)中考察線路W時，除非上半部分所潘要的相交數(shù)r比k[w|小，否則將所竹右邊相交點都分配到上半部分。當while循環(huán)終止時，布線通道中間的線路次序就建立好了.線路1到w在匕半部分沒有相交，因此在這半部分中不必改變它們的相對次序.因而，X(l:w]=[1.2，.…w],余下的線路排序由線性表L給出.程序11-10中的前炳個for循環(huán)構(gòu)造了X.F面抿據(jù)圖丨1?32的例了?來構(gòu)造X.先將線路10添加到L中，得L=(10).沒有產(chǎn)生交叉.所以接F來把線路9濟加到L中，得L=(10.9).這時在上半部分產(chǎn)生了1個相交.之后將8加入到射&個元索后邊，得L=(&】0,9)?此時上半部分的右邊相交總數(shù)仍然是1。下面將7加入到L的第二個元素Z后，上半部分有2個相交，1■變?yōu)?8,10.7.9),所爲的相交次數(shù)r降到了8。當6加人后、得到L=(6,&10,7,9),r=8.將線路5加入后又產(chǎn)生了2個相交,L=(6,8.5,10,7.9),r=6?當4披加詢L的第一個元素之后時，產(chǎn)生了一個相交，得到L=(6.4.&5,10,7,9),r=5。下面將3加人.得到L=(6.4.&3.5.10,7,9),r=2e敏后，月察2時，我們發(fā)現(xiàn)，雖然它能產(chǎn)生/=6個相交，但只能將我中2個分配到通道的上半部分，因此它披插人到L第二個元素的后邊，得到L=(6.4,2,8.3.5,10,7.9).剩下的線路保持它們的相對次序.現(xiàn)在完成了上半部分的布線，然后計算線路的排列，通過在序列(1,2，…,w)上附加L得到X=[1.6.4,2,8,3,5,10.7,9].排列A與X關(guān)系密切.A[j誡明線路j應(yīng)該連接到中間的哪個針腳匕而X[j]表明哪…條線路連接到中間的針腳j上。程序1M0中的第三個for循環(huán)就是用這種信息來計算A的。任第四個fa循環(huán)中，利用X和C計算出B.由于將元索插入到大小為$的線性表中需要的時間是5$人所以程序H-10中的while循環(huán)浦占用0(n')時間,第二個for循環(huán)也需要這么多時間,其他代碼需要8(n)時間.因此程序1110的全部代碼復(fù)雜性是(Xn:).將程序11-10需要的時間與計算K和k[i]所需娶的時間聯(lián)系在一超，可知在使用線性表解決交叉分布問題吋.所希要的全部時間是0($).通i±伎用平衡的捜索樹來代粹線性表，叮以把解決方秦的疑雜性降低到O(nlogn).為了得到平均復(fù)雜性5nlogn),可以使用帶索引的二叉慢索樹，而不使用帶索引的平衡搜索樹.這兩種悄況任技術(shù)上是相同的，卜?面將用帶索引的二叉搜索樹來闡述此技術(shù)。首先,來看-下如何計算相交數(shù)％ 假設(shè)檢査的線路次序是幾“?1，….1并且檢査線路j時，將G插人到帶索引的搜索掛中.對T圖11-32中的例子，首先從空樹開始.槍査線路10并將C/6播人到空樹中，得到圖11-35a所示的樹?節(jié)點外測的數(shù)宇是其LeftSize的值，野點內(nèi)部是其關(guān)鍵值(或C的値)"注意到七總是為零，因此設(shè)￡=0。然后檢査線路9并將C/10插入到樹中，得到圖H-35b所示的樹，為了實現(xiàn)這次桶人，越過了根節(jié)點(其LeftSize=l).根據(jù)這個LeftSize值，町知線路9的底部節(jié)點正好在目前所看到的一條線路的右邊，因此&=1?下面松査線路8,將C嚴3貢入到樹中，得到ffiU-35c所示的樹.由于C,是樹中眾小的入口、因此沒有線路相交廿,=0.對于線路7,C產(chǎn)9被插入后得到圖ll-35d中的秋C,成為樹中的第三個最小入口.通過對進入其右子樹的各節(jié)點的LeftSize值連續(xù)求和，可以確定C：是第三個最小入口.C,被插入時.這個和足2,因此，新無素是當前第三個最小的.由此町以得出結(jié)論.它的底邯節(jié)點位于樹中其他2個節(jié)點的右邊，因此，kt=2.按此方法逬行下去，當檢査線路6至2時，產(chǎn)

Ittll-3S計算交叉的數(shù)就第II章搜索樹363生了圖H-35e至圖ll?35i的樹。最后，松査線路1時.將C>8插入到樹中.作為關(guān)鍵值為7的節(jié)點的右孩尹。進入其右子樹的各市點的LeftSize值之和是6+1=7,線路1的底部節(jié)點位于樹中7條線路的右邊，因此&嚴7。檢査線路i和汁算匕需耍的時間是OG),其中力是當前帶索引的拽索樹的髙度。因此.用帶索引的二叉搜索樹可在0(nlogn)^均時間內(nèi)或用芍索引的平衡搜索樹在O(nlog/i)平均時間內(nèi)計算出所有的《°為計卑4?可以用一個経改的帶索引的捜索樹來實現(xiàn)程序11?10的代碼。在這種修改中■元索沒有關(guān)鍵值，每個元素只有一個位涅或階。InsertGe)用來插入元索e使得e成為階為i+1的元素。為了按階的次序排列元索.可以進行一次中序遍歷。執(zhí)行程序11?10所需要的時間為O(ztlogn)^得到排列A的另一種方法是首先計算12和2最小的幾便得tk(<r9于上面的例子^>=11和*3.程.rii-io實現(xiàn)了線路兒mi：1…，$的所有相交，其半部分包含線路卜1的r-tk(個相交，下半部分包含余卜?的相交.為了得到上半部分的相交點.對SAC后的掛進行檢査。在本例中，檢査圖ll?35h中的樹。對樹刀的中洋遍歷可產(chǎn)生序列(1.2.3,4.5.9,10),用相應(yīng)的線路編號來替換這些底部為點.可得到序列(6.4,835」079),它給出了按圖11?35h中所描述的9人相交線路所得到的排列。對干另外2個相交，將線路