交通点设置优化

1、交巡警服务平台的设置与调度摘要针对交巡警服务平台的管辖范围分配及警力调度问题。首先利用图论里的Floyd算法建立A区服务平台与路口节点的的路径关系模型，在此基础上对服务台进行局部调整，并将该方法应用到全市6区的服务平台设置分析与调整中。然后，利用整数规划理论建立了快速全封锁的最优方案。最后，对发生重大刑事案件的嫌疑犯的追踪案例，根据不同的情况给除了两种最佳围堵方案。对于问题一：第一小问首先利用“画圆”思想排除最不可能最短路径在3km范围内的交通节点。接着通过最短路径算法求出每个平台与对应节点之间的最短路径，根据最短路径的长度是否小于3km，确定各平台能够及时到达的所有交通节点。继而将共有的交通

2、节点在各服务平台之间进行合理分配。对于无法在3分钟内到达的交通节点，按照就近原则划分给最近的平台。第二小问本质上是不平衡指派问题最优解的求解。本文运用整数规划的方法，使用LINGO软件进行编程，得到被封锁的每个路口对应的服务平台。利用MATLAB画出其最佳封锁路线图，并得到最快完成封锁的时间为8.24min。第三小问要解决各平台工作量不均衡和有些地方出警时间过长的情况，即要尽量让每个交巡警服务平台的管辖范围和工作量都保持平衡。根据定量性原则，有效性原则，在各个平台3min内能够到达的交通节点的数据基础上，对各个平台辖区内的重复交通节点进行分配，然后再考虑孤立点，在合适的的地方添加交巡警服务平台

3、，最后再综合各辖区的累计发案率适当增加交巡警服务平台。得出结果，在28、40、48、92对于问题二：第一小问以上述模型和计算方法，找出每个区各自的盲点以及只能管辖自身的交通警卫平台针对这些节点和平台进行交通警卫平台的增设和删减，并给出最终的改善方案。第二小问以两个方案来对罪犯进行搜捕。A方案以通过以32号结点为起始点，求出罪犯逃逸速度为80km/h时候6min内可能到达的所有交通节点。让警察在罪犯可能到达的交通节点外围封锁所有可能的逃逸结点形成一个闭合的曲线。B方案首先通过最短路径的分别计算罪犯在不同逃逸速度时的活动范围，确定嫌疑犯的活动范围在A,C,F区。对A,C,F区的出口进行封锁，使警察

4、从接到报警开始封锁路口需要的时间,和嫌疑犯逃跑到路口所需要的时间满足即可。得出结果当罪犯的逃逸速度为60km/h时可以在罪犯逃出ACF区之前完成封锁；如果罪犯的逃逸速度为80km/h;90km/h；100km/h时,在ACF区的盲点位置始终存在封锁迟于逃逸的情况。关键词：Floyd算法、非平衡指派问题、整数规划法、最短路线规划一、 问题重述1.1背景概要中国警察为有效贯彻实施刑事执法、治安管理、交通管理、服务群众四职能，往往要在一些交通要道和重要部位设置交巡警服务平台。由于警务资源有限，如何根据城市情况与需求合理设置交巡警服务平台、分配各平台管辖范围、调度警务资源是警务部门履行职能的关键。1.

5、2问题简述1.2.1问题一已知该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图以及相关的数据信息。要求解决问题如下：1) 为交巡警服务平台分配管辖范围，使其面对辖区内突发事件时，能够3min内到达（警车时速：60km/h）。2) 面对重大突发事件，要求20个交巡警服务平台能够对13条交通要道实现快速封锁，其中一个交巡警服务平台只能封锁一个路口，给出交巡警服务平台警力合理的调度方案。3) 改善交巡警服务平台的工作量不均衡和有些地方出警时间过长的现状。增加2至5个平台，给出增加平台数目及位置。1.2.2问题二已知交巡警服务平台的设置情况示意图以及相关的数据信息。要求解决问题如下

