2011 国赛B答案 个人计算版

jerrybond6

第一部分：
0 u: q' S6 r9 v1 B(1) 管辖区划分：   （贪心算法）
5 T. O" }/ B/ v! _6 t' @2 G交巡警服务平台        所管辖路口节点
, ?7 I" C$ q1 d8 R, HA1          1 67 68 69 71 73 74 75 76 78
; R" b  {2 [9 `3 ^7 `4 gA2            2 39 40 43 44 70 72
- y) x% [6 Q5 c6 M0 ^' P' E# OA3          3 54 55 65 66
A4          4 57 60 62 63 64
! U" b4 U# c" ~1 }. XA5          5 49 50 51 52 53 56 58 59
  j; k( ^) g( _# n7 {/ V- {A6          6
A7      7 30 32 47 48 61
A8          8 33 46
A9          9 31 34 35 45
' B" c$ t; Y3 R, v- X7 P# PA10         10
( O* q8 c4 B2 y( ^; UA11  11 26 27
* }, ~9 D+ W6 O  I5 t6 b. gA12        12 25
' x5 C, V% n8 }& LA13        13 21 22 23 24
5 @8 G. B4 p2 M1 _) IA14        14
A15        15 28 29
A16        16 36 37 38
A17        17 41 42
A18        18 80 81 82 83
* O, G( o* s9 V, F% \3 DA19        19 77 79
A20        20 84 85 86 87 88 89 90 91 92

+ k3 C  M9 ?' E- L- y* r(2)对A区13条交通要到全封锁最快方案： （二分答案+网络流（二分图匹配匈牙利算法亦可）验证）
: y9 w4 _) X3 E4 K& e3 K对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
1 c  E# K& o! R) N8 j- X' eA7封锁路口节点29                                     7  30 29                                 8.02
: c" y$ H5 z8 H/ o" ]A10封锁路口节点22                                   10 26 11 22                                 7.71
A11封锁路口节点24                                       11 25 24                                 3.81
A12封锁路口节点23                                   12 25 24 13 23                         6.48
/ K+ A! Y8 F+ |A13封锁路口节点12                                      13 24 25 12                         5.98
  o: o5 v. u# a$ i1 ~5 H3 w6 {A14封锁路口节点21                                         14 21                                 3.26
