急求矩形件排样程序实现

jiangze2008

矩形件排样程序实现（要求：只能由一个学生独立完成，不得抄袭）

工业上经常需要在一块大板材上下料得到若干个小的矩形件，使得板材的利用率最高，即所剩余的边角料最少。例如在一块宽40、高15的矩形板材上，排列25块尺寸已知的小矩形，25块小矩形的尺寸如表1，板材的利用率达100%，如图1所示。

file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-14128.png

图1 一种排样方案

表1 小矩形的尺寸

序号	宽	高
1	12	6
2	4	7
3	6	7
4	10	2
5	2	5
6	6	4
7	4	2
8	4	6
9	7	9
10	4	5
11	6	4
12	4	6
13	6	3
14	4	5
15	2	4
16	8	4
17	8	6
18	8	3
19	6	3
20	2	6
21	8	2
22	3	5
23	2	5
24	3	4
25	2	4

如果上述排样方案未知，即不知道图1的排法，那么如何将这25块小矩形按照某种次序排在一个大的板材上呢？目前这仍是一个世界难题。

通常要求在一个排样图中，任何一个矩形件在不超出板材边界的情况下，按照一个排样方案（给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案（解）file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-19663.png，其中file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-22856.png，file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-5836.png，pi为矩形件的序号，r
7 {% t1 Y( E2 K/ {6 x1 Li为排样方式，r
* U5 n7 ^' U# }i=1表示将矩形件旋转90°,
  j0 H% Y+ K5 Er
i=0表示矩形件不旋转。将第i个矩形件安排在板材上的过程中，均不能再往下、往左移动，则称其满足BL条件（bottom-left-condition，BL-condition）。

基于BL条件，有一种下台阶算法，具体步骤如下：

(1) 将零件file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-5288.png排放在板材的左下角，若file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-6738.png则将其旋转90°后再排放，求出排放后所占板材的最大高度；

(2) 将file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-25672.pngfile:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-11128.png根据其排样方式置于板材右边最大高度处，向下向左移动file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-1248.png，且向下移动优先（即原本已无法再向下移动，故开始向左移动，而在向左移动的过程中若发现又能继续向下移动，则先向下移动），直至file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-20777.png无法向下向左移动为止（即接触到其他零件或板材边界），并求出此时的最大高度；

(3) 重复上述过程，直至所有零件排放完毕，最后所得最大高度即为所需板材高度。

其排样过程如图2所示，就好象下台阶一样，于是形象地称之为下台阶算法。

file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-29311.png

图2  下台阶算法的排样过程

剩余矩形排样法是目前所提出的一种有效的排样算法，该方法记录了所有可利用的空间，更能合理地分配给待排样的矩形件，提高了每个排样方案的板材利用率，更接近最优排样方案。例如对于同一个矩形件序列file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-3294.png进行排样，图3(a)中下方的空洞以往的排样算法都无法利用，矩形4只能被排到上方。而利用剩余矩形排样法可以很好的解决这个问题，它可以使矩形4充分利用下方的空间，如图3(b)。

file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-20428.png

图3  剩余矩形排样法的优越性

剩余矩形排样算法用一个矩形数据集合来表示板材目前的剩余位置情况，任何未被排样的空间（包括孤立的缝隙），都在剩余矩形集合中表示，不会遗漏任何一个。而在每一个矩形件被排入前，都需根据这个剩余矩形集合中的数据来选择最为合理的位置进行排放。下面给出剩余矩形的具体形成方法（这里用矩形的左下角坐标和右上角坐标来确定这个矩形的的位置）：

(1) 板材的左下角和右上角坐标分别为file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-26959.png，于是开始时剩余矩形数据集中只有一个矩形为file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-27790.png。

(2) 当排入一个矩形件file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-20334.png（宽file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-3366.png高file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-23654.png）后，需将剩余矩形数据集合中的每一个矩形都减掉此矩形件所占的位置。若此矩形件的左下角坐标为file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-25374.png，且为横排（即矩形件不旋转90°），则每个剩余矩形都减掉与矩形件file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-2172.png相交的部分。例如矩形file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-26371.png减掉与矩形件file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-11772.png相交的部分后，形成了四个新的剩余矩形为：

file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-1559.png
+ [+ T' o8 J3 q6 qfile:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-14496.png

按顺时针方向记录矩形。如图4所示。若为竖排（即矩形件旋转90°），计算方法类似。

file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-27305.png

# h: ^; x" s' [9 t& c

  j' S: |: ^) x  H

  S  r, ]# F# T+ o% r1 m

! a$ t- E/ e: T% a3 }

" t! ~$ k4 z- R- ^

9 d/ U+ B( F) D2 V

) O/ ]6 ]- Y/ j2 Z% x

