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

“都市摩天楼”的最佳规划问题摘要 游戏的研究，进行了多次改进，终于找到一个建造步骤较少建造楼房居住人口较多的建设方案。模型一主要是用了整体到局部的方法展开研究，在配合以从外到内的办法找到最优方案。至于模型二，是用的相反的方法在进行研究。但是步骤较多，变换方法很繁琐。相比较而言，模型一不仅所用步骤少，而且还简单明了。并且所求出来的模型具有对称美，观赏性很高，最后还对此模型进行了扩展。本文特色在于从两个方面对问题进行研究，最后找出最优解。1. 问题重述“都市摩天楼”是诺基亚手机上的经典游戏。其简化规则可以这样描述：有一个城市，其土地可以表示一个55方阵。 游戏中共有四种楼房。蓝色楼房可以容纳100人，红色楼房能容纳400人，绿色楼房能容纳700人，黄色楼房能容纳1000人。但是若要在某个位置盖红色楼房，必须在位置周围（上，下，左，右，斜相邻不算）有蓝色楼房；同样，若要在某个位置盖绿色楼房，必须在位置周围有蓝色楼房和红色楼房；若要在某个位置盖黄色楼房，必须在位置周围有蓝色楼房，红色楼房和绿色楼房。 游戏过程中，一次只能盖一栋楼房。另外需要注意的一点是：已建成的楼房可以被新楼房取代，只要新楼房满足“相邻”条件。试一个建造方案，使城市容纳的人口最多。2. 问题分析土地为55的方阵，可以看成是一个55的矩阵。蓝，红，绿，黄这四种楼房能容纳的人数分别是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 住房总人口数蓝色楼房用“1”表示红色楼房用“2”表示绿色楼房用“3”表示黄色楼房用“4”表示Y s矩阵各素总和55矩阵为A=aij555. 模型建立模型一：（大化小及由外到内）把这个55矩阵分成四块，标号为A,B,C,D,如图所示：a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45a51a52a53a54a55a11a12a13a21a22a23a31a32a33a13a14a15a23a24a25a33a34a35A模块：a31a32a33a41a42a43a51a52a53a33a34a35a43a44a45a53a54a55C模块：为了简化问题，要研究整个矩阵的问题可转化成研究四个模块的问题。要使总人口最多，只需要某一模块的总人口数最多，也就是要个元素的和最大。首先来看模块A:a11a12a13a21a22a23a31a32a33默认a11=a12=aij=1，在一个33阵里，既要满足题目条件，又要元素总和最大.当a11=1时，a12=1or 2，a21=1or2；max（a11a12a21）=5当a11=2时，a12=1or 2 or3or4，a21=1or2or3or4；max（a11a12a21）=10最后情况如图所示：244覆盖情况：111 121 123 143 243 243 243 243 243111 121 121 121 121 121 131 431 432111 111 111 111 111 121 121 121 1212434243234121214323424342Y=48362813=69当a11=3时，a12=1or 2or3or4，a21=1or2 or3or4；max（a11a12a21）=11这种情况如图所示：3443而此时求得的各元素和应为最大14，在覆盖过程中这个小模块的数据变换跟其他模块是没有关系的，因此可以对称到另外3个模块即B模块C模块D模块，则可达到整个矩阵各元素总和最大。整个矩阵各元素总和最大的推导过程：（由外到内）111111111111111111111111121212211122111221112212123121321112211122111231213342434111421112411143424334243411142212241114342433424343234221224323434243最后结果：3424343434241424343434243Y=412382411=81当a11=4时，不能满足题目要求。综合上述：a11=3为矩阵的各个元素之和的最大的情况。模型二：（由内及外，以1展开）33矩阵：a11a12a13a21a22a23a31a32a33把1234填入其中，1是234出现的基础，那么一定会有1，但是要做到总和很大，那么，1的个数应该是越少越好，因此很显然会把1放在对角线相交处，即a22 =1。342414243类似的55矩阵：a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35a41a42a43a44a45a51a52a53a54a551111113421141411243111111311132242214141224223111311111134211414112431111113111323422141412243231113341434212411111421243414334143424241414142424341433424342124221224212434243342434313422122431343424334243434342414243434342436. 模型求解用两种模型所求出的结果是相同的，均为：3424343434241424343434243该表格所对应的实际游戏盖房图应为： Y=121000870044001100=193007. 模型优缺点所建造房屋居住人口最多。最优解证明过程：用复杂问题 简单化原则。即将矩阵分成几块小模型来分析，并采用自上而下，从左到右，由外而内的原则。444444444444通过对建房规则的分析，4不能出现在图中红色区域且每个“田”字格最多只能出现2个4. 为了使矩阵中Y最大，只有使任何两个“田”字格中都有两个4.要使任何两个“田”字格中都有两个4，4只有出现在如图所示的位置。3 44343434414434343443为了使A中Y最大，A中 a11最大只能为3，同理为了使B,C,D中Y最大， a15 ，a51，和a11 最大也只能为3.如图所示。3424343434241424343434243又因为1是2，3，4生成的基础，所以矩阵中必须有1。而且1在最后的布局中越少越好，当然最理想的情况是只有1个1。要让1的利用率最大，而如果把矩阵的第三行当作横坐标，第三列当作纵坐标的话，上图中的数字刚好是对的，因而把1建在矩阵的中心。而同样要有2，又根据对称把其他的地方建为2。如图所示：现在验证A中能否建如图所示的摩天楼。1111111111111111111111111第一步：全部建立1，共建了25次第二步：在如图所示的位置 推掉1建立2，共建了8次1122121111211121111212211 第三步：推掉原来的1建3122321111211121111232213立满足条件的3共建了4次 第四步：推掉原来的1 或2建立满足条 件的4共建了8次3424341114211124111434243第五步：推掉原来的1建立满足条件的2，共建了2次如图3424341214211124121434243第六步：推掉原来的1建立满足条件的3，共建了4次如图3424343234211124323434243第七步：推掉原来的1建立满足条件的4，共建了4次如图3424343434241424343434243经过验证，完全可以建立这样的摩天楼，根据上面的