都市摩天楼最佳规划问题x:

“都市摩天楼”的最佳规划问题

摘要

游戏的研究，进行了多次改进，终于找到一个建造步骤较少建造楼房居住 人口较多的建设方案。

模型一主要是用了整体到局部的方法展开研究， 在配合以从外到内的办法 找到最优方案。

至于模型二，是用的相反的方法在进行研究。但是步骤较多，变换方法很 繁琐。

相比较而言，模型一不仅所用步骤少，而且还简单明了。并且所求出来的 模型具有对称美，观赏性很高，最后还对此模型进行了扩展。

本文特色在于从两个方面对问题进行研究，最后找出最优解。

1. 问题重述

“都市摩天楼”是诺基亚手机上的经典游戏。其简化规则可以这样描述：有 一个城市，其土地可以表示一个 5X 5方阵。

游戏中共有四种楼房。

　蓝色楼房可以容纳 100人，红色楼房能容纳 400 人， 绿色楼房能容纳 700 人，黄色楼房能容纳 1000 人。但是若要在某个位置盖红色 楼房，必须在位置周围（上，下，左，右，斜相邻不算）有蓝色楼房；同样， 若要在某个位置盖绿色楼房，必须在位置周围有蓝色楼房和红色楼房；若要在 某个位置盖黄色楼房，必须在位置周围有蓝色楼房，红色楼房和绿色楼房。

游戏过程中，一次只能盖一栋楼房。另外需要注意的一点是：已建成的楼 房可以被新楼房取代，只要新楼房满足“相邻”条件。

试一个建造方案，使城市容纳的人口最多。

2. 问题分析

土地为5X 5的方阵，可以看成是一个5X 5的矩阵。

蓝，红，绿，黄这四种楼房能容纳的人数分别是 100， 400， 700， 1000 是 公差为三的等差数列，并且 1， 2， 3， 4 也为等差数列，因此可以用 1， 2， 3， 4 来代表蓝，红，绿，黄这四种楼房。那么，问题可以看成是把 1234这四个数按 照一定的规则 （2 的周围位置有 1；3 的周围位置有 1， 2；4 的周围位置有 1， 2， 3）填入矩阵，使得整个矩阵的各个元素之和最大。

3. 模型假设

假设楼房可以拆建多次，但是却不影响所能容纳的人口数。

4. 符号说明

X1——盖蓝色楼房个数 X2 ――盖红色楼房个数

X3 ――盖绿色楼房个数 X4 ――盖黄色楼房个数 丫 一一住房总人口数 蓝色楼房用“ 1”表示 红色楼房用“ 2”表示 绿色楼房用“ 3”表示 黄色楼房用“ 4”表示 丫 s 矩阵各素总和

5X 5矩阵为A=[a ij ] 5X5

模型建立

模型一：（大化小及由外到内）

把这个5X 5矩阵分成四块，标号为A,B,C,D,如图所示:

B模块

B模块

aii

ai2

Sl3

ai4

3i5

a21

a22

耳3

a24

325

a3i

a32

333

334

335

囱1

342

印3

a44

345

a5i

a52

353

354

355

C模块:a31

C模块:

a31

a32

a33

a41

a42

a43

a51

a52

a53

033

a34

a35

943

a44

°45

a53

a54

a55

D模块

为了简化问题，要研究整个矩阵的问题可转化成研究四个模块的问 题。要使总人口最多，只需要某一模块的总人口数最多， 也就是要个元素 的和最大。

首先来看模块A：

an

a12

a13

a21

a22

a23

a31

332

a33

默认aii=ai2=aij =1，在一个3X3阵里，既要满足题目条件，又要元 素总和最大.

当 aii=1 时，ai2=1or 2，a2i=1or2;

max (a“ + a〔2 + a21) =5

当 an=2 时，a12=1or 2 or3or4，a21=1or2or3or4;

max (a“ + a12 + a21) =10

最后情况如图所示：

2

4

4

111

121

123

143

243

243

243

243

111

121

121

121

121

121

131

431

111

111

111

111

111

121

121

121

覆盖情况:

243

432

121

2

4

3

4

2

4

3

2

3

4

1

2

1

2

1

4

3

2

3

4

2

4

3

4

2

Y=4X8 + 3X6+ 2X8 + 1X 3=69

当 an=3 时，ai2=1or 2or3or4, a2i=1or2 or3or4;

max (aii + ai2 + a2i) =11

这种情况如图所示:

3

4

4

3

而此时求得的各元素和应为最大 14，在覆盖过程中这个小模块的数 据变换跟其他模块是没有关系的，因此可以对称到另外 3个模块即B模

块C模块D模块，则可达到整个矩阵各元素总和最大。

整个矩阵各元素总和最大的推导过程：（由外到内）

1111111

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

3

1

2

1

3

2

1

1

1

2

2

1

1

1

2

2

1

1

1

2

3

1

2

1

3

3

4

2

4

3

4

1

1

1

4

2

2

1

2

2

4

1

1

1

4

3

4

2

4

3

最后结果:

3

4

2

4

3

4

3

2

3

4

2

2

1

2

2

4

3

2

3

4

3

4

2

4

3

3

4

2

4

3

4

3

4

3

4

2

4

1

4

2

4

3

4

3

4

3

4

2

4

3

Y=4X 12 + 3X 8+2X4 + 1 X 1=81

