二維Packing問題擬人型算法中的動作空間更新過程求解

胡文蓓+饒昊

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

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

DOIDOI：10.11907/rjdk.171602

中圖分類號：TP302.7

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0019-02

0 引言

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

自1971年提出二維矩形Packing問題以來，此問題一直都是數學和計算機科學領域中未被解決的重大問題之一，中外學者一直在進行著大量的研究。近幾十年來，國內外學者提出了多種高效近似算法，可分為非隨機型和隨機型近似算法。非隨機型近似算法中提出選擇放置動作的優先序，并在其基礎上進行適當的枚舉[2]，包括底部左齊擇優匹配算法[4]、分支限界[5]、擬人算法[3]。

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

1 基本算法B0

相關算法定義如下：

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

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

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

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

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

2 動作空間更新

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

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

2.1 動作把動作空間覆蓋

滿足以下4個條件：①動作左下角頂點的橫坐標的值小于或等于動作空間左下角頂點的橫坐標的值；②動作左下角頂點的橫坐標加動作的寬的值大于或等于動作空間左下角頂點的橫坐標加上動作空間的寬的值；③動作左下角頂點的縱坐標的值小于或等于動作空間左下角頂點的縱坐標的值；④動作左下角頂點的縱坐標加動作的高的值大于或等于動作空間左下角頂點的縱坐標加上動作空間的高的值。滿足了這些條件，即是動作把動作空間覆蓋。如若出現動作把動作空間覆蓋的情況，又因為動作是放在動作空間里，則說明存在其它動作空間一定包裹了此動作，所以刪除此動作空間，循環下一個動作空間。

2.2 動作空間把動作包住

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

2.3 動作橫穿動作空間

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

2.4 動作豎穿動作空間

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

2.5 動作大于動作空間

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

2.6 多動作與動作空間重疊

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

3 結語

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

參考文獻：

[1] 王磊，尹愛華.求解二維矩形Packing 問題的一種優美度枚舉算法[J].中國科學：信息科學，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].軟件學報，2012，23（5）：1037-1044.

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