从仓储、集装箱货物堆放方案优化到计算机信息纠错机制

             ——从二维到三维里的最密堆积问题

一、背景

在这个物价极高的时代，对于城市中的仓储场所和运货集装箱来说, 如何最大限度地利用空间,提高空间的使用效率, 成为了一个迫切需要解决的问题。不同的堆积方式可能会有截然不同的结果，而最密堆积是一种非常有效的空间利用方式。那么，想必大家一定会有所疑问：如何最密堆积？使用最密堆积能节约多少空间?

二、文章简介

本文着重研究了二维和三维里的最密堆积问题，主要内容如下：

1.我们对二维空间中圆的最密堆积进行了研究

2.我们计算了六方最密堆积和面心立方堆积的空间利用率，将它与简单立方堆积的空间利用率作了比较，对当今的物流给出了自己的意见

核心知识点：三维空间密铺、简单立方堆积、六方最密堆积、面心立方堆积、晶胞、空间利用率

引言：

关于最密堆积，我们可以追溯至1611年开普勒写的一本科普小册子里：论六角形的雪花里在这本小册子里，开普勒讨论了沃尔特·雷利提出的一个问题：怎么堆放加农炮弹最有效率？

    开普勒给出了他的猜想：六方最密堆积和面心立方堆积是球形在三维空间中的最佳摆法。

    那么我们的研究也将从较简单的二维开始。

1、二维最密堆积

开普勒认为：在二维空间中，将球面逐一摆放后，会发现当球面与周围的六个球面相切时，它的空间利用率最高。

设圆的半径为r，则正六边形的边长为2r，不难运算该正六边形的面积为6r2该正六边型内包含3个完整的球（把残缺的球进行拼接），那么球的总面积为3πr2        

所以密度为≈91%

（图1）

   以上是特殊情况，但在现实中往往会受到诸多限制。为了模拟不理想的条件，假设有一个10×10cm的正方形，需要用直径为1cm的球去填充(如图2)。那么仅用上图的堆积方式就能达到最大的密度了吗？

（图2）

（图3）

如图3所示，设点A、B、C为圆心，☉A、☉B、☉C分别相切于点D、E、F，设圆的半径r=0.5cm，所以CD的长度为cm，由此可知，这种堆积方式可以使每一层圆所占的直径减少约0.1339cm（1-  ），那么正方形内可以容纳11排小球，也就是105个小球，那么它的密度就是（105×0.5×0.5×π）÷100≈82%。

2、三维最密堆积

在探究三维空间的最密堆积前我们先插入一个寓言故事——乌鸦喝水。口渴的乌鸦把石头扔到瓶子里，水面上升，最终乌鸦喝到了水。

    我们以这个寓言故事为例，找了几个不同的瓶子放一点水，向里面丢石子，结果水面只上升了一些就停下来了，乌鸦根本喝不到水。那寓言故事里的乌鸦是怎么喝到水的？

    经过探究，我们认为乌鸦喝不到水的原因在于石子和石子之间有很多空隙，水位升高的时候会先填满这些空隙，很难升到瓶口。如果能让石子的堆积变密，那么水面就会升的更高，这样是不是就能喝到水了？

如果石子是规整的立方体，那就好办了。只要石子之间没有缝隙，再少的水也能升到瓶口。这种摆放方法叫做三维空间密铺（如图4）。六面体的三维空间密铺可以利用与于仓储场所和集装箱的纸箱摆放。三维空间密铺其实还有很多种形式，这里不一一细讲。

（图4）

但自然界中几乎找不到这样规整的石子，不现实。我们把石子理想化为大小相同的球体，再来审视这个问题。

上文提到开普勒猜想六方最密堆积和面心立方堆积是三维空间中的最佳摆法。球体需要在三维空间中进行摆放，要直接解决这个问题比较困难，逐一摆放后，会发现当球面与周围的六个球面相切时，它的空间利用率最高。

面心最密堆积（图5）

六方最密堆积（图6）

六方最密堆积和面心最密堆积空间利用率很接近，在此我们先只研究六方最密堆积。想要计算出六方最密堆积的空间利用率，我们就需要计算出六方晶胞的密度，计算过程如下：

设晶胞长、宽、高分别为a,b,h，每个原子半径为r。 由图7得，晶胞长、宽都为原子核间距，即a=b=2r。

（图7）

以刚才第二幅图为例，中间层原子与底层原子原子核的连线构成正四面体（点O,A,B,C），且晶胞的高为正四面体高的2倍。底层原子的原子核连线围成菱形（四边形ABCD），且∠ABC=60°，△ABC为正三角形。现在单独看正四面体OABC。

    （如图8）

如图，BM⊥AC，ON为正四面体OABC的高。

BM=AB×sin∠BAC=2r×sin60°=r ,又BN=BM=r

在Rt△BNO中，由勾股定理得，BN²+ON²=OB²

                    （ r )² +(ON)² =(2r)²

∴ON=r为正四面体的高 

∴晶胞的高 h=2ON= r 

由图10可知，六方晶胞为平行六面体，所以晶胞体积=晶胞底面积×高。

晶胞底面为菱形（菱形ABCD），菱形ABCD的面积又为正三角形ABC面积的2倍。所以S菱形ABCD=S△ABC=2r²。

∵晶胞的高为正四面体OABC高的2倍

∴晶胞的高为r 

则V晶胞=Sh=2r²×r =8r³

算完晶胞的体积，

再算晶胞中所含有原子的体积。

我们通常将原子看作球体，

因此原子体积为 V原子=πr³

（图9）

由图9并计算得，一个六方晶胞中含有两个原子，所以原子的总体积πr³

原子的空间利用率= 晶胞中所含原子的体积÷晶胞的体积×100% 