6、：1) 根据设置交巡警服务平台的原则和任务分析交巡警服务平台设置现状合理性，如不合理，给出解决方案。2) 若该市P点发生重大刑事案件，嫌犯驾车逃跑，案发3min后接到报警，为拦截嫌犯，给出调度全市交巡警服务平台警力的最佳围堵方案。二、 问题分析2.1问题分析该市的警务资源，如何根据交巡警服务平台的反应速度以及犯案率管控能力合理分配管辖范围是解决问题的关键。问题一：该部分要解决的问题可以分成三小问进行分步解决。对于第一小问：首先以每个交巡警服务平台（以下称为平台）为圆心以3km为半径“画圆”（即求出路口节点到平台的距离，然后与3km作比较）。然后求出各个平台到“圆内”各个节点的最短路径，保留3k

7、m以内的，对于大于3km的路口节点（以下称为孤立点），分配给出到其最短路径最小的平台。对于第二小问：通过指派问题的解决思想，将20个交通平台指派封锁13个交通要道，利用LINGO软件通过匈牙利算法求出使得封锁的用时最短的最优解。对于第三小问：要解决各平台工作量不均衡和有些地方出警时间过长的情况，即要尽量让每个交巡警服务平台的管辖范围和工作量都保持平衡。根据定量性原则，有效性原则，在各个平台3min内能够到达的交通节点的数据基础上，对各个平台辖区内的重复节点进行分配，然后再考虑孤立点，在合适的的地方添加交巡警服务平台，最后再综合各辖区的累计发案率适当增加交巡警服务平台。问题二：根据现实情况不同区

8、的警力管辖范围仅限于该区，只有发生重大事件时才有跨区合作的机会，因此本文将全市六区分开考虑，每个区的交巡警服务平台的辖区仅限于该区。对于第一小问：首先计算各区的服务平台的工作量、方差和各节点处的出警时间。接着，根据上面的辖区范围规划模型对每个区的平台管辖范围进行优化。最后，对平台集中且平台工作量不大的情况进行考虑并适当撤销平台以达到节约警力资源的目的。对于第二小问：对于罪犯搜捕问题，首先根据题意知警方案件发3min后接到报案，根据上文知警方可以在3min内封锁任何一个交通节点。则说明从案发到警察实现封锁罪犯最多只有6min的逃逸时间，所以罪犯所走的路径最多为8km。所以以32号结点为起始点，求

9、出最短路径小于8km的可能到达的所有交通节点。让警察在罪犯可能到达的交通节点外围封锁所有可能的逃逸结点形成一个闭合的曲线，达到小范围封锁，逐步压缩封锁范围的目的。2.2A市交通网络示意图图2- 1 A市交通网络示意图三、 问题假设1. 假设本文给出的数据均真实准确，得出的结果真实有效。2. 假设交通道路状况对线路规划没有影响，所有道路均可双向通行。3. 假设警察接到报案的反应时间可以忽略，假设警车时速为60km/h。4. 假设各区交巡警服务平台管辖互不影响。四、 符号说明符号描述加权无向图的带权邻接矩阵指派问题的系数矩阵完成路口封锁的最后耗时各个交通节点的犯案率警察从接到报警开始封锁路口需要的

10、时间罪犯逃跑到路口所需要的时间五、 问题一5.1建模思路 先是利用画圆思想，排除对于各个平台不必要的路口节点，减轻运算量优化运算。接着通过Floyd提出的优化过的最短路径算法，求出各个节点到相对的平台的最短路径。确定出孤立点，并将孤立点分配给到其最短路径最小的平台。接着，通过指派问题的解决思想，将20个交通平台指派封锁13个交通要道，利用LINGO软件通过匈牙利算法求出最优解，并且使得封锁的用时最短。最后，根据定量性原则，有效性原则，尽量让每个交巡警服务平台的管辖范围和工作量都保持平衡。先根据各个平台在3min内能够到达的交通节点的数据，对各个平台辖区内的重复节点进行分配，然后再考虑孤立点，最

11、后再综合各辖区的累计发案率适当增加交巡警服务平台。5.2建模原理5.2.1Floyd最短路径算法1为了利用加权图的带权邻接矩阵求图的任意两点之间的距离，先定义矩阵的一种运算：定义：设，矩阵的“*”运算为： ，其中 设是加权无向图的带权邻接矩阵，记 则 ，表示从顶点经顶点到顶点含2条边的路径长度，； 表示它们的最小值，即从顶点经中间点到顶点的所有通路中最短的通路长度。以此类推，在中，表示从顶点最多经顶点个中间点到顶点的所有通路中最短的通路长。因图的顶点数为，从 到的路径最多经过个中间顶点，所以只要求出就行了。于是，得到求每一对顶点间距离的算法：给出加权图的邻接矩阵。求，。令，则即为图的距离矩阵。

