胡文蓓+饒昊

摘 要：二維矩形Packing問題備受關(guān)注。對(duì)于這一問題，有學(xué)者提出了擬人型穴度算法。該類啟發(fā)式算法極大提高了解決二維Packing問題的效率，其引用了動(dòng)作空間的概念。此類算法中的基本算法B0旨在通過制定的指標(biāo)選出每一次放置的矩形塊及其矩形塊放置的位置，待選出后完成矩形塊放置動(dòng)作，再進(jìn)行動(dòng)作空間的更新操作，以此類推，只至最終格局。基于此，詳細(xì)解釋了算法中動(dòng)作空間的更新過程。

關(guān)鍵詞：Packing問題；NP難度；動(dòng)作空間更新；擬人型算法

DOIDOI：10.11907/rjdk.171602

中圖分類號(hào)：TP302.7

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：1672-7800（2017）008-0019-02

0 引言

所謂的二維矩形Packing問題是指：在二維空間里，存在一個(gè)矩形框和有限個(gè)矩形塊，矩形框和矩形塊的長(zhǎng)和寬已知，現(xiàn)將這些矩形塊放入框中，并希望矩形塊盡可能多地放入到矩形框內(nèi)，放入的塊與塊之間無重疊[1]。

自1971年提出二維矩形Packing問題以來，此問題一直都是數(shù)學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域中未被解決的重大問題之一，中外學(xué)者一直在進(jìn)行著大量的研究。近幾十年來，國(guó)內(nèi)外學(xué)者提出了多種高效近似算法，可分為非隨機(jī)型和隨機(jī)型近似算法。非隨機(jī)型近似算法中提出選擇放置動(dòng)作的優(yōu)先序，并在其基礎(chǔ)上進(jìn)行適當(dāng)?shù)拿杜e[2]，包括底部左齊擇優(yōu)匹配算法[4]、分支限界[5]、擬人算法[3]。

本文主要基于擬人型穴度算法、優(yōu)美度枚舉算法中的基本算法B0，詳細(xì)描述其動(dòng)作空間更新過程。

1 基本算法B0

相關(guān)算法定義如下：

定義1（格局） 框內(nèi)放入的矩形塊的具體位置和方向不會(huì)再改變，稱此為一個(gè)格局。初始格局時(shí)，框內(nèi)未放入任何矩形塊。當(dāng)所有塊都已放入框中，或框外的剩余塊均無法再放入時(shí)，稱為終止格局[1]。

定義2（動(dòng)作空間） 動(dòng)作空間即是框內(nèi)一塊虛擬的矩形塊，此虛擬矩形塊的上、下、左、右4 條邊均與其它已放入的塊或框的邊重合，則稱該虛擬矩形塊為動(dòng)作空間。

定義3（占角動(dòng)作） 矩形框中每個(gè)90°的角都稱為角區(qū)。若將一個(gè)矩形塊放入到動(dòng)作空間的4個(gè)角，則稱此為一個(gè)占角動(dòng)作。

基本算法B0的詳細(xì)步驟如下：準(zhǔn)備好矩形框和矩形塊。最初始的矩形框里是空的，檢查矩形塊，按照一定規(guī)則對(duì)矩形塊進(jìn)行排序；然后把矩形塊放入到框中，先確認(rèn)好動(dòng)作空間，進(jìn)行占角動(dòng)作的枚舉。做完動(dòng)作后，對(duì)所有動(dòng)作空間做如下兩步操作：①更新有動(dòng)作的動(dòng)作空間；②刪去被其它動(dòng)作空間包含的動(dòng)作空間[2]。

依此類推，直到終止格局。B0算法如圖1所示。

2 動(dòng)作空間更新

通過研究可以知道，動(dòng)作空間的更新對(duì)于B0算法十分重要。動(dòng)作空間擁有兩個(gè)特點(diǎn)：①它是一個(gè)虛擬的矩形；②動(dòng)作空間之間可以相互重疊；③動(dòng)作空間的位置有如下情況：矩形塊放入原動(dòng)作空間的下兩角或上兩角；④矩形塊放入原動(dòng)作空間的左兩角或右兩角。

動(dòng)作空間與動(dòng)作之間存在以下幾種情況：①動(dòng)作把動(dòng)作空間覆蓋；②動(dòng)作空間把動(dòng)作包?。虎蹌?dòng)作橫穿動(dòng)作空間；④動(dòng)作豎穿動(dòng)作空間；⑤動(dòng)作大于動(dòng)作空間；⑥多動(dòng)作與動(dòng)作空間重疊。

2.1 動(dòng)作把動(dòng)作空間覆蓋