所以六方最密堆积的空间利用率为（πr³）÷（8r³）≈74%

综上所述，只有当水的体积占瓶子体积的26%时乌鸦才有可能喝到水。

3、三维最密堆积应用

跳出乌鸦喝水问题，谈到实际，当运送或储存物品时用六方最密堆积（如苹果橙子等水果，一些类似球体的零件、玩具等），是不是能节省很多空间呢？

    我们做了一个模型如下（如图10所示）

，在60cm×50cm×30cm的立方体（模拟纸箱）内，按照六方最密堆积的堆积方式放置半径均为8cm的小球（模拟球状物体）。经计算，共可摆下2452个小球。

我们将六方最密堆积与简单立方堆积比较前，先需计算出它的空间利用率，计算方式如下：由图11可知，在简单立方堆积的晶胞中，八个原子都处于顶点，所以在这个晶胞中均摊得到1个原子。

设原子半径为r,则这个晶胞的边长为2r（如图12）

那么它的空间利用率就是：[（4÷3）∏r2]÷（2r）3=∏÷6=52.36%

如果按照这种普通堆积方式，在60cm×50cm×30cm的立方体内，放置半径均为8cm的小球（与图10建模的数据相等）。经计算，共可摆下1872个小球。

（图13）

四、总结：堆积在现实生活中的实际应用

比较上面两个建模（图9和图12），可发现：堆积小球的方式不同，能堆下的小球数量相差甚远。而通过计算我们可以得出，简单立方堆积和六方最密堆积的空间利用率相差了近20%，所以，我们建议：在储存球状物体，例如苹果、橙子、梨（在水果外面可套上防撞绵，如图14）、球形玩具等，可利用六方最密堆积的堆积方式节省空间，从而极大地节省成本。

（图14）

为了实现六方最密堆积下小球总数计算的自动化，我们编写了Python程序。

五、实际操作中遇到的问题：

我们发现在20cm×15cm×25cm的箱子中填充直径为5cm的小球，得到的结果却是六方最密堆积比简单立方堆积少放了1个球，这与先前的理论相违背。经过反思，我们得出，六方最密堆积的空间利用率是在无限的空间内进行计算的，我们堆放的货物也不可能被分割。所以只有当空间足够大，或堆放的球形货物半径足够小时，才能充分发挥出六方最密堆积的优势。

对此，我们尝试将六方最密堆积和简单立方堆积结合起来，会不会有更密的情况？我们再从二维最密堆积看起：

前文提到在10cm×10cm中的正方形内填充直径为1cm的小球，经计算得的空间利用率为82%，这和最理想情况密度（91%）差了约9%。所以我们猜想这还不算是最理想的堆积情况，我们通过计算发现堆积完成之后仍余下了约0.1339cm

（图15）

（图16）

那么我们就可以将其中一层放九个球的改成放十个球的，最多就可以放106个球。

所以10×10cm的正方形里最多能放106个直径为1cm的小球，它的密度是（106×0.5²π）÷100=83.21%。

此时是最理想的状态。

（图17）                                             

在箱子里如果全部使用六方最密堆积的堆积方式，那么最外边与箱子还有一定的空隙，因此我们尝试使用和二维最密堆积相同的做法，将第一、三层的其中一列多摆一个球，如图所示，那么空间利用率将更高。

(图18)

综上所述，我们对当今物流行业给出一下意见：如果使用90cm×90cm×90cm的的塑料箱子，分别按填充直径约为8cm的苹果，六方最密堆积可以填充1512个，简单立方堆积可以填充1331个。按世界苹果产量为8000吨来算，每用六方最密堆积代替简单立方堆积就可以节约约181个苹果的空间，每8个用六方最密堆积代替简单立方堆积的箱子就可以节省1个塑料箱。按全球苹果产量为8157.80万吨，平均每个苹果200g，且箱子都是聚乙烯塑料箱（密度为0.93g/cm）计算，如果全部用六方最密堆积代替简单立方堆积，每年可以节省200万吨石油，按国际石油价格来算，折合人民币6.72亿。

六、计算机信息纠错机制——汉明码

当然，六方最密堆积不止能利用于仓储场所和运货集装箱。还有一个应用领域是信息传输中的纠错码。如果一种信息由三个变量组成，那我们可以把这种信息看作三维空间中的一个个小球。我们希望传送这种信息的时候尽量密度大点，但是我们不能让信息之间靠太近，信息互相之间有重叠我们可能就无法区分信息。这个最密填充就能告诉我们信息传输的最大密度是多少，如果有误差该如何纠错。

编程程序代码与运行结果如下图所示：

（图19）

（图20）

汉明码——“最密堆积”？

我们将汉明码可视化后发现，纠错码的设计并不能看成是一个球的堆积问题，因为汉明码是在汉明空间内进行讨论的，它不同于欧几里得空间。比如001到100的最短距离不是，√2，而是2，所以在这个空间里面不存在体积的概念，自然也就没有最密堆积的概念。所以我们得出结论，我们猜测的纠错码与最密堆积有关是错的。（图21）

结语：

因此,在今后的建筑和仓储设计中,应加强对最密堆积空间利用率的研究和应用,以推动空间利用的创新和提升。只有充分发挥最密堆积空间利用率的优势,才能更好地满足人们对空间的需求,实现可持续发展的目标。

参考资料：

学术期刊库 六方最密堆积晶胞密度和原子空间利用率的计算 

哔哩哔哩 毕导THU 科学打假！乌鸦喝水的寓言竟然骗了我们这么多年！

知乎 Alepha E 信息与编码系列（六）错误纠正码——校验码、纠正码的结构及Hadamard矩阵（编码）

微信公众号 墨奇博客 北京大数据研究院BIBDR 生物特征密码系统之错误纠正码简介——汉明码