求解装箱问题的启发式算法研究

1、若是一块砖的长、宽、高可写成a ×ab ×abc(这里a、b、c都是正整数,则布鲁京称之为和谐(harmonic砖块。其中1 ×2 ×4的砖块(见图一又称为标准(canonical砖,因为它不但是满足和谐条件的最简单例子,而且又非常像砌墙用的实际砖头。布鲁京证明一批大小为a ×ab ×abc的和谐砖块能正好完全填满一个匣子的充分及必要条件,是匣子的大小必须呈(ax×(aby×(abcz形式,其中x、y、z 都是整数。布鲁京的结果可以推广到高维数的欧几里得空间,以及二维空间(即平面。在平面上,1 ×2的长方

2、形纸牌若可填满一个大的长方形,则此长方形最少有一边是偶数。现在回到布鲁京的小孩所面临的难题。由于6不能被4除尽,根据布鲁京定理,这个难题是不能解的;不过有没有简单的证明呢?让我们先看另一个比较简单的类似问题:把边长为8的正方形纸板斜对角上的两个方格子(面积各为1剪去后,能否用31块1 ×2的小纸牌填满呢?不能,证明如下:把原先纸板上的64个小方格涂以两种不同的颜色,使相邻两格颜色不同。由于剪去的两个格子颜色一样,剩下的纸板不可能用31个纸牌填满,因为每块小纸牌所填入的两格颜色不一样之故。利用类似的方法可以把六阶(指每边长为6立方体分为27个二阶小立方体,使任两个相邻的颜色都不同(见图

3、二。任一块标准砖所占有的8个格子必然是4黑4白,但大立方体中黑格子比白格子多8个,所以最多只能放入26块砖头。克拉纳(D. A. Klarner在1973年趣味数学期刊第六卷第二期发表一篇文章迭砖问题,引入可劈性(cleavability的观念。他证明若一个平面上的大长方形可以由若干个同样大小的小长方形所填满,则各种填法之中必有一种方法使得填好之后,可以把大长方形劈开分成两个长方形,而每一个正好可以用这些小长方形填满。不过在三维空间中没有可劈性,星马士特(D. Singmaster发现了一个最简单的反例:一个5 ×5 ×12 的匣子可以用1 ×3 ×4的

4、砖块来塞满,但不论如何塞法都不满足可劈性。另一问题是,对某一形状的砖块而言,非可劈的匣子种类是否无限多?答案是意外的否。克拉纳证明在任何级数比2大的欧氏空间中,对任一种砖而言,只有有限个匣子是可被它填满但却不可劈开。1971年,二位匈牙利数学家卡透纳(G.Katona及史沙兹(D.Szasz把克氏定理推广,他们得到一些数目上的上限(指匣子的数目。如果不限于用同一类的砖块,我们就可引入许多精彩的问题。其中最简单的是一个三阶立方体难题:我们想要用6块1 ×2 ×2的砖头及3块单位体积的小立方体来填满一个3 ×3 ×3的立方体(见图三。这个难题看起来容易,但解

5、起来相当困难。如不计旋转及镜像反映,解法只有一种:3个小立方体必须沿对角线排列(见图四。证明如下:考虑任何一个3 ×3截面,假定如图四所示涂以黑白二色,则得5格黑色4格白色(相邻两截面把黑白二色交换。不管一块1 ×2 ×2的砖头如何放法,在每一截面中它将占有02或4个格子,其中黑白二色的格子数相同。所以9个截面中,每一截面必须刚刚好有一个格子被一个单位体积的砖块所占有。而且每一截面中,这个单位砖必须放在正当中或者四角上。于是只有如图四所示的排法;剩下6块砖头排法很容易,不再详述。现在回到用同样的砖块来填满一个匣子的问题。我们可以问以下的问题:若一个匣子不能被一组(

6、同样大小砖块所完全填满,那么最多可以塞几个?这个问题非常困难。1974年,布劳迪和佛拉格(R. A. Brualdi, T. H. Foregger发表了一篇论文,把这个难题解决了一部分。假设R为匣子当中的一些格子的集合,如果不管一块砖怎样放,它总要占有R中的格子,则R称为代表组。在所有的代表组中如果以R的格子数为最少,就说R含有最小基数(cardinality。他们证明一个匣子所能塞入的砖块(不限于和谐砖的数目不能超过这个最小基数。平面上一长方形中能放入最多的和谐砖数正好等于最小基数。但三维及高次空间则不然。以标准砖及立方体为例,四阶立方体可以塞入标准砖,而且可以填满,六阶则以前证明过不可能

7、填满,最多可放26块。五阶立方体有125格,由于不能被8除尽,所以不可能以标准砖(每块8格填满。此时最小基数虽是15,但至多只能放入14块。布、佛二位有一个很麻烦的涂色证法,但加德纳想到一个巧妙的归谬证法:假设可以填入15块标准砖,其余用5个单位体积的小立方体填满,每个单位立方体在3个平行于表面的截面上,截面共有15个,而单位立方体只有5个,所以任一截面刚好含有1个单位立方体。这样五阶立方体6个表面的150格子就剩下150-6=144个,它们必须以标准砖的表面来占满。但每一块砖正好有一个1 ×2的侧面靠到大立方体的表面上,于是留下144-(15 ×2=114 个格子,要用1

8、 ×4及2 ×4二种长方形来填满,但114不能以4除尽,所以原假设不成立。加德纳又想到另一个证明如下:考虑立方体的三个与三面(互相垂直平行而且通过中心的截面。每一截面是一个5 ×5的方块,一共有75个格子。由于25是奇数,可知每一面必有一格与一个单位立方体相交。(有许多可能性,例如放一个单位立方体在整个立方体的正中央。每一块标准砖一定正好与这三个截面当中某一个有两格相交(与其他的面则可能不相交,亦可能与4或8格相交。15块标准砖又占去30格。75减去33所剩的格数42不可能被4除尽,所以无法塞入15块标准砖。接下来是七阶立方体。此立方体很容易塞入41块标准砖,但问

9、题在于可否放入42块标准砖,而以单位立方体填入余下的空间。一般的n阶立方体也有类似的问题,而答案是这样的:当以标准砖塞入n阶的立方匣中时,若n为4之倍数则必可塞满;若n为偶数但不能被4除尽,则有一块砖塞不进去。n为奇数时,每一截面有n ×n个格子,因此必然有一个洞(单位格子,所以不可能填塞满,而最多只可塞入(n3-n/8 块标准砖。问题是在什么情形下可以塞入这些砖块。安曼(R.Ammann证明当n为不等于16k±1的奇数时,不可能塞入最多数目即(n3-n/8的标准砖,而当n=16k±1时,的确可以塞入最多的砖头。英国的巴尼斯(F.Barnes得到更进一步的结果,即

10、n16k±1且为奇数时,立方匣必可被比最多的数目少一个的砖块所填满。在西洋棋盘(64格放骨牌(面积为2格的问题,以前证明过,若把两个斜对角上的格子去掉,则用涂色的方法可证明不能以31块骨牌填满,此问题可加推广如下:若以交错方式把棋盘涂以两种颜色,若把同色的二格去掉,则必不可能以31块骨牌填满。但若把异色的二格拿掉,是不是就一定可以填满呢?这问题要难多了。几年前,IBM的古莫里(R.Gomory想出一巧妙的证明:把整个棋盘分隔开来(见图五再取走异色的二格子A、B,则由其中一格A走到另一格B有两种相反的走法,每一条路正好有偶数个格子,因此必可被骨牌填满。另一个有趣的问题是如何证明不可能把一个每边有25个格子的方块,用2 ×2及3 ×3的小方块来填满。克拉纳有一个简单的证明(见图六:他把大方块以黑白两色一条条的交错涂色。一片2 ×2的小方块不管怎样放都必然遮盖2黑2白。但大方块中黑格子比白的多25个,所以我们必须想法子用3 ×