% o% }5 z* P+ C

3 g* t- T2 u' F" ?6 |4 F

                     图4  剩余矩形表示法

依此类推，将矩形数据集中的所有剩余矩形都作如此操作，减去所排入矩形件file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-18702.png所占位置，形成新的剩余矩形。

(3) 由于新的剩余矩形的产生，又将引起原矩形数据集的改变，因此对其进行整理：去掉面积为零的或已无法排下所剩的任何一个矩形件的剩余矩形；把具有完全包含关系的剩余矩形中面积小的矩形去除、有相交关系的矩形全部保留。得到新的剩余矩形集，为下一次排放使用。

用剩余矩形表示法可记录每个可形成最大矩形的空间，用于排样。将这种表示法与BL排样算法结合，就形成了剩余矩形排样算法，对于给定的一个排样方案file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-7186.png，其中file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-13661.png，file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-23460.png，具体排样过程如下：

(1) 开始时剩余矩形集file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-22218.png中仅有一个矩形，即板材本身file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-3602.png。

(2) 从排列file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-22016.png中取出第一个需排的矩形件file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-15639.png（宽file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-29337.png，高file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-23406.png），将file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-26571.png根据相应排放方式 file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-1361.png排放在板材的左下角，用上面所述的剩余矩形表示法计算新的板材剩余矩形集file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-24413.png：

若file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-2578.png（横排），则file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-14132.png，file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-30412.png，如图5；

若file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-7952.png（竖排），则file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-29899.png，file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-15602.png。

file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-10665.png

图5   剩余矩形排样过程

(3) 依此类推，按顺序逐一排放file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-28784.png，直至所有矩形排放完毕。每放入一矩形件，都需根据剩余矩形集确定其排放位置，即在剩余矩形集中选择宽高均大于等于此矩形件的底部最低的最靠左的剩余矩形（先靠下后靠左），让矩形件与剩余矩形的左下角重叠。同时放入矩形后要对剩余矩形集进行整理更新。

同样，剩余矩形排样算法也满足BL条件。

我们的问题叙述如下：

现在有宽为15、高为充分大的板材(即板材的高度没有限制)，将表1中的25块矩形安排到板材上有下列3种排样方案：

(1)P=(4,2,1,3,6,5,7,9,8,10,11,12,14,13,19,15,18,17,20,16,21,22,24,23,25);

R=(1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);

具体排样图见图6.

(2)P=(10,5,1,13,23,24,22,8,14,4,7,25,11,19,6,2,16,20,18,9,17,3,12,15,21);

   R=( 0,1,1, 1, 0, 1, 1,0, 1,1,1, 0, 0, 1,1,1, 0, 1, 0,0, 0,1, 1, 0, 0);

具体排样图见图7.

(3) P=(23,21,20,16,17,2,24,25,9,3,5,8,22,14,15,18,7,6,10,19,4,12,11,13,1);

R=( 0, 0, 1, 0, 1,1, 0, 0,0,1,0,1, 0, 0, 0, 1,0,1, 1, 0,1, 0, 1, 0,0);

具体排样图未给出，由参赛同学编制相应程序绘制。

现在的问题是，请学生根据剩余矩形排样算法编制一个通用的程序仿照图6、图7绘制上述3种排样方案的图形（由程序自动绘制，不是手工绘制）。使用语言不限，最后成果需提交程序清单、程序使用说明以及由程序绘制的三张排样图。

file:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-8201.pngfile:///C:/DOCUME~1/Jk/LOCALS~1/Temp/ksohtml/wps_clip_image-17760.png

- [  t; X4 a; m% }2 a

- b. N4 w1 D; m. i* v2 _& f

8 x# G, x; R8 U) U2 b

; Z$ _. K; a: w" d/ }

0 l5 _. O+ k7 c  j

2 u: k2 I6 {& i: r* m4 L$ P- }

& U7 R$ k, n6 y% ?

( \; J  v) |: j, B! ]- a8 L0 F

图6 问题(1)的排样图      图7 问题(2)的排样图

& \- \" p; l+ i& d) f0 ?