2011 全国大学生数学建模竞赛B题优秀论文.pdf

交巡警服务平台的设置与调度 摘要 本文探讨了如何根据城市的实际情况与需求合理地设置交巡警服务平台、 分配各平 台的管辖范围、调度警务资源的问题。实际上布置服务平台的基本原则有：1. 尽可能使 发生事故的地点在三分钟内有巡警及时赶到。2. 尽可能使警察的工作量较为均衡。 问题一：根据 A 城区具体情况为各交巡警服务平台分配管辖范围 问题一要求在三分钟内能有警察赶到事故发生的现场，经分析发现有些路段的长度 已经超过 3km 甚至 6km， 对于这样的路段不可能有警察在三分钟内到达， 所以提出一个 重要的模型假设：突发事件只会发生在路口处。在此假设的基础上，我们建立了逐点扩 散模型，以每个服务平台为中心，运用 C+对其所有相邻点逐个判断，若路程满足条件， 再相邻点的相邻点进行判断，依次类推直到不满足条件为止，最终得到了每个警察的管 辖路口。此处对受到重复管辖的路口不予特别处理，因为重复管辖在发生事故时能够给 警察更多协调时间，再者如果同一警察管辖范围内发生两件以上事故，重复管辖可以减 少警察的工作量，提高工作质量。尽管如此我们在允许重复的情况下得到结果，发现仍 然存在路口是所有警察在三分钟内无法管辖的，自然地，这些点就是接下来优化时要处 理的点。 问题二：对进出该区的 13 条交通要道实现快速全封锁 问题二实质是一个最优化问题， 即在最短时间内， 调度警察赶到 13 个出入城区的路 口。对于这个最优化问题，我们从局部入手，采用局部最优的思想，将 13 个出入口分 区，在严密的理论分析基础上求出每个区的最优结果，得到总体的最优结果。其中在处 理左下角两个通向 E 城区同一点的出口时，我们认为可以将警察直接调度到 E 区的这一 点，这样就节省一个单位的警力资源，使资源调度空间更大。 问题三：增加 2 至 5 个平台改善警察工作量不合理的情况 问题三非常自然地承接了问题一遗留的问题， 实质就是对无人管辖的路口进行处理。 我们在距离这部分路口 3km 以内（包括本身）的路口安插服务平台，运用 C+从插入 2 个平台开始遍历验证，最终发现至少插入 4 个平台才能解决问题。最后，在四个平台的 48 种方案中，以警察的工作量不均衡度（即方差）的大小来选出最佳方案。 问题四：分析研究该市现有交巡警服务平台设置方案的合理性并作修正 问题四提出对全市的的服务平台布置合理性进行分析，按照设置服务平台的两个基 本原则分别对现有的服务平台设置进行验证，发现现有方案很大程度的违背了两种原 则。因此需要对现有方案进行调整。本文选用静态插入模型，在工作量很不均衡且无人 管辖的路口附近新增服务平台，运用 C+搜索找出最少的增加平台数，再沿用问题三的 处理方法，找出需要增加的平台个数以及位置。 问题五：调度全市交巡警服务平台警力资源的最佳围堵方案 对于问题五，也就是追捕逃犯问题，我们采取优化的方案。我们调集全市的警 力围堵逃犯出逃 3 分钟内到达的路口之后可能到达的所有路口，如果无法围堵，则扩大 范围，围堵下一级可能到达的路口。最后通过 lingo 的优化处理，我们得到结果，可以 在 12.68027 分钟内完成围堵。 关键词：逐点扩散模型，静态插入模型，局部最优化思想，Matlab，lingo，C+ 一、 问题重述 “有困难找警察” ，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理 交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的 一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警 力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理 地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临 的一个实际课题。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题： （1）附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡 警服务平台的设置情况示意图，相关的数据信息见附件 2。请为各交巡警服务平 台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有 交巡警（警车的时速为 60km/h）到达事发地。 对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该 区的 13 条交通要道实现快速全封锁。 实际中一个平台的警力最多封锁一个路口， 请给出该区交巡警服务平台警力合理的调度方案。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况， 拟在该区内再增加 2 至 5 个平台，请确定需要增加平台的具体个数和位置。 （2）针对全市（主城六区 A，B，C，D，E，F）的具体情况，按照设置交巡警 服务平台的原则和任务， 分析研究该市现有交巡警服务平台设置方案 （参见附件） 的合理性。如果有明显不合理，请给出解决方案。 如果该市地点 P （第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到 报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警 服务平台警力资源的最佳围堵方案。 二、 问题分析 2.1 问题一 问题一要求根据 A 城区具体情况为各交巡警服务平台分配管辖范围。在此问中，要 求警察能尽量在 3min 中内赶到事发地点，且尽可能所有地点都有警察管辖。在具体分 析时，我们发现有部分路段较长，且有相当一部分路段本身长度甚至就在 3km，6km 以 上，如果要求警察在案发三分钟之内赶到道路上任意点肯定是不可能的，并且由于在公 路上发生各种事件概率相对人流集中的节点处少很多。因此提出一个重要假设：假设突 发事件都发生在节点处。这一假设将成为之后论述的基本前提。至于在确定警察管辖范 围时，我们采用逐点扩散模型，这一模型的基本思想是：针对每一个警察个案分析，对 每一个警察，首先判断他到所有相邻点的距离，若小于等于 3km，则找出此点的其他相 邻点，再判断如此形成的道路长度，如此类推，直至道路的长度大于 3km 为止，放弃超 过 3km 的部分，在 3km 以内的点就都是此警察的管辖范围。此模型存在另一个明显的假 设：允许不同警察管理相同的路口。实际上，此假设不但不影响问题的解决，在一定程 度上更加有利于对事件的处理：如果公共管辖路口发生事件，警察可以同时前往解决问 题；如果有警察出现管辖范围内发生多起事件时，公共路口可以留给其他警察，提高问 题解决的效率。在这两大假设的基础上，用 C+实现上述的逐点扩散模型，得到 20 个警 察各自的管辖范围，再求其并集就得到所有警察的管辖范围，求并集的补集就是所有警 察都管辖不到的路口。 2.2 问题二 问题二要求对进出该区的 13 条交通要道实现快速全封锁。实际上就是对 13 个出入 A 区的 13 个路口进行封锁。这是一个明显的最优化问题。由于此问题情况较为清楚，且 安排方案实际是由 13 个出入路口决定，因此对 13 个出入路口采用分区讨论的方案，对 每个部分求解出最优化方案，由局部最优的解得出全局的最优解。尤其值得注意的是， 我们在处理 A 区左下角的出入路口时发现，有两个出入路口同时通向 E 区中的同一点， 因此只要安排警察奔赴 E 区那一点就可以同时封锁这两个点，不仅时间短，而且节省了 一个单位的警力资源。 2.3 问题三 问题三要求在现有的服务平台中安置几个新的服务平台，使新的服务平台设置方案 能够处理掉问题一未能处理的路口，同时减少警察工作的不确定度。由于是新插入服务 平台，因此在允许管辖范围重复的假设前提下，对其他的服务平台工作量没有影响，因 此只要单独分析未能处理的工作平台即可。由第一问的结果已知了未能受到管辖的路 口。在图上找出与这些点距离在 3km 以内的点（包括本身）的点组成集合，取集合中的 路口插入新的服务平台。由于服务平台的个数是不定的，因此运用 C+从 2 个平台开始 一次验证， 发现直到插入 4 个平台时才能管辖所有点。 而插入 4 个平台的方案有很多种， 此时警察工作的不均衡度就是衡量方案好坏的标准，在所得所有 4 个平台的插入情况中 选择工作不均衡度最小的情况即为最佳插入方案。 2.4 问题四： 问题四要求对整个城区的现有交警服务平台设置方案的合理性进行分析。根据两条 基本原则： 1.尽可能使案发路口在 3 分钟内有警察赶到 2.尽可能减小警察工作的不均衡 度。用 C+编程对上述两条原则进行验证，发现无论那一条原则，现有的方案做的都有 较大失误。因此考虑改善原来的方案，我们选用静态增加平台数的方法，沿用问题三的 解决方案，求出整个城区无人管辖的路口，然后在距离他们 3km 之内的地方插入新的服 务平台直，运用 C+编程求出至少需要的平台数目，最后由方差确定方案选择。 2.5 问题五 对于第二题的追捕逃犯问题。我们调集全市的警力围堵逃犯出逃 3 分钟内到达的路 口之后可能到达的所有路口，如果无法围堵，则扩大范围，围堵罪犯下一级别可能到达 的路口。直到可以找到一种方案，使得需要围堵的路口中任一点到巡警的路程都小于到 罪犯的距离。这样，程序可以在最短时间内找到围堵方案，让罪犯无路可逃，同时尽可 能避免伤害到群众的生命安全。 三、 模型假设 1. 所有事故都在路口发生 2. 每个路口可以由多个服务平台管辖 3. 每个服务平台的警力配备基本相同 4. 每个事故都可以由一个服务平台独立处理 5. 工作量：服务平台所管辖路口发案率之和 6. 工作不均衡度: 服务平台工作量之间的方差 7. 假设逃犯的车速与警车相同，两者都以最大速度匀速行驶 8. 假设出警时间即为警察从服务点到目的地的时间 9. 假设巡警不知道坏蛋的逃跑方向 四、 符号说明 i J 巡警所在点 i N i J 所管理路口数 ( , )d x y 两点间最短距离 i p J n i J 所管辖的第 p 个路口 C 新增巡警集合 i C 新增巡警 i I 需求集元素 c N C 的元素个数 I 需求集 五、 模型建立与求解 5.1 问题一 5.1.1 逐点扩散模型 根据问题一的分析，建立逐点扩散模型。得到最大覆盖函数为： 20 1 1 max() i i fN 满足： ( ) 1 . . (,)3 i i p iJ N st d J n 这一模型的基本思想是：针对每一个巡警服务平台个案分析。具体步骤如下： a) 对一个平台 i J，首先判断他到所有相邻点 i K的距离 ( ) (,) j ii d J K。若小于等于 3km，则记录该相邻点与距离，若超过 3km，则舍弃该相邻点。 b) 对记录的所有相邻点 i K ，继续判断其与其所有相邻点的距离。重复（1）中 操作并叠加距离直至距离和大于 3km。如此便遍历出 i J能管辖的所有节点与 路线。 c) 对所有 i J 重复（1） 、 （2）操作，如此便遍历出所有巡警服务平台能管辖的所 有节点 5.1.2 模型求解 对模型的求解借助 C+的编程，相关代码见附录。求解结果见下表 巡警服务台编号 管辖点编号 巡警服务台编号 管辖点编号 1 1 75 76 77 78 19 64 66 67 65 68 69 70 71 79 80 18 2 44 43 72 42 11 11 26 27 25 2 2 44 3 67 68 66 40 43 72 73 74 71 69 42 17 70 1 75 12 12 25 3 3 65 66 67 68 76 64 44 2 43 70 55 54 13 13 22 21 23 24 4 4 63 64 65 66 57 58 60 62 14 14 5 5 49 50 51 52 56 59 58 53 47 48 6 7 15 15 31 6 6 59 51 52 56 50 58 47 48 5 7 16 16 36 35 45 46 9 8 34 33 37 7 7 32 33 34 9 8 31 47 48 6 5 30 17 17 40 42 43 2 72 70 41 8 8 9 35 45 46 36 37 16 34 33 32 47 7 31 18 18 81 82 83 84 89 90 91 88 85 20 87 9 9 35 45 46 8 36 37 16 33 34 32 31 7 19 19 79 80 18 81 82 83 74 73 78 1 75 69 70 71 68 77 76 64 66 67 65 10 10 20 20 86 87 88 89 84 90 91 85 83 82 18 5.2 问题二 5.2.1 局部优化模型的建立与求解 图? A 区交通路线图 图 1 A 区分区大致示意图 按照上图所示对 A 区进行大致分区。显然三个分区之间很难产生交叉，如若产生交 叉，则不可能在短时间内封锁全城。因为三个分区之间基本没有影响，因此可以通过局 部优化结果得到全局最优化结果。至于某些具体路口，如 2,3 之间仍有两个路口则会在 具体操作时具体分析。接下来就对不同分区进行具体调度布置。布置原则为出入口必须 有巡警封锁，且时间应该尽可能短。由于时间要尽可能短，因此方案的最优化主要取决 于移动时间最长的巡警。因此在处理时首先考虑每个出入口应由哪些巡警封锁，再考虑 尽量缩短移动距离最长的巡警所要移动的距离。 注：由于以下分析时点不是按照序号编排，因此不沿用符号说明里的符号，在每个区中 定义 P 为巡警点，a,b,c 表示出入口。 2 1 3 第一步：处理 1 区 图 2 1 区调度处理 如上图所示，1 区实际上有五个警察，六个出入口。显然分配时， 4 P 将封锁 b 路口， 2 P 将封锁 c 路口。由于明显此区移动距离最长的巡警必然是 3 P ,因此应让 3 P 封锁离他最 近的点。 计算 3 P 到 f，a，c 的距离依次为 7.587km，8.244km，7.708km。因此将 3 P 调度去封锁 f 点，调度 1 P 封锁 a。 至于 d，e 两路口则采取特殊化处理，因为的 d，e 两路口同时通到 E 区的同一点，因此 只要调度 5 P 去封锁 E 区那一点即可。 图 3 A，E 区衔接处 如上图所示，只要封锁 X 点就可以达到封锁的 d，e 两点的效果。 上述处理完毕，得到 1 区的封锁方案： 1 P 封锁 a， 2 P 封锁 c， 3 P 封锁 f， 4 P 封锁 b， 5 P 封锁 E 区的 X。 第二步：处理 2 区 a b c d e f d e X 图 4 2 区调度处理 对于 2 区的处理，从 g，h 两路口开始，因为 g，h 距离巡警点比较远，直接决定了 最长时间，因此计算 7 P 到 g，h 两个路口的最短距离，分别为 29.0km，28.2km。因此将 6 P 调度去 g， 7 P 调度去 h。对于 k，j 两个路口的处理则是 8 P ， 9 P 各自封锁哪个路口的问 题，因为最长时间已经由 6 P ， 7 P 确定，因此 8 P ， 9 P 封锁 k，j 两个路口均可。 最终 2 区的处理方案： 6 P 调度去 g， 7 P 调度去 h， 8 P 调度去 k， 9 P 调度去 j。 第三步：3 区的处理 图 5 3 区调度方案 显然， 13 P 调度去 l。关键在于 12 P ， 13 P 到 m 的距离谁更小，因为 11 P 到 k 的距离很小。 计算 12 P ， 13 P 到 m 的距离分别为 3.41km，4.76km。 g h i j k l m 3 区的调度方案为： 13 P 调度去 l， 12 P 调度去 m， 11 P 调去 k。 按照上述布置方案即可得到全局最优化方案。 5.3 问题三 5.3.1 静态插入模型 从问题一的求解可以看出，现有的 20 个服务平台并不能在规定时间内到达 A 城区全部 92 个节点。对全体服务平台管辖的节点求补集可得到下述不能被覆盖的节点 28,29,38,39,61,92I 。用与求解问题（1）同样的方法可以求得距离I中所有元素最短距离小 于 3km 的候选点集合28,29,38,39,40,48,61,87,88,89,90,91,92Q 本题要在 Q 中选择出子集 C，C 中有 25 个元素作为新增巡警平台的位置，使I中所有路口在案发时均有巡警赶到。 建立模型如下： 2 min() C fN 满足： 5 . .2 (,)3,1,2.,1,2.6 ,1,2. i C C ijC CC CQ N stN d C IiNj IniN 5.3.2 模型求解 求解借助 C+编程完成， 相应代码见附录。 求解结果显示只有当 C 中元素大于等于 4 时才能满足覆盖 I 中所有元素的条件。所有组合见下表。 28 38 48 87 28 39 61 87 29 38 48 87 29 39 61 87 28 38 48 90 28 39 61 90 29 38 48 90 29 39 61 90 28 38 48 91 28 39 61 91 29 38 48 91 29 39 61 91 28 38 48 92 28 39 61 92 29 38 48 92 29 39 61 92 28 38 61 87 28 40 48 87 29 38 61 87 29 40 48 87 28 38 61 90 28 40 48 90 29 38 61 90 29 40 48 90 28 38 61 91 28 40 48 91 29 38 61 91 29 40 48 91 28 38 61 92 28 40 48 92 29 38 61 92 29 40 48 92 28 39 48 87 28 40 61 87 29 39 48 87 29 40 61 87 28 39 48 90 28 40 61 90 29 39 48 90 29 40 61 90 28 39 48 91 28 40 61 91 29 39 48 91 29 40 61 91 28 39 48 92 28 40 61 92 29 39 48 92 29 40 61 92 共有 48 种组合，再根据工作均衡度来进行筛选，选出工作最为均衡的一种组合。工作 均衡度的计算公式为 2 1 cincicinci C cnpnp N 。在上述组合中在加入 2 1 . .min() cincicinci C stcnpnp N 进行筛选，得到如下结果 28 38 48 87 1.82222 28 39 61 87 1.94209 29 38 48 87 1.82757 29 39 61 87 1.94743 28 38 48 90 1.82222 28 39 61 90 1.94209 29 38 48 90 1.82757 29 39 61 90 1.94743 28 38 48 91 1.66071 28 39 61 91 1.79978 29 38 48 91 1.66433 29 39 61 91 1.80347 28 38 48 92 1.99887 28 39 61 92 2.10398 29 38 48 92 2.00499 29 39 61 92 2.11009 28 38 61 87 1.90669 28 40 48 87 1.61376 29 38 61 87 1.9123 29 40 48 87 1.62096 28 38 61 90 1.90669 28 40 48 90 1.61376 29 38 61 90 1.9123 29 40 48 90 1.62096 28 38 61 91 1.76578 28 40 48 9128 40 48 91 1.460041.46004 29 38 61 91 1.76971 29 40 48 91 1.46544 28 38 61 92 2.06893 28 40 48 92 1.79422 29 38 61 92 2.0753 29 40 48 92 1.80208 28 39 48 87 1.85822 28 40 61 87 1.70197 29 39 48 87 1.8633 29 40 61 87 1.70935 28 39 48 90 1.85822 28 40 61 90 1.70197 29 39 48 90 1.8633 29 40 61 90 1.70935 28 39 48 91 1.69572 28 40 61 91 1.57137 29 39 48 91 1.69908 29 40 61 91 1.57698 28 39 48 92 2.0342 28 40 61 92 1.86594 29 39 48 92 2.04007 29 40 61 92 1.874 得出最终结果为28,40,48,91C 5.4 问题四 5.4.1 分析合理性 对于交巡警服务平台设置方案的合理性，我们定义了两个评价原则： 原则一：巡警能在3min之内到达案发路口 原则二：巡警服务台的工作量均衡度尽量小。 依据问题分析中的两个评价原则，分别对现有巡警服务台的设置方案进行评价。 讨论现有设置方案是否满足原则一 全城六区 A，B，C，D，E，F 现有个 80 巡警服务台、582 个路口，运用问题一（1）中的算 法，得到全城集合I路口的数目与位置，如下表： 28 29 38 39 61 92 122 123 124 151 152 153 183 199 200 201 202 203 205 206 207 208 209 210 215 238 239 240 247 248 251 252 253 257 259 261 262 263 264 268 269 285 286 287 288 299 300 301 302 303 304 312 313 314 315 316 317 318 319 329 330 331 332 336 337 339 344 362 369 370 371 387 388 389 390 391 392 393 395 407 408 409 411 412 413 417 418 419 420 438 439 443 445 446 451 452 455 458 459 464 469 471 474 486 487 505 506 507 508 509 510 512 513 514 515 516 517 518 519 522 523 524 525 526 527 529 533 540 541 559 560 561 566 569 574 575 578 582 计算结果表明：I中共有138个元素，即在案发时巡警不能在3min到达的路口数，约占全城 总路口数的1/4。 讨论现有设置方案是否满足原则二 运用问题三中的方法，为每个巡警服务台分配管辖范围，并计算工作量及巡警服务台的工 作不均衡度。结果如下： 表12现有 配置下每 个巡警服 务台的工 作量巡警 服务台 工作量 巡警服务 台 工作量 巡警服务 台 工作量 巡警服务 台 工作量 1 10.3 93 2.1 178 4.5 378 2.6 2 9.7 94 11.3 179 13 379 7.4 3 5.6 95 9.5 180 13 380 2.5 4 17.1 96 11.5 181 6.2 381 6.2 5 9.7 97 5.6 182 12.2 382 10.3 6 2.5 98 12.1 320 8.7 383 10 7 40.4 99 4.3 321 12 384 8.3 8 5 100 4.5 322 4.4 385 9.1 9 8.2 166 3.8 323 4.2 386 6.3 10 1.6 167 8.3 324 7.9 475 13.1 11 4.6 168 4.7 325 2.2 476 13 12 10.3 169 3.4 326 5.1 477 10.7 13 39.6 170 12.9 327 7.6 478 9.5 14 7.2 171 12.4 328 6.7 479 8.7 15 12.9 172 8.3 372 5.2 480 4.7 16 28.4 173 11.5 373 4.1 481 7.2 17 5.3 174 10.1 374 5.5 482 4.4 18 6.1 175 8.7 375 6.1 483 3.3 19 3.4 176 8.1 376 2.6 484 3.8 20 11.5 177 2.2 377 4.2 485 3.3 结果分析： 由表中数据可得：在现有配置下，其中有个7巡警服务台的工作量已达到40.4，而其中还有 10巡警服务平台的工作量仅为1.6，所有巡警服务台的工作量不均衡度为40.3。可见，此时 巡警服务平台的工作量极其不均衡。 根据上述 1、2 的讨论可知：现有巡警服务台的设置极其不合理。 5.4.2 静态增加改良方案 对于目前不合理的情况，我们设计了“静态增加”的方案，即在不改变现有巡警服务平 台的配置情况下，适当增加新的平台以解决无法覆盖全部节点与工作量不均衡的问题。 由上文步骤求解结果可得 138 个元素组成的集合I，同样采用问题 3 的方法，得到新增加的 节点集合C与工作量c，结果见下表： 由上表可知：标号为 170 的巡警服务台工作量最大，为 12.2，541 巡警服务台工作量最为 0.1，此方案不均衡度降为 9.4078 5.5 问题五 根据题意，为了快速搜捕嫌疑犯，也就是说，各个平台到封锁路口的时间要最短， 即最大搜索距离最短，首先求出需要封锁的路口，具体做法为：先计算出嫌疑犯 3 分钟 走的路程为 3km，再以 P32 点为中心，找出 3km 内的点的毗邻点，即为嫌犯可能到达 的点。使用 Matlab 和 Lingo 软件求解 80 个警察点到这些点的方案中最长路程最短的方 案。如果没有方案，则再求下一级毗邻点，重复上述操作。建立模型如下： 目标函数：min=max(dij*xij) 约束条件： 55.2 模型求解 最终的求解结果如下： 15 173 151 93 96 382 153 95 177 177 202 175 203 180 235 16 236 15 325 324 328 327 332 380 362 323 387 100 418 375 483 478 541 476 572 484 578 485 479 此时最短时间为：12.68027 六、模型评价与推广 1.优点： 采用离散定位模型作为城区巡警服务台优化布局方法的应用基础, 结合相关的影响因素 （发案率）,能很好地解决实际问题。本文把实际问题抽象成集合模型、规划模型和图论 模型，巧妙地整体与局部进行结合，简化了问题。完整准确的描述了实际问题。本文所 用算法，效率好，精度高，解决实际问题方便快捷。 2.缺点： 本文对工作量的定义只考虑路口的发案率，没有考虑不同区的人口密度对交巡警工作量 的影响。 本文对所有区都是以 3 分钟赶到作为标准， 较少考虑不同区的路口的发案率相 差加大，导致交巡警工作量难以均衡。 3.模型推广： 本模型不仅对巡警服务平台适用，而且可以广泛运用于消防站、医院等应急服务设施的 布局。 七、附录 1.C+处理 EXCEL： #include #include #include #include using namespace std; struct point double a5; int num; ; void main() point point92; int ch,ch1; int ch2; int i=1; int j=0; int p,q; ifstream ifile; ofstream ofile; ifile.open(“E:a1.txt“); ch=1; while(!ifile.eof() ifilech1; ifilech2; if(ch1=ch) j+; pointi-1.num=j; pointi-1.aj-1=ch2; else ch=ch1; j=1; i+; pointi-1.num=j; pointi-1.aj-1=ch2; ifile.close(); ofile.open(“E:a2.txt“); for(p=0;pxy; if(ji; if(i!=0) count+; pointj-1.Choption(j,count); pointj-1.Getnext(count,i,pointi-1.Getx(),pointi-1.Gety(); else j+; count=0; ifile1.close(); double length1,length2,length3,length4,length5,length6,length7,length8,length9,length10; int a1,a2,a3,a4,a5,a6,a7,a8,a9,a10; int b1,b2,b3,b4,b5,b6,b7,b8,b9,b10; int p; b1=0; Record record92; for(i=0;iodds; pointi.Chodds(odds); else break; Record record16;/求 6 个剩余点的 3KM 内点 int left6; left0=27; left1=28; left2=37; left3=38; left4=60; left5=91; a1=a2=a3=a4=a5=a6=a7=a8=a9=a10=0; b1=b2=b3=b4=b5=b6=b7=b8=b9=b10=0; for(i=0;i=5;i+) record1i.Putin(lefti+1); for(a1=0;a1=pointlefti.Getnebnum()-1;a1+) length1=0; cout“【编号】“lefti“ “; b1=pointlefti.Getnextnum(a1); if(b1=lefti)continue; if(length13) length2=length1+pointlefti.Distance(a1); cout“第一点“b1“ “; for(a2=0;a2=pointb1.Getnebnum()-1;a2+) b2=pointb1.Getnextnum(a2); if(length23) record1i.Putin(b1+1); if(b2=i|b2=b1)continue; length3=length2+pointb1.Distance(a2); cout“第二点“b2“ “; for(a3=0;a3=pointb2.Getnebnum()-1;a3+) b3=pointb2.Getnextnum(a3); if(length33) record1i.Putin(b2+1); if(b3=i|b3=b1|b3=b2)continue; length4=length3+pointb2.Distance(a3); cout“第三点“b3“ “; for(a4=0;a4=pointb3.Getnebnum()-1;a4+) b4=pointb3.Getnextnum(a4); if(length43) record1i.Putin(b3+1); if(b4=i|b4=b1|b4=b2|b4=b3)continue; length5=length4+pointb3.Distance(a4); cout“第四点“b4“ “; for(a5=0;a5=pointb4.Getnebnum()-1;a5+) b5=pointb4.Getnextnum(a5); if(length53) if(b5=i|b5=b1|b5=b2|b5=b3|b5=b4)continue; record1i.Putin(b4+1); length6=length5+pointb4.Distance(a5); cout“第五点“b5“ “; for(a6=0;a6=pointb5.Getnebnum()-1;a6+) b6=pointb5.Getnextnum(a6); if(length63) record1i.Putin(b5+1); if(b6=i|b6=b1|b6=b2|b6=b3|b6=b4|b6=b5)continue; length7=length6+pointb5.Distance(a6); cout“第六点“b6“ “; for(a7=0;a7=pointb6.Getnebnum()-1;a7+) b7=pointb6.Getnextnum(a7); if(length73)/ record1i.Putin(b6+1); if(b7=i|b7=b1|b7=b2|b7=b3|b7=b4|b7=b5|b7=b6)continue; length8=length7+pointb6.Distance(a7); cout“第七点 “b7“ “; for(a8=0;a8=pointb7.Getnebnum()-1;a8+) b8=pointb7.Getnextnum(a8); if(length83)/ record1i.Putin(b7+1); if(b8=i|b8=b1|b8=b2|b8=b3|b8=b4|b8=b5|b8=b6|b8=b7)continue; length9=length8+pointb7.Distance(a8); cout“ 第 八点“b8“ “; for(a9=0;a9=pointb8.Getnebnum()-1;a9+) b9=pointb8.Getnextnum(a9); length9+=pointb8.Distance(a9); if(length93) record1i.Putin(b8+1); if(b9=i|b9=b1|b9=b2|b9=b3|b9=b4|b9=b5|b9=b6|b9=b7|b9=b8)continue; coutlength10“ “第九点“b9endl; else coutlength8endl; break; / else coutlength7endl; break; /8 / else coutlength6endl; break; /7 else coutlength5endl; break; else coutlength4endl; break; else coutlength3endl; break; else coutlength2endl; break; else break; /求合集 oneoneendl; oneone“求 6 个剩余点的 3KM 内点并集“ “endl; int m; int cand13; for(m=0;m=12;m+) candm=0; for(j=1;j=92;j+) for(i=0;i=5;i+) for(p=0;p=91;p+) if(record1i.Getnode(p)=j)q+; if(q!=0) for(m=0;m=12;m+) if(candm=0) candm=j-1; oneonej“ “; break; q=0; Record record213; a1=a2=a3=a4=a5=a6=a7=a8=a9=a10=0; b1=b2=b3=b4=b5=b6=b7=b8=b9=b10=0; for(i=0;i=12;i+) record2i.Putin(candi+1); for(a1=0;a1=pointcandi.Getnebnum()-1;a1+) length1=0; cout“【编号】“candi“ “; b1=pointcandi.Getnextnum(a1); if(b1=candi)continue; if(length13) length2=length1+pointcandi.Distance(a1); cout“第一点“b1“ “; for(a2=0;a2=pointb1.Getnebnum()-1;a2+) b2=pointb1.Getnextnum(a2); if(length23) record2i.Putin(b1+1); if(b2=i|b2=b1)continue; length3=length2+pointb1.Distance(a2); cout“第二点“b2“ “; for(a3=0;a3=pointb2.Getnebnum()-1;a3+) b3=pointb2.Getnextnum(a3); if(length33) record2i.Putin(b2+1); if(b3=i|b3=b1|b3=b2)continue; length4=length3+pointb2.Distance(a3); cout“第三点“b3“ “; for(a4=0;a4=pointb3.Getnebnum()-1;a4+) b4=pointb3.Getnextnum(a4); if(length43) record2i.Putin(b3+1); if(b4=i|b4=b1|b4=b2|b4=b3)continue; length5=length4+pointb3.Distance(a4); cout“第四点“b4“ “; for(a5=0;a5=pointb4.Getnebnum()-1;a5+) b5=pointb4.Getnextnum(a5); if(length53) if(b5=i|b5=b1|b5=b2|b5=b3|b5=b4)continue; record2i.Putin(b4+1); length6=length5+pointb4.Distance(a5); cout“第五点“b5“ “; for(a6=0;a6=pointb5.Getnebnum()-1;a6+) b6=pointb5.Getnextnum(a6); if(length63) record2i.Putin(b5+1); if(b6=i|b6=b1|b6=b2|b6=b3|b6=b4|b6=b5)continue; length7=length6+pointb5.Distance(a6); cout“第六点“b6“ “; for(a7=0;a7=pointb6.Getnebnum()-1;a7+) b7=pointb6.Getnextnum(a7); if(length73)/ record2i.Putin(b6+1); if(b7=i|b7=b1|b7=b2|b7=b3|b7=b4|b7=b5|b7=b6)continue; length8=length7+pointb6.Distance(a7); cout“第七点 “b7“ “; for(a8=0;a8=pointb7.Getnebnum()-1;a8+) b8=pointb7.Getnextnum(a8); if(length83)/ record2i.Putin(b7+1); if(b8=i|b8=b1|b8=b2|b8=b3|b8=b4|b8=b5|b8=b6|b8=b7)continue; length9=length8+pointb7.Distance(a8); cout“ 第 八点“b8“ “; for(a9=0;a9=pointb8.Getnebnum()-1;a9+) b9=pointb8.Getnextnum(a9); length9+=pointb8.Distance(a9); if(length93) record2i.Putin(b8+1); if(b9=i|b9=b1|b9=b2|b9=b3|b9=b4|b9=b5|b9=b6|b9=b7|b9=b8)continue; coutlength10“ “第九点“b9endl; else coutlength8endl; break; / else coutlength7endl; break; /8 / else coutlength6endl; break; /7 else coutlength5endl; break; else coutlength4endl; break; else coutlength3endl; break; else coutlength2endl; break; else break; oneoneendl“添加四个点时组合与方差“endl; int check6; double odd6; odd0=1.3; odd1=1.4; odd2=1.2; odd3=1.4; odd4=0.6; odd5=0.8; double eve4; for(i=0;i=3;i+)evei=0; int n; double square; for(i=0;i=5;i+)checki=0; for(a1=0;a1=9;a1+) for(a2=a1+1;a2=10;a2+) for(a3=a2+1;a3=11;a3+) for(a4=a3+1;a4=12;a4+) for(m=0;m=91;m+) for(n=0;n0) square=Square(eve0,eve1,eve2,eve3); oneonecanda1+1“ “canda2+