智慧金字塔的数学模型与求解

作者: 风之骑士_4926 | 来源:发表于2017-10-15 15:25 被阅读231次

高一的时候看到同学玩智慧金字塔，深感有趣，于是我也买了一套在家里慢慢玩。在高二的暑假我把第5册第11阶段的题目都做出来了，然后试试第12阶段的题目，发现那根本就不是人玩的。。。他喵的，已知两块甚至更少的积木然后让你拼出5层的金字塔，要尝试的可能性实在是太多了；就算你直觉敏锐能看出些端倪，但这些残忍的题目还是完全能够将一个强迫症患者折磨至死。（根据我的受虐体会，智慧金字塔题目的难度到达一定程度之后，需要的更多是逻辑推理而不是空间想象。）

A~L编号共12块积木

其中一种拼法

残忍的题目

后来呢，学了些简单的模型和算法，视野宽了点，返过来又思考智慧金字塔。也知道了其实智慧金字塔的玩法就是所谓的“精确覆盖问题”，我感觉应该有希望用“0-1规划”的数学模型求解。于是我用简化了的情形在LINGO上求解一下，发现可行。现在分享一下这个思路。。。

考虑的简化情形是：只用如下的F和K编号的积木，

而需要填充的形状为

对每个空位作了编号

对于这种简单的情形，一眼便能看出答案一定是

但如果要用数学方法借助计算机求解，则需要将其表达形式抽象化，也就是

F：①④⑤

K：②③⑥⑦

进而用7维向量表示如下

F1：（1，0，0，1，1，0，0）

K1：（0，1，1，0，0，1，1）

显然，F1+K1=（1，1，1，1，1，1，1），等式右边全为1表示将这7个空位不多不少地“精确覆盖”了。

另外，注意到，K积木只有一种可能的摆法，也就是K1：②③⑥⑦，向量形式为K1：（0，1，1，0，0，1，1）；F积木一共有6种可能的摆法，分别为

F1：①④⑤ F1：（1，0，0，1，1，0，0）

F2：③⑥⑦ F2：（0，0，1，0，0，1，1）

F3：②⑥⑦ F3：（0，1，0，0，0，1，1）

F4：②③⑦ F4：（0，1，1，0，0，0，1）

F5：②③⑥ F5：（0，1，1，0，0，1，0）

F6：②⑤⑥ F6：（0，1，0，0，1，1，0）

为了描述问题，我们对以上7个向量各赋予一个系数，分别为k1、f1、f2、f3、f4、f5、f6，然后作出3个约束条件：

k1 · K1+ f1 · F1 + f2 · F2 + f3 · F3 + f4 · F4 + f5 · F5 + f6 · F6 = （1，1，1，1，1，1，1） ——（“精确覆盖”）；

k1、f1、f2、f3、f4、f5、f6均为“0-1变量” ——（值为0表示不接受该积木的该种摆法，值为1则表示接受）；

k1 = 1 ， f1 + f2 + f3 + f4 + f5 + f6 = 1 ——（对每个积木，选择一种摆法）；

以上便是描述这个简化情形的数学模型，事实上这并不是“0-1规划”，而是“0-1变量方程组”而已。如果将这个模型推广为5层金字塔的情形，用来求解第12阶段的金字塔题目，那么就不是这里的7个7维向量那么简单了，而是数百上千个55维向量，所以求解模型的计算量就很大了，有必要借助LINGO这个解方程的“神器”，但前提是要将模型转化为LINGO语言。

于是我用MATLAB建立了一个GUI文件，可以生成题目相应的LINGO代码，经LINGO求解得到结果后可以再用MATLAB画出三维图，操作及效果如下（以第477题为例）：

第一步：在格子中选择A~L的字母，也可以为空，表示题目。