12、如果不仅要求任意两点之间的距离，还要求出两点间的最短路径，则在矩阵运算时要注以下表，并在运算中保留下标，如： 5.2.2指派问题2 对于有项任务且恰好有个人去完成的指派问题（称为平衡指派问题），规定每人只完成一项任务，且每项任务只能由一个人去完成 已知表示第个人完成第项任务时的效率（所用时间或成本等）， 称为效率矩阵设决策变量： 于是指派问题的数学模型为： 对于非平衡指派问题通常是先将其转化为平衡的指派问题（否则可能会得到错误的结论）然后再用匈牙利算法求解 。本文利用实例验证总结对于几种不平衡的指派问题的解法。5.3模型建立5.3.1优化运算根据附件中给出的A区交通节点数据，求出各个平台到各个

13、交通节点的距离。此时经过分析可知：距离大于3km的节点，警察沿路径到达的时间一定大于3min;距离小于3km的节点，警察到达的时间不确定。因此排除距离大于3km的交通节点，考虑到20个平台分别设立在标号为1-20的交通节点上，所以对标号为1-20的节点不予分配。则有：表5- 1 距各平台3km内的节点平台对应路口节点130 31 32 33 42 43 44 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 240 41 42 43 44 64 65 66 67 68 69 70 71 72 73 74 75 76 7

14、7 78338 39 40 43 44545563 646566676869 7076454 55 56 5758606263646566 67 68 75 76 77530 32 33 46 474849505152535657 5859 61630 32 474849 50515253 5657 5859 617303132333435 36 37 45 46 4748 49 52 53830 31323334353637454647 48 49 52 53 569313233343536374546101121 252627 281224 25 281321222324142615311

15、632 33343536374546174041424344 67 68 69 7071 72 73 74 781842 68 69 7172737475 76 777879808182831930 63 646566676869707173747576 77 78 79 80 81 82 83 84 85 88 89 90 91 922080 81828384858687888990915.3.2模型最短路径模型根据Floyd最短路径算法，利用MATLAB计算出A区加权无向图的带权邻接矩阵为【具体数据见附录】： 根据表5-1，结合带权领接矩阵，求出各个平台到对应节点的最短路径。满足条件的有：

16、表5- 2 到平台最短路径在3km以内的节点平台对应路口节点142 43 44 64 65 66 67 68 69 70 71 72 73 74 75 77 78 79 80240 42 43 44 66 67 68 69 70 71 72 73 74 75 76 78343 44545564656667687076457586062636465665474849505152535658596474850515256585973031323334474883132333435363745469313233343536374546101125262712251321222324141531163

17、33435363745461740414243707218717273747778798081828319646566676869707173747576208182838485868788899091对于不符合条件的孤立点，则利用MATLAB计算出各个孤立点到20个平台的对应最短路径，取，并将孤立点分配给对应的平台。结果如下表所示：表5- 3 各平台辖区内的节点平台对应路口节点142 43 44 64 65 66 67 68 69 70 71 72 73 74 75 77 78 79 80238 39 40 42 43 44 66 67 68 69 70 71 72 73 74 75 76

18、78343 445455646566676870764575860626364656654748495051525356585964748505152565859730313233344748 618313233343536374546479313233343536374546101125262712251321222324141528 29 31163334353637454617404142437072187172737477787980818283 92196465666768697071737475762081828384858687888990915.3.3模型路口封锁分配模型根据题

19、意，当发生重大突发性事件的时候，要对13个交通要道实现快速封锁。本文利用不平衡指派问题模型，指派20个交巡警服务平台对13个交通要道实现快速封锁，即所用的封锁时间 最短。首先根据前面求出的带权邻接矩阵给出20个交巡警服务平台对于13个交通要道的最短路径矩阵【数据见附录】，称为指派问题的系数矩阵。接着，引入0-1变量得出路口封锁指派模型为：最后，利用LINGO软件通过匈牙利算法对上述路口封锁模型进行求解。得出最佳的路口封锁方案：图5- 1 A区平台封锁路线图 其中红色加粗部分为A区的平台到对应的用时最短的交通要道的最短路径。完成路口封锁的最后耗时。5.3.4模型辖区范围规划模型在上述求出的表5-

