二維矩形howl-hapx問題的研究

1維矩形環(huán)境問題二維矩形壓縮問題是指在二維歐空間中，已知的大矩形框架為w，高為h，寬為s，高分別為s1、b1、w2、b2。。。wn和hn的小矩形塊（不具有普遍性，可以認為所有已知數(shù)量均為正整數(shù)）需要盡可能多地插入矩陣框架，使框架的面積利用率最大化。放入塊須完全在框內(nèi),邊與框的邊平行且任意兩塊間無嵌入。二維矩形Packing問題是關于空間利用的典型的NP難度問題,簡記此問題為P。目前問題P代表性的求解方法為啟發(fā)式算法,包括通用的遺傳法、禁忌法、模擬退火及根據(jù)問題特點設計的穴度法。本文擬給出一個復雜度僅與待放塊個數(shù)相關的完備算法。2傳統(tǒng)的完整算法用于解決二維矩形壓縮問題本節(jié)擬先給出一種基于枚舉法的完備算法以及相關的證明。2.1格格局局+左下平行算法在各塊合法放置的前提下,稱X={(xi1,xi2),(xi2,yi2),…,(xik,yik)}為一個格局,其中{i1,i2,…,ik}是{1,…,n}的子集且(xik,yik)為塊k的左下角坐標。例如,若框大小為7×4,有6個待放塊,大小分別為1×1,1×1,1×2,1×3,2×1,4×1,其放置方法如圖1所示,則對應的格局X={(0,1),(4,2),(2,1),(6,0),(4,1),(2,3)}。圖圖11格格局局XX左下平移算法A0:設格局X={(xi1,xi2),(xi2,yi2),…,(xik,yik)}為一合法格局。1.從X出發(fā)做水平左移動作(1)所有塊按照(x,y)的字典序從小到大排序;(2)按序將當前矩形塊水平左移,直至其左邊與某塊或框的左壁相貼(即交的邊長大于0)。由此得到格局X′。對圖1中格局做水平左移動作后的格局如圖2所示。2.從X′出發(fā)做豎直下移動作(1)所有塊按照(y,x)的字典序從小到大排序;(2)按序對當前矩形塊豎直下移,直至其下邊與某塊或框的下壁相貼。由此得到格局X″,返回X″。對圖2中格局做水平下移動作后的格局如圖3所示。2.2左下平行擬合為了求解問題P,需對待放塊集A的每個子集S,以及S中每個塊的左下角坐標(由于塊的寬和高已確定,因此由其左下角坐標和放置方向即可唯一確定其放置位置)和方向(橫放或豎放)進行窮舉。由于塊放入后,可在框內(nèi)平滑移動,其候選的放置位置有無限多種可能,因此問題P的搜索空間為無限大。目前國際上討論此問題的計算復雜性時,均默認塊的左下角坐標為整數(shù)值,即只搜索整格點的情況,但未給出嚴格的證明。本節(jié)擬給出嚴格的證明,即若問題P存在最優(yōu)解,則一定存在塊放置位置都為整數(shù)坐標的最優(yōu)解。設框的左壁為第0個寬為0的特殊矩形。本小節(jié)將利用左下平移算法逐步證明問題P若存在最優(yōu)解,則一定存在整數(shù)坐標的最優(yōu)解。命題1在格局X′中,第k(1≤k≤n)個左移的矩形塊必然和第i(0≤i<k)個左移的矩形塊的右邊相貼。證明:(反證法)假設存在第k(1≤k≤n)個左移的矩形塊在格局X′中不和前k-1個左移的矩形塊中的任意一個矩形塊的右邊相貼。又由第1步的移動規(guī)則可知矩形塊在完成動作后必然和框左壁或其他矩形塊的右邊相貼?！嘟Y合假設和第1步的移動規(guī)則易知,第k個左移的矩形塊只可能和第j(j>k)個左移的矩形塊的右邊相貼?！咚袎K是按照(x,y)的字典序從小到大排序的?！嘣诘趉個矩形塊進行左移動作時,第j(j>k)個左移的矩形塊不可能在其左側。∵在第k個左移的矩形塊進行左移動作時,第j(j>k)個左移的矩形塊的位置不發(fā)生任何變化。∴在第k個左移的矩形塊完成左移動作時,第j(j>k)個左移的矩形塊不可能在其左側?！嗟趉個左移的矩形塊不可能和第j(j>k)個左移的矩形塊的右邊相貼。與假設矛盾,故假設不成立,原命題成立。命題1得證。命題2若問題P存在一個合法解,則該合法解通過左下平移算法A0得到的格局X″對應于布局中每個矩形塊的左下角坐標均為整數(shù)。證明:首先證明X″中的每個矩形塊的左下角的x坐標均為整數(shù)。∵第2步中并未改變?nèi)我粔K左下角的x坐標?！嘀恍枳C明X′中每個矩形塊左下角的x坐標均為整數(shù)值。用數(shù)學歸納法證明X′中任一塊左下角的x坐標均為整數(shù)值:1.對于第1個移動的矩形塊:∵所有塊是按照(x,y)的字典序從小到大排序的?！嘤傻?步的移動規(guī)則易知該塊在完成左移動作后必然與框的左壁相貼?！嗥渥笙陆莤坐標等于0,為整數(shù)值。2.假設前k(k≥1)個矩形塊的左下角x坐標為整數(shù)。由命題1可知,第k+1個移動的矩形塊在格局X′中必然與框的左壁相貼,或者和第i(1≤i≤k)個移動的矩形塊的右邊相貼。(1)若該塊在格局X′中與框的左壁相貼,則其左下角x坐標等于0,為整數(shù)。(2)若該塊在格局X′中和第i(1≤i≤k)個矩形塊相貼,則有xk+1=xi+length[i],其中l(wèi)ength[i]表示塊i在x方向的長度?！哂杉僭O知xi為整數(shù),而由問題P的定義可知length[i]為整數(shù)。∴xk+1是整數(shù)。綜上,第k(1≤k≤n)個矩形塊,其左下角x坐標為整數(shù)。即X′中每個矩形塊的左下角x坐標均為整數(shù)?！郮″中每個矩形塊的左下角x坐標均為整數(shù)。同理可證X″中每個矩形塊的左下角y坐標也均為整數(shù)。命題3若問題P存在最優(yōu)解,則一定存在對應布局中每個矩形塊左下角坐標均為整數(shù)的最優(yōu)解。證明:設格局X={(xi1,xi2),(xi2,yi2),…,(xik,yik)}為問題P的最優(yōu)解。顯然存在以下兩種情況:(1)若X對應布局中每個矩形塊左下角坐標均為整數(shù)。這種情況下,顯然X就是滿足條件的最優(yōu)解,命題3成立。(2)若X對應布局中存在矩形塊左下角坐標不均為整數(shù)?！咦顑?yōu)解必然為合法解。∴由命題2可知,合法解X通過左下平移算法A0可以得到另一合法解X″,且X″對應布局中每個矩形塊的左下角坐標均為整數(shù)?！咦笙缕揭扑惴ˋ0并未改變格局中矩形塊的數(shù)量。命題3得證。至此,問題P整數(shù)最優(yōu)解的存在性得到了完整的證明。3.在s中，每個矩形截面都有兩個垂直和水平放置方向。4、評估并獲得模式的有效性。否則，返回13.1角x-坐標等同(1)構造節(jié)點:將框的左壁看作一寬為0、高為H的特殊塊,對應節(jié)點0;矩形塊i對應節(jié)點i。(2)構造有向邊:記塊i的左下角坐標為(xi,yi),右上角坐標為(xi′,yi′)。對于塊i和塊j,若xi′=xj(即塊i的右上角x坐標與塊j的左下角x坐標相等),則在X-圖中生成一條由節(jié)點i指向節(jié)點j的有向邊。(3)邊權:所有邊的權值固定為1。(4)點權:節(jié)點i的權值為矩形塊i的寬,節(jié)點0的權值為0。圖2中格局X″對應的X-圖如圖4所示。其邊權均為1,節(jié)點的權為矩形塊i的寬。2.Y-圖與X-圖的構造方法類似:(1)構造節(jié)點:將框的下壁看作一寬為L、高為0的特殊塊,其對應節(jié)點0;矩形塊i對應節(jié)點i。(2)構造有向邊:記塊i的左下角坐標為(xi,yi),右上角坐標為(xi′,yi′)。對于塊i和塊j,若yi′=yj(即塊i的右上角y坐標與塊j的左下角y坐標相等),則在X-圖中生成一條由節(jié)點i指向節(jié)點j的有向邊。(3)邊權:所有邊的權值固定為1。(4)點權:節(jié)點i的權值為矩形塊i的高,節(jié)點0的權值為0。圖3中格局X″對應的Y-圖如圖5所示。其邊權均為1,節(jié)點的權為矩形塊i的寬。3.2節(jié)點0至節(jié)點i、ki假定框左壁為矩形塊0,通過觀察不難發(fā)現(xiàn)X-圖的一些基本性質。性質1除節(jié)點0的入度為0以外,其余節(jié)點的入度均≥1。證明:(1)矩形塊0左邊無矩形塊,故節(jié)點0的入度為0。(2)在算法A0水平左移過程中,任意一個矩形塊i(i∈{1,2,…,n})均與矩形塊j(j∈{0,1,…,n},j≠i)相貼,即有xi″=xj′。而在水平下移動作中,i,j的x坐標均不變。因此節(jié)點i在X-圖必然至少有一條邊指向它,即入度≥1。性質2X-圖為有向無環(huán)圖。證明:假設X-圖中存在環(huán){i1,i2,…,im},則xi1<xi2<…<xim<xi1,矛盾。故X-圖為有向無環(huán)圖。性質3從節(jié)點0至節(jié)點i路徑上的所有節(jié)點的點權和代表矩形i的右上角x坐標。證明:用dist[j]表示節(jié)點0到節(jié)點j的邊權和。例如圖4中dist=dist=1,dist=2。定義Ki={j|dist[j]=i}。例如圖4中K1={1,6}?，F(xiàn)用數(shù)學歸納法證明對于ue02fi∈[0,n]及ue02fj∈Ki,有節(jié)點0至節(jié)點j上所有節(jié)點的點權和代表矩形j的右上角x坐標成立。1)當i=0時,Ki={0},而矩形0的點權及寬為0,顯然結論成立。2)假設對于i=m(0≤m<n)時結論成立。對于ue02fj∈Ki,由性質1可知必然存在節(jié)點l使得l指向j,即xl′=xj?！遆-圖中所有邊權值固定為1,∴必然有l(wèi)∈Ki。∴xl′等于節(jié)點0至節(jié)點l的點權和?！鄕j等于節(jié)點0至節(jié)點l的點權和?！吖?jié)點j的點權為矩形j的寬wj,∴xj′+wj等于節(jié)點0至節(jié)點j的點權和,∴對于i+1結論也成立。綜上所述,對于ue02fi∈[0,n]及ue02fj∈Ki,有節(jié)點0至節(jié)點j上所有節(jié)點的點權和代表矩形k的右上角x坐標成立。而顯然,K=K1∪K2∪…∪Km∪…={0,1,…,n}故原命題成立。性質4對任一節(jié)點i,從節(jié)點0至節(jié)點i若有多條路徑,則這些路徑的點權和相等。證明:節(jié)點0至節(jié)點i有多條路徑共有兩種情況:(1)節(jié)點i被多個節(jié)點指向。(2)節(jié)點i之前的某個節(jié)點j被多個點指向,而節(jié)點j到節(jié)點i只有一條路徑。分情況討論:(1)若節(jié)點i被多個節(jié)點i1,i2,…,im指向。由有向邊的構造方法可知必然有xi1′=xi,xi2′=xi,…,xim′=xi?！鄕i1′=xi2′=…=xim′?！邚墓?jié)點0至節(jié)點i的路徑的上所有節(jié)點的點權和代表矩形i的右上角x坐標?！喙?jié)點0至節(jié)點k1,k2,…,km的路徑的點權和相等。(2)節(jié)點i之前的某個節(jié)點j被多個點指向,而節(jié)點j到節(jié)點i只有一條路徑。由(1)易知節(jié)點0到節(jié)點j的任意路徑的點權和相等。∵節(jié)點j到節(jié)點i只有一條路徑。∴節(jié)點0到節(jié)點i的任意路徑的點權和相等。綜上所述,若有從節(jié)點0至節(jié)點i的多條路徑,則這些路徑的點權和相等。性質5(節(jié)點i在X-圖中的點權,節(jié)點i在Y-圖中的點權)∈{(wi,hi),(hi,wi)}。即當節(jié)點i在一個圖中的點權已知時,其在另一個圖中的點權固定。不難證明,Y-圖也有與X-圖類似的性質。由上述性質可以得到另一條重要性質。性質6一對(X-圖,Y-圖)與一個格局一一對應。證明:(1)一個格局唯一對應一對(X-圖,Y-圖)。由X-圖和Y-圖的構造規(guī)則易知,由一個格局只可能生成一對確定(X-圖,Y-圖)。(2)一對(X-圖,Y-圖)唯一對應一個格局。先證明X-圖中所有節(jié)點對應的矩形左下角x坐標唯一確定。由X-圖性質3可知,節(jié)點0到節(jié)點i的路徑的點權和等于矩形i的右上角坐標?！吖?jié)點i的點權即為矩形i的寬。∴矩形i的左下角x坐標可以由節(jié)點0到節(jié)點i的路徑點權和和節(jié)點i的點權確定。而由X-圖性質4可知,若對某節(jié)點i,有從節(jié)點0至節(jié)點i的多條路徑,則這些路徑的點權和相等。∴矩形i的左下角x坐標唯一確定。命題得證。同理可以證明,Y-圖中所有節(jié)點對應的矩形左下角y坐標唯一確定。綜上所述,一對(X-圖,Y-圖)與一個格局一一對應。因此只需要搜索所有的X-圖和Y-圖即可搜索到所有的格局。但是想要得到所有可能的X-圖與Y-圖是比較困難的,下節(jié)將其轉化為結構更簡單的形式。3.3節(jié)點數(shù)確定—有向圖向樹的轉化通過X-圖的性質3可以知道,若對某節(jié)點i,有從節(jié)點0至節(jié)點i的多條路徑,則這些路徑的點權之和相等。由性質4可知路徑的點權和代表矩形i的右上角x坐標。因此僅需知道節(jié)點0至節(jié)點i的一條路徑即可唯一確定矩形i的放置位置。由此可以得到由X-圖轉換為X-樹的規(guī)則:(1)在X-圖中若存在節(jié)點i被多條邊指向,則只保留其中一條邊。(2)將所有有向邊改為無向邊。圖4對應的X-樹如圖6所示。命題4按照上述規(guī)則得到的一定是一棵樹。證明:(1)X-圖為一個節(jié)點數(shù)為n+1的有向無環(huán)圖。在X-圖執(zhí)行規(guī)則(1)后得到的新圖G′中,顯然除了節(jié)點0,其余節(jié)點的入度均為1,故新圖G′僅有n條有向邊。在G′執(zhí)行規(guī)則(2)后得到新圖G″,G″顯然為無向圖?！逩′中對任意節(jié)點i必然存在節(jié)點0到i的一條路徑?！嘣贕″中對任意節(jié)點i必然存在節(jié)點0到i的一條路徑。∴對任意兩個節(jié)點i和j必然存在節(jié)點0到i和0到j的路徑,即存在節(jié)點i到j的路徑?！郍″為無向連通圖。下證G″中無環(huán),假設G″中存在簡單回路,簡單回路中包含k個點,則簡單回路中必然有k條邊?！逩″為連通圖?！嗍Ｓ嗟膎-k+1個節(jié)點中必然每個節(jié)點均有邊與之相連,且有一個節(jié)點與回路有邊相連?！嘀辽龠€有n-k+1條邊。∴G″中共有n+1條邊,與條件矛盾,假設不成立?！郍″為無向連通圖,有n條邊,且沒有簡單回路?！郍″為一棵樹,顯然節(jié)點0為G″的根。由此命題得證。同理,可以依據(jù)上述規(guī)則得到Y-樹。由于保留邊的隨機性,顯然當節(jié)點數(shù)n確定時,一對(X-圖,Y-圖)可能對應多對(X-樹,Y-樹),但一對(X-樹,Y-樹)唯一對應一對(X-圖,Y-圖)。由性質6可知一對(X-圖,Y-圖)是和一個格局一一對應的,故易知一個格局可能對應多對(X-樹,Y-樹),但一對(X-樹,Y-樹)唯一對應一個格局。即|X-樹,Y-樹對應的格局|≥|X-圖,Y-圖對應的格局|,這保證了利用X-樹和Y-樹來求解問題P時搜索空間的完整性。3.4間接搜索的x-樹和y-樹為了方便在搜索時遍歷到所有的X-樹和Y-樹,可以將X-樹與Y-樹編碼化,通過搜索所有可能的編碼來間接地搜索到所有的X-樹和Y-樹。而實現(xiàn)樹的編碼化可以借用Prüfer編碼的思路,將樹轉變成Prüfer編碼,從文獻中易知Prüfer編碼和一棵樹唯一對應,因此可以通過搜索n+1個節(jié)點的樹的所有Prüfer編碼來找到所有可能的X-樹和Y-樹。3.5高聚物集的生成設n個矩形塊構成集合S1.從1至n枚舉初始待放矩形塊個數(shù)num;2.枚舉集合S的元素個數(shù)為num的子集,代表待放矩形塊;3.預生成所有長度為num的01序列于數(shù)組A中,表示方向序列(矩形塊0方向及位置固定,故無需枚舉其方向);∴在初始格局X中此塊必然在所有塊的最左邊。對于第k+1個矩形塊:命題2得證?！郮為合法解?！郮″的矩形框面積利用率=X的矩形框面積利用率?！郮″也是最優(yōu)解。2.3輸出最優(yōu)解的計算復雜度利用2.2節(jié)的命題和左下平移算法A0可以輕松得到一個基于枚舉法的完備算法A1。完備算法A1:1.枚舉待放塊集的每個子集S;2.枚舉S中每個矩形塊所有左下角整數(shù)坐標;3.枚舉S中每個矩形塊橫豎兩種放置方向;4.判斷得到格局的合法性,若不合法,返回1;5.計算空間利用率,若其比當前最優(yōu)解的空間利用率大,則更新最優(yōu)解,返回1;6.輸出最優(yōu)解及其空間利用率。在算法A1中,每個塊或者放入或者不放入,若放入,其放置方向有兩種。因此,其在框內(nèi)不同整格點上的放置方式為2(W-wi+1)(H-hi+1)≤2WH,不在框內(nèi)時只有一種情況。故完備算法A1最多只需要(2WH+1)n次搜索,檢驗每個格局的合法性,并輸出其中框面積利用率最高的一個及其對應的布局即可精確求解問題P。因此,問題P的計算復雜度為O((2WH+1)n)。至此,我們將問題P的解空間由無限大減為有限大小。但其解空間仍與框的尺寸W、H有關。由于求解網(wǎng)絡流問題的Ford-Fulkerson算法的計算復雜度與網(wǎng)絡的最小割有關,使得FF算法對一些頂點數(shù)、邊數(shù)不變但最小割值很大的網(wǎng)絡計算復雜度過高。因此,隨后有研究者給出了僅與網(wǎng)絡的頂點數(shù)和邊數(shù)有關的多種算法。類似地,對問題P,在W、H的值很大但待放塊數(shù)并不多的情形下,上述完備算法的計算復雜度過高。是否可以找到計算復雜度僅與待放塊數(shù)有關的算法呢?下一節(jié)擬給出一個只與待放塊數(shù)n有關的完備算法。3搜索空間s通過觀察完備算法A1可以發(fā)現(xiàn)它搜索了很多無用的(即矩形有重疊部分)布局,而實際上只需搜索左下平移算法有可能得到的合法布局構成的搜索空間S即可?；赑rüfer編碼,本節(jié)將可能生成的所有布局與一有向圖G(V,E)對應起來,然后將G(V,E)轉化為樹并編碼化,從而降低計算的復雜度。3.1節(jié)點權的生成1.X-圖(1)構造節(jié)點:將框的左壁看作一寬為0、高為H的特殊塊,對應節(jié)點0;矩形塊i對應節(jié)點i。(2)構造有向邊:記塊i的左下角坐標為(xi,yi),右上角坐標為(xi′,yi′)。對于塊i和塊j,若xi′=xj(即塊i的右上角x坐標與塊j的左下角x坐標相等),則在X-圖中生成一條由節(jié)點i指向節(jié)點j的有向邊。(3)邊權:所有邊的權值固定為1。(4)點權:節(jié)點i的權值為矩形塊i的寬,節(jié)點0的權值為0。圖2中格局X″對應的X-圖如圖4所示。其邊權均為1,節(jié)點的權為矩形塊i的寬。2.Y-圖與X-圖的構造方法類似:(1)構造節(jié)點:將框的下壁看作一寬為L、高為0的特殊塊,其對應節(jié)點0;矩形塊i對應節(jié)點i。(2)構造有向邊:記塊i的左下角坐標為(xi,yi),右上角坐標為(xi′,yi′)。對于塊i和塊j,若yi′=yj(即塊i的右上角y坐標與塊j的左下角y坐標相等),則在X-圖中生成一條由節(jié)點i指向節(jié)點j的有向邊。(3)邊權:所有邊的權值固定為1。(4)點權:節(jié)點i的權值為矩形塊i的高,節(jié)點0的權值為0。圖3中格局X″對應的Y-圖如圖5所示。其邊權均為1,節(jié)點的權為矩形塊i的寬。3.2節(jié)點0至節(jié)點i、ki假定框左壁為矩形塊0,通過觀察不難發(fā)現(xiàn)X-圖的一些基本性質。性質1除節(jié)點0的入度為0以外,其余節(jié)點的入度均≥1。證明:(1)矩形塊0左邊無矩形塊,故節(jié)點0的入度為0。(2)在算法A0水平左移過程中,任意一個矩形塊i(i∈{1,2,…,n})均與矩形塊j(j∈{0,1,…,n},j≠i)相貼,即有xi″=xj′。而在水平下移動作中,i,j的x坐標均不變。因此節(jié)點i在X-圖必然至少有一條邊指向它,即入度≥1。性質2X-圖為有向無環(huán)圖。證明:假設X-圖中存在環(huán){i1,i2,…,im},則xi1<xi2<…<xim<xi1,矛盾。故X-圖為有向無環(huán)圖。性質3從節(jié)點0至節(jié)點i路徑上的所有節(jié)點的點權和代表矩形i的右上角x坐標。證明:用dist[j]表示節(jié)點0到節(jié)點j的邊權和。例如圖4中dist=dist=1,dist=2。定義Ki={j|dist[j]=i}。例如圖4中K1={1,6}。現(xiàn)用數(shù)學歸納法證明對于ue420i∈[0,n]及ue420j∈Ki,有節(jié)點0至節(jié)點j上所有節(jié)點的點權和代表矩形j的右上角x坐標成立。2)假設對于i=m(0≤m<n)時結論成立。1)當i=0時,Ki={0},而矩形0的點權及寬為0,顯然結論成立。對于ue420j∈Ki,由性質1可知必然存在節(jié)點l使得l指向j,即xl′=xj?！遆-圖中所有邊權值固定為1,∴必然有l(wèi)∈Ki。∴xl′等于節(jié)點0至節(jié)點l的點權和?！鄕j等于節(jié)點0至節(jié)點l的點權和?！吖?jié)點j的點權為矩形j的寬wj,∴xj′+wj等于節(jié)點0至節(jié)點j的點權和,∴對于i+1結論也成立。綜上所述,對于ue420i∈[0,n]及ue420j∈Ki,有節(jié)點0至節(jié)點j上所有節(jié)點的點權和代表矩形k的右上角x坐標成立。而顯然,K=K1∪K2∪…∪Km∪…={0,1,…,n}故原命題成立。性質4對任一節(jié)點i,從節(jié)點0至節(jié)點i若有多條路徑,則這些路徑的點權和相等。證明:節(jié)點0至節(jié)點i有多條路徑共有兩種情況:(1)節(jié)點i被多個節(jié)點指向。(2)節(jié)點i之前的某個節(jié)點j被多個點指向,而節(jié)點j到節(jié)點i只有一條路徑。分情況討論:(1)若節(jié)點i被多個節(jié)點i1,i2,…,im指向。由有向邊的構造方法可知必然有xi1′=xi,xi2′=xi,…,xim′=xi。∴xi1′=xi2′=…=xim′?！邚墓?jié)點0至節(jié)點i的路徑的上所有節(jié)點的點權和代表矩形i的右上角x坐標?！喙?jié)點0至節(jié)點k1,k2,…,km的路徑的點權和相等。(2)節(jié)點i之前的某個節(jié)點j被多個點指向,而節(jié)點j到節(jié)點i只有一條路徑。由(1)易知節(jié)點0到節(jié)點j的任意路徑的點權和相等?！吖?jié)點j到節(jié)點i只有一條路徑?！喙?jié)點0到節(jié)點i的任意路徑的點權和相等。綜上所述,若有從節(jié)點0至節(jié)點i的多條路徑,則這些路徑的點權和相等。性質5(節(jié)點i在X-圖中的點權,節(jié)點i在Y-圖中的點權)∈{(wi,hi),(hi,wi)}。即當節(jié)點i在一個圖中的點權已知時,其在另一個圖中的點權固定。不難證明,Y-圖也有與X-圖類似的性質。由上述性質可以得到另一條重要性質。性質6一對(X-圖,Y-圖)與一個格局一一對應。證明:(1)一個格局唯一對應一對(X-圖,Y-圖)。由X-圖和Y-圖的構造規(guī)則易知,由一個格局只可能生成一對確定(X-圖,Y-圖)。(2)一對(X-圖,Y-圖)唯一對應一個格局。先證明X-圖中所有節(jié)點對應的矩形左下角x坐標唯一確定。由X-圖性質3可知,節(jié)點0到節(jié)點i的路徑的點權和等于矩形i的右上角坐標?！吖?jié)點i的點權即為矩形i的寬?！嗑匦蝘的左下角x坐標可以由節(jié)點0到節(jié)點i的路徑點權和和節(jié)點i的點權確定。而由X-圖性質4可知,若對某節(jié)點i,有從節(jié)點0至節(jié)點i的多條路徑,則這些路徑的點權和相等?！嗑匦蝘的左下角x坐標唯一確定。命題得證。同理可以證明,Y-圖中所有節(jié)點對應的矩形左下角y坐標唯一確定。綜上所述,一對(X-圖,Y-圖)與一個格局一一對應。因此只需要搜索所有的X-圖和Y-圖即可搜索到所有的格局。但是想要得到所有可能的X-圖與Y-圖是比較困難的,下節(jié)將其轉化為結構更簡單的形式。3.3節(jié)點數(shù)確定—有向圖向樹的轉化通過X-圖的性質3可以知道,若對某節(jié)點i,有從節(jié)點0至節(jié)點i的多條路徑,則這些路徑的點權之和相等。由性質4可知路徑的點權和代表矩形i的右上角x坐標。因此僅需知道節(jié)點0至節(jié)點i的一條路徑即可唯一確定矩形i的放置位置。由此可以得到由X-圖轉換為X-樹的規(guī)則:(1)在X-圖中若存在節(jié)點i被多條邊指向,則只保留其中一條邊。(2)將所有有向邊改為無向邊。圖4對應的X-樹如圖6所示。命題4按照上述規(guī)則得到的一定是一棵樹。證明:(1)X-圖為一個節(jié)點數(shù)為n+1的有向無環(huán)圖。在X-圖執(zhí)行規(guī)則(1)后得到的新圖G′中,顯然除了節(jié)點0,其余節(jié)點的入度均為1,故新圖G′僅有n條有向邊。在G′執(zhí)行規(guī)則(2)后得到新圖G″,G″顯然為無向圖?！逩′中對任意節(jié)點i必然存在節(jié)點0到i的一條路徑?！嘣贕″中對任意節(jié)點i必然存在節(jié)點0到i的一條路徑?！鄬θ我鈨蓚€節(jié)點i和j必然存在節(jié)點0到i和0到j的路徑,即存在節(jié)點i到j的路徑?！郍″為無向連通圖。下證G″中無環(huán),假設G″中存在簡單回路,簡單回路中包含k個點,則簡單回路中必然有k條邊?！逩″為連通圖?！嗍Ｓ嗟膎-k+1個節(jié)點中必然每個節(jié)點均有邊與之相連,且有一個節(jié)點與回路有邊相連?！嘀辽龠€有n-k+1條邊?！郍″中共有n+1條邊,與條件矛盾,假設不成立?！郍″為無向連通圖,有n條邊,且沒有簡單回路?！郍″為一棵樹,顯然節(jié)點0為G″的根。由此命題得證。同理,可以依據(jù)上述規(guī)則得到Y-樹。由于保留邊的隨機性,顯然當節(jié)點數(shù)n確定時,一對(X-圖,Y-圖)可能對應多對(X-樹,Y-樹),但一對(X-樹,Y-樹)唯一對應一對(X-圖,Y-圖)。由性質6可知一對(X-圖,Y-圖)是和一個格局一一對應的,故易知一個格局可能對應多對(X-樹,Y-樹),但一對(X-樹,Y-樹)唯一對應一個格局。即|X-樹,Y-樹對應的格局|≥|X-圖,Y-圖對應的格局|,這保證了利用X-樹和Y-樹來求解問題P時搜索空間的完整性。3.4間接搜索的x-樹和y-樹為了方便在搜索時遍歷到所有的X-樹和Y-樹,可以將X-樹與Y-樹編碼化,通過搜索所有可能的編碼來間接地搜索到所有的X-樹和Y-樹。而實現(xiàn)樹的編碼化可以借用Prüfer編碼的思路,將樹轉變成Prüfer編碼,從文獻中易知Prüfer編碼和一棵樹唯一對應,因此可以通過搜索n+1個節(jié)點的樹的所有Prüfer編碼來找到所有可能的X-樹和Y-樹。3.5pruhen編碼設n個矩形塊構成集合S1.從1至n枚舉初始待放矩形塊個數(shù)num;2.枚舉集合S的元素個數(shù)為num的子集,代表待放矩形塊;3.預生成所有長度為num的01序列于數(shù)組A中,表示方向序列(矩形塊0方向及位置固定,故無需枚舉其方向);4.預生成所有長度為num+1的Prüfer編碼于數(shù)組B中;5.枚舉B中元素組成的排列〈B1,B2〉于數(shù)組C中,分別代表X-樹和Y-樹的結構;6.枚舉A中元素和C中元素組成的組合〈Ai,Cj〉,并判斷其對應格局的合法性,若合法則保存該方案,并跳轉1;7.輸出保存的最優(yōu)方案并退出。3.6算法b:存在x-樹,y-樹對未被算法bp的編碼命題5算法A2枚舉了所有的待放塊集合。證明:(反證法)。假設存在待放塊集合S′未被算法A2枚舉。設該集合元素個數(shù)為k,顯然有1≤k≤n。∴由A2中第1步可知必然存在num=k的情況。而當num=k時,A2在第2步會枚舉S所有個數(shù)為num的子集。由此可推出S′ue05bS,與條件矛盾,假設不成立,原命題成立。命題5得證。命題6算法A2枚舉了所有的(X-樹,Y-樹)對。證明:(反證法)。假設存在(X-樹