滿足以下4個(gè)條件：①動(dòng)作左下角頂點(diǎn)的橫坐標(biāo)的值小于或等于動(dòng)作空間左下角頂點(diǎn)的橫坐標(biāo)的值；②動(dòng)作左下角頂點(diǎn)的橫坐標(biāo)加動(dòng)作的寬的值大于或等于動(dòng)作空間左下角頂點(diǎn)的橫坐標(biāo)加上動(dòng)作空間的寬的值；③動(dòng)作左下角頂點(diǎn)的縱坐標(biāo)的值小于或等于動(dòng)作空間左下角頂點(diǎn)的縱坐標(biāo)的值；④動(dòng)作左下角頂點(diǎn)的縱坐標(biāo)加動(dòng)作的高的值大于或等于動(dòng)作空間左下角頂點(diǎn)的縱坐標(biāo)加上動(dòng)作空間的高的值。滿足了這些條件，即是動(dòng)作把動(dòng)作空間覆蓋。如若出現(xiàn)動(dòng)作把動(dòng)作空間覆蓋的情況，又因?yàn)閯?dòng)作是放在動(dòng)作空間里，則說明存在其它動(dòng)作空間一定包裹了此動(dòng)作，所以刪除此動(dòng)作空間，循環(huán)下一個(gè)動(dòng)作空間。

2.2 動(dòng)作空間把動(dòng)作包住

滿足以下4個(gè)條件：①動(dòng)作左下角頂點(diǎn)的橫坐標(biāo)的值大于動(dòng)作空間左下角頂點(diǎn)的橫坐標(biāo)的值；②動(dòng)作左下角頂點(diǎn)的橫坐標(biāo)加動(dòng)作的寬度值小于動(dòng)作空間的寬加動(dòng)作空間左下角頂點(diǎn)的橫坐標(biāo)的值；③動(dòng)作左下角頂點(diǎn)的縱坐標(biāo)的值大于動(dòng)作空間左下角頂點(diǎn)的縱坐標(biāo)的值；④動(dòng)作左下角頂點(diǎn)的縱坐標(biāo)加動(dòng)作的高度值小于動(dòng)作空間的高加動(dòng)作空間左下角頂點(diǎn)的縱坐標(biāo)的值。滿足了這些條件，即動(dòng)作空間把動(dòng)作包住。如若出現(xiàn)動(dòng)作空間把動(dòng)作包住的情況，則當(dāng)前動(dòng)作空間改變。原空間會(huì)生成根據(jù)動(dòng)作的位置生成4個(gè)新的動(dòng)作空間，把新增動(dòng)作空間寫入動(dòng)作空間數(shù)組，即完成動(dòng)作空間的更新。

2.3 動(dòng)作橫穿動(dòng)作空間

滿足以下3個(gè)條件：①動(dòng)作左下角頂點(diǎn)的橫坐標(biāo)的值小于或等于動(dòng)作空間左下角頂點(diǎn)的橫坐標(biāo)的值或動(dòng)作左下角頂點(diǎn)的橫坐標(biāo)加上動(dòng)作的寬度值大于或等于動(dòng)作空間左下角頂點(diǎn)的橫坐標(biāo)加動(dòng)作空間的寬度值；②動(dòng)作左下角頂點(diǎn)的縱坐標(biāo)的值大于動(dòng)作空間左下角頂點(diǎn)的縱坐標(biāo)的值；③動(dòng)作左下角頂點(diǎn)的縱坐標(biāo)加動(dòng)作的高度值小于動(dòng)作空間左下角頂點(diǎn)的縱坐標(biāo)加動(dòng)作空間的高度值。滿足了這些條件，即動(dòng)作橫穿動(dòng)作空間。如若動(dòng)作左下角的橫坐標(biāo)小于或等于動(dòng)作空間左下角的橫坐標(biāo)并且動(dòng)作左下角的橫坐標(biāo)加動(dòng)作的寬度值大于或等于動(dòng)作空間左下角的橫坐標(biāo)加動(dòng)作空間的寬度值，即動(dòng)作全橫穿動(dòng)作空間，如圖2（a）所示。如若動(dòng)作左下角的橫坐標(biāo)小于或等于動(dòng)作空間左下角的橫坐標(biāo)并且動(dòng)作左下角的橫坐標(biāo)加動(dòng)作的寬度值小于動(dòng)作空間左下角的橫坐標(biāo)加動(dòng)作空間的寬度值，即動(dòng)作左橫穿動(dòng)作空間，如圖2（b）所示。剩下為動(dòng)作右橫穿動(dòng)作空間，如圖2（c）所示。

2.4 動(dòng)作豎穿動(dòng)作空間

