二维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