2011 国赛B答案 个人计算版
第一部分：
(1) 管辖区划分： （贪心算法）
交巡警服务平台 所管辖路口节点
A1 1 67 68 69 71 73 74 75 76 78
A2 2 39 40 43 44 70 72
A3 3 54 55 65 66
A4 4 57 60 62 63 64
A5 5 49 50 51 52 53 56 58 59
A6 6
A7 7 30 32 47 48 61
A8 8 33 46
A9 9 31 34 35 45
A10 10
A11 11 26 27
A12 12 25
A13 13 21 22 23 24
A14 14
A15 15 28 29
A16 16 36 37 38
A17 17 41 42
A18 18 80 81 82 83
A19 19 77 79
A20 20 84 85 86 87 88 89 90 91 92
(2)对A区13条交通要到全封锁最快方案： （二分答案+网络流（二分图匹配匈牙利算法亦可）验证）
对A区13条交通要道实现全封锁的最短时间为：8.02 min
调度方案 警方达到关键路口的最短路径 警方达到关键路口的所需时间
A1封锁路口节点62 1 75 76 64 63 4 62 4.89
A2封锁路口节点28 2 40 39 38 3.98
A3封锁路口节点16 3 45 35 36 16 6.03
A4封锁路口节点48 4 57 58 59 51 50 5 47 48 7.40
A5封锁路口节点30 5 47 48 30 3.18
A7封锁路口节点29 7 30 29 8.02
A10封锁路口节点22 10 26 11 22 7.71
A11封锁路口节点24 11 25 24 3.81
A12封锁路口节点23 12 25 24 13 23 6.48
A13封锁路口节点12 13 24 25 12 5.98
A14封锁路口节点21 14 21 3.26
A15封锁路口节点28 15 28 4.75
A16封锁路口节点14 16 14 6.74
(3)增设交巡警服务平台的节点： 29、39、61、92
第二部分：
(1) 综合评价合理性，设计新方案(模糊数学，隶属度函数创建，综合评价值=适应度函数，用遗传算法重新布局)
计算结果略，不同模型，不同结果，非定论。
(2)最佳围堵方案(dijkstra算法，匈牙利算法，二分，等步长时间枚举模拟验证)
编写基于dijkstra算法的模拟程序，确定逃犯的活动范围。
进一步确定逃犯可能的活动区域的轮廓。
用第一部分(2)中的算法确定最短围堵时间。
逃犯逃出该城市的最短时间为22min.
从3---22min,以0.1min为步长枚举验证可行解。
从可行解中找出最有方案。
最佳围堵方案：用时10.22min, 调用平台数目:33个， 具体如下：
调度方案 警方达到关键路口的最短路径 警方达到关键路口的所需时间
A11封锁路口节点471 11 25 12 471 10.19
A12封锁路口节点468 12 25 24 470 469 468 8.75
A13封锁路口节点463 13 23 383 460 462 463 6.51
C1封锁路口节点307 166 181 308 307 5.69
C2封锁路口节点180 167 255 256 257 270 180 9.67
C3封锁路口节点183 168 189 192 193 194 175 196 183 9.06
C5封锁路口节点306 170 273 274 179 296 297 306 8.69
C7封锁路口节点204 172 226 224 223 222 178 204 9.62
C9封锁路口节点210 174 213 212 211 210 7.10
C10封锁路口节点199 175 196 198 199 5.51
C11封锁路口节点184 176 184 1.41
C12封锁路口节点177 177 177 0.00
C13封锁路口节点299 178 284 285 288 299 6.87
C14封锁路口节点268 179 292 294 272 271 270 269 268 6.56
C15封锁路口节点287 180 306 297 298 289 288 287 7.74
C16封锁路口节点255 181 266 267 255 5.75
C17封锁路口节点286 182 293 292 295 296 290 285 286 8.05
D1封锁路口节点369 320 349 368 369 4.88
D2封锁路口节点250 321 368 369 248 249 167 250 10.22
D3封锁路口节点349 322 367 359 358 321 355 350 320 349 5.41
D7封锁路口节点248 326 347 320 349 368 369 248 9.46
E1封锁路口节点460 372 23 383 460 4.56
E2封锁路口节点373 373 373 0.00
E3封锁路口节点374 374 374 0.00
E4封锁路口节点378 375 424 425 426 427 378 4.62
E12封锁路口节点455 383 460 461 454 455 3.25
F1封锁路口节点540 475 555 544 543 536 528 538 539 540 8.39
F2封锁路口节点526 476 544 543 536 528 527 525 526 6.32
F3封锁路口节点512 477 500 502 504 505 513 512 8.66 以上为个人计算结果，仅供娱乐。 {:3_41:}{:3_41:} 楼主牛人……
第五问超牛……
封锁方案那块结果差异很大。。
分享一下……
服务平台标号 要道节点标号 到达最短时间（min）
2 38 3.9822
4 62 0.35
5 48 2.4758
7 29 8.0155
8 30 3.0608
9 16 1.5325
10 22 7.708
11 23 4.6751
12 12 0
13 24 2.3854
14 21 3.265
15 28 4.7518
16 14 6.7417
差异不大吧 你是8.1分钟 我是8.2 可能不同程序语言精度不同造成的 我是C++编程 另外 最大匹配也有多种方式 所有 结果是一样。 baivfhpiaqg 发表于 2011-9-12 21:35 static/image/common/back.gif
楼主牛人……
第五问超牛……
封锁方案那块结果差异很大。。
差异不大吧 你是8.1分钟 我是8.2 可能不同程序语言精度不同造成的 我是C++编程 另外 最大匹配也有多种方式 所有 结果是一样。 baivfhpiaqg 发表于 2011-9-12 21:35 static/image/common/back.gif
楼主牛人……
第五问超牛……
封锁方案那块结果差异很大。。
差异不大吧 你是8.1分钟 我是8.2 可能不同程序语言精度不同造成的 我是C++编程 另外 最大匹配也有多种方式 所有 结果是一样。 楼主的想法很不错 呵呵 我也是做B题的 有几点我觉得可以值得商量一下 首先，**是管理点还是管理线段？ 我们组通过计算发现 如果单纯把点划分给服务平台，会可能造成造成部分边没人管辖，比如ABCD一次在一条直线上，b属于A管辖 C属于D管辖 哪些线段BC归谁管辖呢？
第二问我们也是8.02min 呵呵
第三问也是增设4个平台
第四问我们可能做的有点复杂了 我们利用第三问的模型，首先分析了6个城区的不合理性，还计算了哥哥城区应该在哪些地方增设平台，应该有点偏离组委会的意思
最后一问我们用MATLAB仿真，计算得到了围堵路径 只需要调动ACF三个平台（共14名警力）的经历 共需要xmin x好像是10左右 具体我忘记了 并且给出了维度路线 我们的唯独路线是个动态搜索过程，每个出动的警力有一条固定的路线
仅供交流 希望咱们都能取得好成绩 呵呵 baivfhpiaqg 发表于 2011-9-12 21:35 static/image/common/back.gif
楼主牛人……
第五问超牛……
封锁方案那块结果差异很大。。
有可能跑到C区了 你的结果显然不合理 安树庭 发表于 2011-9-12 22:14 static/image/common/back.gif
楼主的想法很不错 呵呵 我也是做B题的 有几点我觉得可以值得商量一下 首先，**是管理点还是管理线段？ ...
Orz 思路差不多