20、 4 到平台最短路径在3km以内的节点的基础上，对各辖区重复的交通节点进行重新分配。设各个交通节点的犯案率为，则有各个平台的累计犯案率为。若交通节点在两个及以上的平台辖区内重复，则将交通节点分配给累计犯案率 最小的平台；若平台之间的累计犯案率相差小于，则通过计算交通节点到包含它的各个平台的最短路径，将交通节点分配给最短路径最小的平台。 接着对孤立点进行分析，以增加的平台尽量覆盖较多的孤立点为原则，增设平台。 最后求出各个平台的累计犯案率 ，对犯案率超过平均值的平台，在其附近兼顾尽量覆盖较多的交通节点的原则增加平台【处理数据见附录】。得出结果如下： 表5- 5 A区交巡警服务平台辖区分布平台对应

21、路口节点平台对应路口节点169 71 73 77 801321 22 23 24243 70 72 7514354 55 65 66 67 681531457 58 60 62 63 641636 37550 51 52 531741 42 72656 58 591878 79 81 82 83730 321973 74 75 76833 46 472085 86 89 90934 35 452828 29104038 39 40 44 701126 274848 49 6112259287 88 91 92 最后确定新增的平台数目为4个，分别为28、40、48、92。5.4模型评价根据程序运

22、行的结果，可知在38或39号节点处增加新平台所得结果是相差无几的，因此可以任选一个当作最终方案。由于模型在数据处理上忽略了许多细节，得到的结果可以有一定的差异，但对问题没有本质上的影响。六、问题二6.1建模思路本文主要通过各服务平台的工作量的差异与各个节点的出警时间的长短两个指标来对现有交巡警服务平台设置的合理性进行讨论。根据现实情况不同区的警力管辖范围仅限于该区，只有发生重大事件时才有跨区合作的机会，因此本文将全市六区分开考虑，每个区的交巡警服务平台的辖区仅限于该区。因此可以对上面的辖区范围规划模型稍加改进，再对六个区的平台设置合理性进行分析，并给出优化方案。对于罪犯搜捕问题，先求出罪犯在6

23、min内可能到达的所有交通结点，然后根据上述求出的平台辖区分布，指派各个平台，在罪犯可能到达的交通节点外围进行封锁，形成闭合曲线的效果，达到逐步压缩封锁范围搜捕罪犯的目的。6.2模型建立6.2.1模型市区平台设置优化模型首先计算各区的服务平台的工作量、方差和各节点处的出警时间。接着，根据上面的辖区范围规划模型对每个区的平台管辖范围进行优化。最后，对平台集中且平台工作量不大的情况进行考虑并适当撤销平台以达到节约警力资源的目的。通过MATLAB编程运行得到各个平台的工作量【数据见附录】,得到结果如表6-1所示：表6- 1 各区交巡警服务平台优化方案区号新增平台所在节点标号撤销平台所在节点标号A28

24、 40 48 92B120 14797 99C205 240 261 281 301 313166 169 179 178D333 362322 325E391 409 417 452372 376 377F493 5154846.3模型罪犯搜捕模型6.3.1方案A 根据对题目的分析可以确定罪犯的逃逸时间最多为6min，假设逃逸速度为80km/h。首先利用MATLAB求出以P点为起始点，最短路径小于8km的可能到达的所有交通节点。得到结果如下：图6- 1 罪犯逃逸时间内可能达到的交通节点 由图6-1不难发现罪犯在6min内最大的活动范围在A区，其次是C区，排在最后的是F区。根据上述结果，设计封

25、锁方案只需要将罪犯可能活动的范围给围住，罪犯便无处可逃了。所以，搜捕方案为：封锁区对外的所有交通要道；对区、区中可能的交通节点外围进行封锁。可以确定附近平台所需要封锁的交通节点【数据见附录】如下：图6- 2罪犯搜捕封锁示意图从图6-2可知，对C区的封锁只需要封锁交通节点168、216、228、239、241即可；对于F区只需要封锁488、549、581即可；对于A区的全境封锁方案在问题一中便已经给出最佳的封锁路线。6.3.2方案B由于罪犯的逃逸速度无法确定，根据实际情况，方案B对罪犯的逃逸速度分别为60km/h ; 80km/h ; 90km/h ; 100km/h的情况进行有差别讨论。罪犯若

