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

《都市摩天楼的最佳规划问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、“都市摩天楼”的最佳规划问题摘要游戏的研究，进行了多次改进，终于找到一个建造步骤较少建造楼房居住人口较多的建设方案。模型一主要是用了整体到局部的方法展开研究，在配合以从外到内的办法找到最优方案。至于模型二，是用的相反的方法在进行研究。但是步骤较多，变换方法很繁琐。相比较而言，模型一不仅所用步骤少，而且还简单明了。并且所求出来的模型具有对称美，观赏性很高，最后还对此模型进行了扩展。本文特色在于从两个方面对问题进行研究，最后找出最优解。1.问题重述“都市摩天楼”是诺基亚手机上的经典游戏。其简化规则可以这样描述：有一个城市，其土地可以表示一个5

2、×5方阵。游戏中共有四种楼房。蓝色楼房可以容纳100人，红色楼房能容纳400人，绿色楼房能容纳700人，黄色楼房能容纳1000人。但是若要在某个位置盖红色楼房，必须在位置周围（上，下，左，右，斜相邻不算）有蓝色楼房；同样，若要在某个位置盖绿色楼房，必须在位置周围有蓝色楼房和红色楼房；若要在某个位置盖黄色楼房，必须在位置周围有蓝色楼房，红色楼房和绿色楼房。游戏过程中，一次只能盖一栋楼房。另外需要注意的一点是：已建成的楼房可以被新楼房取代，只要新楼房满足“相邻”条件。试一个建造方案，使城市容纳的人口最多。2.问题分析土地为5×5的方阵，可以看

3、成是一个5×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——盖黄色楼房个数Y——住房总

4、人口数蓝色楼房用“1”表示红色楼房用“2”表示绿色楼房用“3”表示黄色楼房用“4”表示Ys——矩阵各素总和5×5矩阵为A=[aij]5×51.模型建立模型一：（大化小及由外到内）把这个5×5矩阵分成四块，标号为A,B,C,D,如图所示：a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45a51a52a53a54a55a11a12a13a21a22a23a31a32a33a13a14a15a23a24a25a33a34a35A模块：a31a32a33a41a42a43a51

5、a52a53a33a34a35a43a44a45a53a54a55C模块：为了简化问题，要研究整个矩阵的问题可转化成研究四个模块的问题。要使总人口最多，只需要某一模块的总人口数最多，也就是要个元素的和最大。首先来看模块A:a11a12a13a21a22a23a31a32a33默认a11=a12=aij=1，在一个3×3阵里，既要满足题目条件，又要元素总和最大.当a11=1时，a12=1or2，a21=1or2；max（a11＋a12＋a21）=5当a11=2时，a12=1or2or3or4，a21=1or2or3or4；max（a11＋a

6、12＋a21）=10最后情况如图所示：244覆盖情况：1111211231432432432432432431111211211211211211314314321111111111111111211211211212434243234121214323424342Y=4×8＋3×6＋2×8＋1×3=69当a11=3时，a12=1or2or3or4，a21=1or2or3or4；max（a11＋a12＋a21）=11这种情况如图所示：3443而此时求得的各元素和应为最大14，在覆盖过程中这个小模块的数据变换跟其他模块是没有关系的，因此可以

7、对称到另外3个模块即B模块C模块D模块，则可达到整个矩阵各元素总和最大。整个矩阵各元素总和最大的推导过程：（由外到内）111111111111111111111111121212211122111221112212123121321112211122111231213342434111421112411143424334243411142212241114342433424343234221224323434243最后结果：3424343434241424343434243Y=4×12＋3×8＋2×4＋1×1=81当a11=4时，不能满足

8、题目要求。综合上述：a11=3为矩阵的各个元素之和的最大的情况。模型二：（由内及外，以1展开）3×3矩阵：a11a12a13a21a22a23a31a32a33把1234填入其中，1是234出