滿足以下3個(gè)條件：①動(dòng)作左下角頂點(diǎn)的橫坐標(biāo)的值大于動(dòng)作空間左下角頂點(diǎn)的橫坐標(biāo)的值；②動(dòng)作左下角頂點(diǎn)的橫坐標(biāo)加動(dòng)作的寬度值小于動(dòng)作空間左下角頂點(diǎn)的橫坐標(biāo)加動(dòng)作空間的寬度值；③動(dòng)作左下角頂點(diǎn)的縱坐標(biāo)的值小于或等于動(dòng)作空間左下角頂點(diǎn)的縱坐標(biāo)的值或者動(dòng)作左下角頂點(diǎn)的縱坐標(biāo)加動(dòng)作的高度值大于或等于動(dòng)作空間左下角頂點(diǎn)的縱坐標(biāo)加動(dòng)作空間的高度值。滿足了這些條件，即動(dòng)作豎穿動(dòng)作空間。如若動(dòng)作左下角的縱坐標(biāo)小于或等于動(dòng)作空間左下角的縱坐標(biāo)并且動(dòng)作左下角的縱坐標(biāo)加動(dòng)作的高度值大于或等于動(dòng)作空間左下角的縱坐標(biāo)加動(dòng)作空間的高度值，即動(dòng)作全豎穿動(dòng)作空間，如圖3（a）所示。如若動(dòng)作左下角的縱坐標(biāo)小于或等于動(dòng)作空間左下角的縱坐標(biāo)并且動(dòng)作左下角的縱坐標(biāo)加動(dòng)作的高的值小于動(dòng)作空間左下角的縱坐標(biāo)加動(dòng)作空間的高的值，即動(dòng)作下豎穿動(dòng)作空間，如圖3（b）所示。剩下為動(dòng)作上豎穿動(dòng)作空間，如圖3（c）所示。endprint

2.5 動(dòng)作大于動(dòng)作空間

動(dòng)作大于動(dòng)作空間和動(dòng)作覆蓋動(dòng)作空間不同。動(dòng)作大于動(dòng)作空間說明，動(dòng)作空間的一部分被動(dòng)作覆蓋。而動(dòng)作覆蓋動(dòng)作空間，說明動(dòng)作空間全部被覆蓋。如若出現(xiàn)動(dòng)作大于動(dòng)作空間的情況，則當(dāng)前動(dòng)作空間改變，新動(dòng)作空間就是動(dòng)作未覆蓋的部分，把新動(dòng)作空間寫入動(dòng)作空間數(shù)組，完成動(dòng)作空間的更新操作。

2.6 多動(dòng)作與動(dòng)作空間重疊

在動(dòng)作更新中，還會(huì)存在多動(dòng)作與動(dòng)作空間重疊的情況。如若遇到該情況，原動(dòng)作空間改變，必生成1個(gè)新動(dòng)作空間。新生成的動(dòng)作空間是動(dòng)作未覆蓋部分中的最大虛擬矩形，把新動(dòng)作空間寫入動(dòng)作空間數(shù)組，完成動(dòng)作空間的更新操作。

3 結(jié)語(yǔ)

二維Packing問題一直是研究的熱點(diǎn)，其在切割、焊接等領(lǐng)域應(yīng)用廣泛，提高該問題解決效率，具有很強(qiáng)的實(shí)際價(jià)值。擬人型穴度算法開拓了新視野，使算法綜合性大大提升。其中，動(dòng)作空間的更新作為擬人型穴度算法的核心之一，在提高算法效率和精度上擁有很多可能，值得繼續(xù)深入研究。

參考文獻(xiàn)：

[1] 王磊，尹愛華.求解二維矩形Packing 問題的一種優(yōu)美度枚舉算法[J].中國(guó)科學(xué)：信息科學(xué)，2015，45（9）：1127-1140.

[2] LEI WANG，AIHUA YIN.A quasi-human algorithm for the two dimensional rectangular strip packing problem：in memory of Prof.Wenqi Huang[J].Journal of Combinatorial Optimization，2016，32（2）：416-444.

[3] 何琨，黃文奇，金燕.基于動(dòng)作空間求解二維矩形Packing問題的高效算法[J].軟件學(xué)報(bào)，2012，23（5）：1037-1044.

[4] 蔣興波，呂肖慶，劉成城.二維矩形條帶裝箱問題的底部左齊擇優(yōu)匹配算法[J].軟件學(xué)報(bào)，2009，20（6）：1528-1538.

[5] CUI Y D，YANG Y L，CHENG X，et al.A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem[J].Comput Oper Res，2008（2）：1281-1291.endprint