26、以60km/h的速度逃逸，通过最短路径计算，确定罪犯的活动范围在A,C,F区。故只要保证罪犯在逃到A,C,F区出口的时候，此交通要道已经被警察封锁即可。假设警察从接到报警开始封锁路口需要的时间为；罪犯逃跑到路口所需要的时间为。只要不等式恒成立即可。首先通过Floyd算法，利用MATLAB进行编程分别计算出，P点到A,C,F区各个出口的最短路径以及全市80个交通警卫平台到各个出口的最短路径。然后通过非平衡指派问题模型，将80个交通警卫平台利用LINGO软件对A,C,F区的出口进行分配。由于一个出口可能分配到多个警卫平台，此时取最短路径较短的平台。分别计算32号站台到各个出口的时间与各个交通警卫平

27、台到自己分配的出口的时间，并进行比较，得到结果如下：表6- 2 罪犯最短逃逸时间（60km/h）出口最短路径时间/min出口最短路径时间/min1213.813.820321.821.81410.010.024820.520.52113.313.326427.027.02315.315.331725.225.22414.414.448327.027.0289.09.054124.924.9299.29.257221.721.717725.325.357830.830.820227.927.9/表6- 3封锁ACF区交通要道最短用时出口平台最短路径时间/min出口平台最短路径时间/min1212

28、0020341444.414140024830373.72161868.626429666.6231350.531744555.52467777.748378002815484.854179707.02936797.957280171.717738909.057874585.820240656.5/ 通过观察表6-2和表6-3中的最短时间可以发现，当罪犯的逃逸速度为60km/h时可以在罪犯逃出ACF区之前完成封锁；如果罪犯的逃逸速度为80km/h;90km/h；100km/h时,在ACF区的盲点位置始终存在封锁迟于逃逸的情况。七、模型评价7.1模型的优缺点7.1.1模型的优点1. 在使用Flo

29、yd最短路径算法前，利用求平台到各对应辖区节点的距离应小于3km的的思想排除大量不必要的交通节点，实现运算的优化。2. 利用Floyd算法而非采用常规的Dijkstra算法，达到优化求解最短路径运算的目的。3. 依据指派问题模型原理建立的路口封锁分配模型简化了问题的求解思路。4. 在对P点罪犯的搜捕问题中给出两种方案，保证搜捕工作的万无一失，符合实际。5. 在罪犯搜捕模型中方案结合实际情况，确定罪犯在逃逸时间内的活动范围，缩小了封锁范围，并且减少了调用的警力资源，便于后续的搜捕工作的开展。6. 在罪犯搜捕模型中方案，除了考虑逃逸速度为80km/h的情况，还考虑了逃逸速度大于80km/h的情况，

30、增大了模型的适用范围。7.1.2模型的缺点1. 在辖区范围规划模型中，只依据一个简单的标准进行划分，无法充分结合实际，也没有给出最优的辖区规划方案。2. 在对P点罪犯的搜捕问题中，A方案只考虑了逃逸速度为80km/h的情况，而没有考虑逃逸速度大于80km/h的情况。八、参考文献1 龚劬图论与网络最优化算法M重庆：重庆大学出版社，20092 杜金玲，周杰关于几种不平衡指派问题的修正匈牙利解法J价值工程，120-121，20103 邓薇MATLAB函数速查手册 北京：人民邮电出版社，2010附录A区路线图绘制函数function =ti2huatu()clearx=413403383.538133

31、9335317334.5333282247219225280290337415432418444251234225212227256250.5243246314315326327328336336331371371388.5411419411394342342325315342345348.5351348370371354363357351369335381391392395398401405410408415418422418.5405.5405409417420424438438.5434438440447448444.5441440.5445444;y=359343351377.5376

