胡文蓓+饒昊

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

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

DOIDOI：10.11907/rjdk.171602

中圖分類號：TP302.7

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

0 引言

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

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

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

1 基本算法B0

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

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

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

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

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

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

2 動作空間更新

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

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

2.1 動作把動作空間覆蓋

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

2.2 動作空間把動作包住

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

2.3 動作橫穿動作空間

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

2.4 動作豎穿動作空間

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

2.5 動作大于動作空間

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

2.6 多動作與動作空間重疊

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

3 結(jié)語

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

參考文獻(xiàn)：

[1] 王磊，尹愛華.求解二維矩形Packing 問題的一種優(yōu)美度枚舉算法[J].中國科學(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] 何琨，黃文奇，金燕.基于動作空間求解二維矩形Packing問題的高效算法[J].軟件學(xué)報，2012，23（5）：1037-1044.

[4] 蔣興波，呂肖慶，劉成城.二維矩形條帶裝箱問題的底部左齊擇優(yōu)匹配算法[J].軟件學(xué)報，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