当an=4时，不能满足题目要求。

综合上述：

aii=3为矩阵的各个元素之和的最大的情况

模型二：（由内及外，以1展开）

3X 3矩阵：

an

a12

a13

a21

a22

a23

a31

a32

a33

把1234填入其中，1是234出现的基础，那么一定会有1,但 是要做到总和很大，那么，1的个数应该是越少越好，因此很显然会 把1放在对角线相交处，即a22 =1。

3

4

2

4

1

4

2

4

3

类似的5X5矩阵:

aii

ai2

a13

ai4

ai5

a2i

a22

a23

a24

a25

a3i

a32

a33

a34

a35

a4i

a42

a43

a44

a45

a5i

a52

a53

a54

a55

1

1

1

1

1

1

3

4

2

1

1

4

1

4

1

1

2

4

3

1

1

1

1

1

1

1

1

1

1

1

1

3

4

2

1

1

4

1

4|

1

1

2

4

3

1

1

1

1

1

1

导出

3

1

1

1

3

2

3

4

2

2

1

4

1

4

1

2

2

4

3

2

3

1

1

1

3

3

1

1

1

3

2

2

4

2

2

1

4

1

4

1

2

2

4

2

2

3

1

1

1

3

i[l

3

4

1

4

3

4

2

4

2

4

1

4

1

4

1

4

2

4

2

4

3

4

1

4

3

3

4

1

4

3

4

2

1

2

4

1

1

1

1

1

4

2

1

2

4

3

4

1

4

3

曰ill

3

4

2

4

3

4

2

1

2

4

2

2

1

2

2

4

2

1

2

4

3

4

2

4

3

3

4

2

4

3

4

3

1

3

4

2

2

1

2

2

4

3

1

3

4

3

4

2

4

3

导出

3

4

2

4

3

4

3

4

3

4

2

4

1

4

2

4

3

4

3

4

3

4

2

4

3

模型求解

用两种模型所求出的结果是相同的，均为:

3

4

2

4

3

4

3

4

3

4

2

4

1

4

2

4

3

4

3

4

3

4

2

4

3

该表格所对应的实际游戏盖房图应为:

■

■

1

■ !

■

1

■

Y =12X 1000+ 8X 700 + 4X 400 + 1 X 100=19300

模型优缺点

所建造房屋居住人口最多。最优解证明过程:

用复杂问题

简单化原则。即将矩阵分成几块小模型来分析，并采用自上而下，从左 到右，由外而内的原则。

通过对建房规则的分析，4不能出现在 图中红色区域且每个“田”字格最多只能出现 2个4.为了使矩阵中丫最大，只有使任何两个

“田”字格中都有两个4?要使任何两个“田” 字格中都有两个4，4只有出现在如图所示的 位置。

为了使A中丫最大，A中aii最大只 能为3,同理为了使B,C,D中丫最大， ai5 ， asi，和 aii最大也只能为3.如图所示。

又因为1是2, 3, 4生成的基础，所以矩阵中必须有1。而且1在最后 的布局中越少越好，当然最理想的情况是只有1个1。要让1的利用率最大，而 如果把矩阵的第三行当作横坐标，第三列当作纵坐标的话，上图中的数字刚好

3

4

2

4

3

4

3

4

1 3

4

2

4

1

4

2

4

3

4

3

4

3

4

2

4

3

2,又 根是对的，因而把1建在矩阵的中心。而同样要有 据对称把其他的地方建为2

2,又 根

1

1

1

1

1

1 \

1

1

11

1

1

1

1

1

1

1 1

1

1

P

1

1

1

1

1

1

现在验证A中能否建如图所示的摩天楼 第一步：全部建立1， 共建了 25次

第二步：在如图所示的位置 推掉1建立2,共建了 8次

1

1

2

2

1

2

丄

1

1

I 1

2

1

1

1

2

1

1

1

2

1

2

2

1

1

第三步：推掉原来的1建

立满足条件的3共

建了 4次

3

1

2

2

3 1

2

1 1

1

1

1 1

2

1

1

1

2

1

1 1

1

1

2 1

3

2

2

1

3 1

第四步：推掉原来的1或2建立满足条

件的4共建了 8次

第五步：推掉原来的1建立满足条件的

第五步：推掉原来的1建立满足条件的2,共建了 2次如图

3

4

2

\4

3

4

1：

1

1 1

4

2

1

1

1

2

4

1

1

1

4

3

4

2

4

3

3

4

2

4

3

4

3

4

3

4

2

4

1

4

2

4

3

4

3

4

3

4

2

4

3

经过验证，完全可以建立这样的摩天楼，根据上面的分析，这样的部局

将使摩天容纳的人最多

模型扩展

模型一相对于模型 只看矩阵的四分之一。至于模型的扩展， 矩阵。

模型一相对于模型 只看矩阵的四分之一。

至于模型的扩展， 矩阵。

推出结果为：

可以把模型一扩展到7X 7矩阵，9X 9矩阵，…2n-1 x 2n-1

3

4

2

4

2

4

3

4

3

4

2

4

3

4

2

4

3

4

3

4

2

4

2

4

1

4

2

4

2

4

3

4

3

4

2

4

3

4

2

4

3

4

3

4

2

4

2

4

3

建议

10.参考文献

相关热词搜索： 规划 摩天楼 规划 都市 都市摩天楼最佳规划问题x