32、383362353.5342325301316270292335328335371374394277271265290300301306328337367351355350342.5339334335330333330.5327.5344343346342348372374372382380.5377369363353374382.5387382388395381375366361362359360355350351347354356364.5368370364370372368373376385392392381383385381.5380360;plot(x(1:20),y(1:20),b

33、o);hold onplot(x(21:92),y(21:92),r*);for k=1:92 text(x(k)+1,y(k)+1,sprintf(%d,k),fontsize,12 );endD=zeros(92,92);D(1,69)=1;D(1,74)=1;D(1,75)=1;D(1,78)=1;D(2,40)=1;D(2,43)=1;D(2,44)=1;D(2,70)=1;D(3,44)=1;D(3,45)=1;D(3,55)=1;D(3,65)=1;D(4,39)=1;D(4,57)=1;D(4,62)=1;D(4,63)=1;D(5,47)=1;D(5,49)=1;D(5,50)

34、=1;D(6,47)=1;D(6,50)=1;D(7,15)=1;D(7,32)=1;D(7,34)=1;D(7,47)=1;D(8,9)=1;D(8,33)=1;D(8,46)=1;D(8,47)=1;D(9,8)=1;D(9,34)=1;D(9,35)=1;D(10,26)=1;D(10,34)=1;D(11,25)=1;D(11,26)=1;D(11,22)=1;D(12,25)=1;D(12,27)=1;D(13,22)=1;D(13,23)=1;D(13,24)=1;D(14,16)=1;D(14,21)=1;D(15,7)=1;D(15,28)=1;D(15,31)=1;D(16,

35、14)=1;D(16,36)=1;D(16,38)=1;D(17,41)=1;D(17,40)=1;D(17,42)=1;D(17,81)=1;D(18,73)=1;D(18,80)=1;D(18,81)=1;D(18,83)=1;D(19,77)=1;D(19,79)=1;D(20,85)=1;D(20,86)=1;D(20,89)=1;D(21,14)=1;D(21,22)=1;D(22,11)=1;D(22,13)=1;D(22,21)=1;D(23,13)=1;D(24,13)=1;D(24,25)=1;D(25,11)=1;D(25,12)=1;D(25,24)=1;D(26,10)

36、=1;D(26,11)=1;D(26,27)=1;D(27,12)=1;D(27,26)=1;D(28,15)=1;D(28,29)=1;D(29,28)=1;D(29,30)=1;D(30,29)=1;D(30,48)=1;D(31,15)=1;D(31,32)=1;D(31,34)=1;D(32,7)=1;D(32,31)=1;D(32,33)=1;D(33,8)=1;D(33,32)=1;D(33,34)=1;D(34,9)=1;D(34,10)=1;D(34,7)=1;D(34,31)=1;D(34,33)=1;D(34,37)=1;D(35,9)=1;D(35,36)=1;D(35,

37、45)=1;D(36,16)=1;D(36,35)=1;D(36,37)=1;D(36,39)=1;D(37,34)=1;D(37,36)=1;D(38,16)=1;D(38,39)=1;D(38,41)=1;D(39,4)=1;D(39,36)=1;D(39,38)=1;D(39,40)=1;D(40,2)=1;D(40,17)=1;D(40,39)=1;D(41,17)=1;D(41,38)=1;D(41,92)=1;D(42,17)=1;D(42,43)=1;D(43,2)=1;D(43,42)=1;D(43,70)=1;D(43,72)=1;D(44,2)=1;D(44,3)=1;D(

38、44,67)=1;D(45,3)=1;D(45,35)=1;D(45,46)=1;D(46,8)=1;D(46,45)=1;D(46,55)=1;D(47,5)=1;D(47,6)=1;D(47,7)=1;D(47,8)=1;D(47,48)=1;D(48,30)=1;D(48,47)=1;D(48,61)=1;D(49,5)=1;D(49,50)=1;D(49,53)=1;D(50,5)=1;D(50,6)=1;D(50,49)=1;D(50,51)=1;D(50,59)=1;D(51,50)=1;D(51,52)=1;D(51,59)=1;D(52,51)=1;D(52,53)=1;D(5

39、2,56)=1;D(53,49)=1;D(53,52)=1;D(53,54)=1;D(54,53)=1;D(54,55)=1;D(54,63)=1;D(55,3)=1;D(55,46)=1;D(55,54)=1;D(56,52)=1;D(56,57)=1;D(57,4)=1;D(57,56)=1;D(57,58)=1;D(57,60)=1;D(58,57)=1;D(58,59)=1;D(59,50)=1;D(59,51)=1;D(59,58)=1;D(60,57)=1;D(60,61)=1;D(60,62)=1;D(61,48)=1;D(61,60)=1;D(62,4)=1;D(62,60)=