A15封锁路口节点28                                         15 28                                 4.75
A16封锁路口节点14                                         16 14                                 6.74
2 W6 i! y* Z; n) O0 P3 Q
(3)增设交巡警服务平台的节点：         29、39、61、92
( c' F  T6 O6 O; v; X$ I/ U


第二部分：
(1) 综合评价合理性，设计新方案(模糊数学，隶属度函数创建，综合评价值=适应度函数，用遗传算法重新布局)
计算结果略，不同模型，不同结果，非定论。

: Y+ C- q4 X' Q5 d/ ~; }(2)最佳围堵方案(dijkstra算法，匈牙利算法，二分，等步长时间枚举模拟验证)
编写基于dijkstra算法的模拟程序，确定逃犯的活动范围。
5 e. V* x  W* F0 c& e4 |进一步确定逃犯可能的活动区域的轮廓。
8 q$ L( r$ Z0 a, M# A6 w用第一部分(2)中的算法确定最短围堵时间。
逃犯逃出该城市的最短时间为22min.
3 I, n' L8 D0 Y9 p+ m从3---22min,以0.1min为步长枚举验证可行解。
从可行解中找出最有方案。
2 A( f9 y$ ^* g
最佳围堵方案：用时10.22min, 调用平台数目:33个， 具体如下：
3 t6 f1 G, F: A7 ~9 r* u6 T6 m
; X6 r" D& @) b( \3 Q调度方案          警方达到关键路口的最短路径        警方达到关键路口的所需时间
A11封锁路口节点471        11 25 12 471        10.19
A12封锁路口节点468        12 25 24 470 469 468        8.75
9 S; g7 R# I( k7 YA13封锁路口节点463        13 23 383 460 462 463        6.51
0 @% W$ o8 `) l/ E% u! i  SC1封锁路口节点307         166 181 308 307        5.69
C2封锁路口节点180                167 255 256 257 270 180        9.67
- [% O7 k# [  w# GC3封锁路口节点183                168 189 192 193 194 175 196 183        9.06
! [" `6 m: U% u! b1 Y: f4 iC5封锁路口节点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
$ T& {2 H9 W! aC10封锁路口节点199        175 196 198 199        5.51
/ s8 a$ {  X6 l- V8 jC11封锁路口节点184        176 184        1.41
/ e. h$ Z7 f( a5 p8 g0 KC12封锁路口节点177        177 177        0.00
C13封锁路口节点299        178 284 285 288 299        6.87
# ~) c% k- F+ q: ~& D9 V/ R6 wC14封锁路口节点268        179 292 294 272 271 270 269 268        6.56
C15封锁路口节点287        180 306 297 298 289 288 287        7.74
5 V& a3 r0 ?& N- s3 p2 ?  r6 AC16封锁路口节点255        181 266 267 255        5.75
; L& u/ b6 P* c2 [' E( CC17封锁路口节点286        182 293 292 295 296 290 285 286        8.05
, O; t( c1 v, ED1封锁路口节点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
# w2 Q8 M% \9 _5 G$ M7 fD7封锁路口节点248                326 347 320 349 368 369 248        9.46
/ Y6 h3 Y  Z# H1 Y+ K2 n+ X' QE1封锁路口节点460                372 23 383 460        4.56
& E" v7 J/ j1 S! PE2封锁路口节点373                373 373        0.00
E3封锁路口节点374                374 374        0.00
9 l% a' g* F1 s3 C, ^+ GE4封锁路口节点378                375 424 425 426 427 378        4.62
3 @4 U7 u0 h5 x9 O9 bE12封锁路口节点455        383 460 461 454 455        3.25
F1封锁路口节点540                475 555 544 543 536 528 538 539 540        8.39
; t1 p+ m' |& ?" E+ C# i. AF2封锁路口节点526                476 544 543 536 528 527 525 526        6.32
F3封锁路口节点512                477 500 502 504 505 513 512        8.66

jerrybond6

以上为个人计算结果，仅供娱乐。

不明白

baivfhpiaqg

楼主牛人……
" u+ v1 w. L% f/ v! ?' J8 g6 J第五问超牛……
  k  X. J4 K' e; S0 a& L: h$ k封锁方案那块结果差异很大。。
8 h/ Z0 i- A& a2 x: y分享一下……

* m/ v8 J; r5 a# Y4 m  l6 |5 u! h3 K服务平台标号        要道节点标号        到达最短时间（min）
( g+ ^# S' N4 V# ~2 ^% B' A/ \$ Y2        38        3.9822
: b7 D4 M5 k0 `4        62        0.35
9 f! `0 C6 c/ {* L% O& A, o! ]& K5        48        2.4758
! ^. P1 T, ^: t: V' |3 H7        29        8.0155
$ I5 n  X. e$ \8        30        3.0608
: T, V0 n4 E! f# ~# U& O$ N3 Y9        16        1.5325
10        22        7.708
9 E2 k1 C& L* u11        23        4.6751
) R8 q& \1 @* N+ V12        12        0
13        24        2.3854
14        21        3.265
15        28        4.7518
16        14        6.7417
% E2 |5 Y& _5 p& h6 s  b

jerrybond6

差异不大吧  你是8.1分钟  我是8.2   可能不同程序语言精度不同造成的 我是C++编程 另外 最大匹配也有多种方式 所有 结果是一样。

jerrybond6

baivfhpiaqg 发表于 2011-9-12 21:35
楼主牛人……
第五问超牛……
封锁方案那块结果差异很大。。

$ f/ y6 ~5 G$ M! M6 O差异不大吧  你是8.1分钟  我是8.2   可能不同程序语言精度不同造成的 我是C++编程 另外 最大匹配也有多种方式 所有 结果是一样。

jerrybond6

baivfhpiaqg 发表于 2011-9-12 21:35
- e3 m7 x+ r$ k' B$ T7 b楼主牛人……
+ n+ J, y. @- I; I; t第五问超牛……
封锁方案那块结果差异很大。。

* J  x3 A& |& |5 P$ ~. r. d差异不大吧  你是8.1分钟  我是8.2   可能不同程序语言精度不同造成的 我是C++编程 另外 最大匹配也有多种方式 所有 结果是一样。

安树庭

楼主的想法很不错  呵呵 我也是做B题的 有几点我觉得可以值得商量一下  首先，**是管理点还是管理线段？   我们组通过计算发现   如果单纯把点划分给服务平台，会可能造成造成部分边没人管辖，比如ABCD一次在一条直线上，b属于A管辖  C属于D管辖   哪些线段BC归谁管辖呢？
7 b7 g- u5 A! T8 S+ G6 Q
* R6 w% J: Y  n- J( @第二问我们也是8.02min   呵呵

% L5 U  R9 J2 L6 _) S& p第三问也是增设4个平台

7 w9 {! r1 g" a! Y. q第四问我们可能做的有点复杂了  我们利用第三问的模型，首先分析了6个城区的不合理性，还计算了哥哥城区应该在哪些地方增设平台，应该有点偏离组委会的意思
! }5 q* j6 E' v5 u
0 l( ?) u; a5 y, [; b; U最后一问我们用MATLAB仿真，计算得到了围堵路径  只需要调动ACF三个平台（共14名警力）的经历 共需要xmin   x好像是10左右  具体我忘记了  并且给出了维度路线  我们的唯独路线是个动态搜索过程，每个出动的警力有一条固定的路线
4 t+ g5 D. \( c! [7 D+ r( L$ f8 q

* d( \- d' v4 |1 J  仅供交流   希望咱们都能取得好成绩  呵呵

安树庭

baivfhpiaqg 发表于 2011-9-12 21:35
( x# ], n8 P* }( G; t6 K楼主牛人……
第五问超牛……
封锁方案那块结果差异很大。。

9 U$ j6 v2 x/ p3 |, C" b' `有可能跑到C区了 你的结果显然不合理

jerrybond6

安树庭 发表于 2011-9-12 22:14
楼主的想法很不错  呵呵 我也是做B题的 有几点我觉得可以值得商量一下  首先，**是管理点还是管理线段？    ...

Orz    思路差不多