40、1;D(62,85)=1;D(63,4)=1;D(63,54)=1;D(63,64)=1;D(64,63)=1;D(64,65)=1;D(64,76)=1;D(65,3)=1;D(65,64)=1;D(65,66)=1;D(66,65)=1;D(66,67)=1;D(66,76)=1;D(67,44)=1;D(67,66)=1;D(67,68)=1;D(68,67)=1;D(68,69)=1;D(68,75)=1;D(69,1)=1;D(69,68)=1;D(69,70)=1;D(69,71)=1;D(70,2)=1;D(70,43)=1;D(70,69)=1;D(71,69)=1;D(71,

41、72)=1;D(71,74)=1;D(72,43)=1;D(72,71)=1;D(72,73)=1;D(73,18)=1;D(73,72)=1;D(73,74)=1;D(74,1)=1;D(74,71)=1;D(74,73)=1;D(74,80)=1;D(75,1)=1;D(75,68)=1;D(75,76)=1;D(76,64)=1;D(76,66)=1;D(76,75)=1;D(76,77)=1;D(77,19)=1;D(77,76)=1;D(77,78)=1;D(78,1)=1;D(78,77)=1;D(78,79)=1;D(79,19)=1;D(79,78)=1;D(79,80)=1;

42、D(80,74)=1;D(80,79)=1;D(80,18)=1;D(81,17)=1;D(81,18)=1;D(81,82)=1;D(82,81)=1;D(82,83)=1;D(82,90)=1;D(83,18)=1;D(83,82)=1;D(83,84)=1;D(84,83)=1;D(84,85)=1;D(84,89)=1;D(85,62)=1;D(85,84)=1;D(85,20)=1;D(86,20)=1;D(86,87)=1;D(86,88)=1;D(87,86)=1;D(87,88)=1;D(87,92)=1;D(88,86)=1;D(88,87)=1;D(88,88)=1;D(8

43、8,91)=1;D(89,20)=1;D(89,84)=1;D(89,90)=1;D(89,88)=1;D(90,89)=1;D(90,82)=1;D(90,91)=1;D(91,88)=1;D(91,90)=1;D(91,92)=1;D(91,87)=1;D(92,41)=1;D(92,91)=1;D(92,87)=1;fori=1:92for j=1:92if D(i,j)=1 line(x(i),x(j),y(i),y(j) %画连线图 %line(1,2,3,4)将画出（1,3）到(2,4)的一条直线，而不是(1,2)到(3,4)。 D(i,j)=sqrt(x(i)-x(j)2+(y(

44、i)-y(j)2);endendend封锁路线绘制函数function = zhuibuluxian( juzhen1,B,AAA,BBB )%UNTITLED 此处显示有关此函数的摘要% 此处显示详细说明hold on;fori=1:20 xian1= mydijkstra2(juzhen1,i,B(i); ,t=size(xian1);for j=2:t line(AAA(xian1(j),AAA(xian1(j-1),BBB(xian1(j),BBB(xian1(j-1),linewidth,4,color,r);hold on;endendend总图绘制函数function = qua

45、ntu(B,AAA,BBB,A,C)%UNTITLED 此处显示有关此函数的摘要% B为80个警察的列，AB为节点连接的XYfori=1:582plot(AAA(i),BBB(i),r*);hold on;endhold on;fori=1:80plot(AAA(B(i),BBB(B(i),bo);hold on;endhold on;fori=1:928 line( AAA(A(i),AAA(C(i),BBB(A(i),BBB(C(i) );endhold on;fori=1:582 text( AAA(i)+1,BBB(i)-1,sprintf(%d,i),fontsize,7 );endend追捕路线绘制函数function = dian56(B,AAA,BBB,A,C)%UNTITLED 此处显示有关此函数的摘要% B为56个点的列，AB为节点连接的XYfori=1:56plot(AAA(B(i),BBB(B(i),*);hold on;endhold on;m=1;fori=1:928for j=1:56if(A(i)=B(j)k(m)=i; m=m+1;endendend,t=size