2011 国赛B答案 个人计算版

jerrybond6

$ ~% o0 p; S- j# M* v- r第一部分：
(1) 管辖区划分：   （贪心算法）
交巡警服务平台        所管辖路口节点
. R8 o9 Z% N' ~+ |A1          1 67 68 69 71 73 74 75 76 78
& u6 ^' j. i! o* c3 d. [( c. |& D. QA2            2 39 40 43 44 70 72
A3          3 54 55 65 66
6 Z/ ~# F% S2 c" \- [A4          4 57 60 62 63 64
& _& [/ T0 B* _A5          5 49 50 51 52 53 56 58 59
) N. `) [+ P5 o4 o# z0 J! R4 ^! wA6          6
- Y9 m; t! O5 _/ g* K4 F; fA7      7 30 32 47 48 61
5 a8 j0 l$ ~9 {; KA8          8 33 46
A9          9 31 34 35 45
4 T" _! z. P$ R( TA10         10
; B7 ~: k# C5 S% ~A11  11 26 27
! x7 o( @5 q" B% ]# cA12        12 25
  u6 ], _; [" p; _! L/ g, |% A) A( {A13        13 21 22 23 24
8 h1 w7 g( c" Y: T4 IA14        14
) B7 o8 x7 h$ n6 mA15        15 28 29
: w- D2 `' G8 A' ~5 j5 s) vA16        16 36 37 38
A17        17 41 42
2 j! ?, Q2 v: X, F5 Z/ nA18        18 80 81 82 83
8 I: |& Q2 R3 `: {) OA19        19 77 79
A20        20 84 85 86 87 88 89 90 91 92

(2)对A区13条交通要到全封锁最快方案： （二分答案+网络流（二分图匹配匈牙利算法亦可）验证）
对A区13条交通要道实现全封锁的最短时间为：8.02 min
4 ?. Y6 G0 O  H, u调度方案                               警方达到关键路口的最短路径        警方达到关键路口的所需时间
7 d* g2 l! y1 F' e2 w: WA1封锁路口节点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
- r. c/ ?0 Y+ S3 j# u6 r; {% sA5封锁路口节点30                                    5 47 48 30                                 3.18
' c* N3 A2 k( P% r2 A2 sA7封锁路口节点29                                     7  30 29                                 8.02
- \( o+ q/ k7 iA10封锁路口节点22                                   10 26 11 22                                 7.71
A11封锁路口节点24                                       11 25 24                                 3.81
/ o, k8 l4 H+ y# P. x# S/ qA12封锁路口节点23                                   12 25 24 13 23                         6.48
% i/ _* g, U- }$ I0 ^, l& qA13封锁路口节点12                                      13 24 25 12                         5.98
A14封锁路口节点21                                         14 21                                 3.26
9 G( H7 U5 B* K- y/ Y' vA15封锁路口节点28                                         15 28                                 4.75
A16封锁路口节点14                                         16 14                                 6.74
, E) E; z( H' v* K$ ^
: z/ Y( ?* D. m9 M3 N$ R2 Q(3)增设交巡警服务平台的节点：         29、39、61、92
" n9 h) L! D' z4 E% U: C; k7 n  h

, J# F' B4 s% J9 Z  `4 H3 e% b' o7 L, S
! c3 R& J* U* S6 i- w0 {/ i- u第二部分：
' Y- R3 P5 V& A0 p/ L(1) 综合评价合理性，设计新方案(模糊数学，隶属度函数创建，综合评价值=适应度函数，用遗传算法重新布局)
计算结果略，不同模型，不同结果，非定论。
$ p! I6 a6 I: e
: w! H) A* ]9 A, f" ~- Q1 v! p(2)最佳围堵方案(dijkstra算法，匈牙利算法，二分，等步长时间枚举模拟验证)
- ^( G& ]3 Y5 U! K2 A编写基于dijkstra算法的模拟程序，确定逃犯的活动范围。
进一步确定逃犯可能的活动区域的轮廓。
用第一部分(2)中的算法确定最短围堵时间。
$ k# x  ]( p% p1 i! K逃犯逃出该城市的最短时间为22min.
: I. {: C; p# W; A从3---22min,以0.1min为步长枚举验证可行解。
从可行解中找出最有方案。

最佳围堵方案：用时10.22min, 调用平台数目:33个， 具体如下：

调度方案          警方达到关键路口的最短路径        警方达到关键路口的所需时间
- k8 C; u: a. b  V& {8 ]( VA11封锁路口节点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
: v6 B) _+ ]" y" L6 {# H3 EC1封锁路口节点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
) A' @% u  y1 LC9封锁路口节点210                174 213 212 211 210        7.10
C10封锁路口节点199        175 196 198 199        5.51
C11封锁路口节点184        176 184        1.41
. f5 {+ r- n- JC12封锁路口节点177        177 177        0.00
; Z7 C/ K- o& o' m6 [2 ?( vC13封锁路口节点299        178 284 285 288 299        6.87
C14封锁路口节点268        179 292 294 272 271 270 269 268        6.56
6 C5 b& p4 U" L2 a9 a/ aC15封锁路口节点287        180 306 297 298 289 288 287        7.74
+ a- P* {. A) n0 r6 J/ y9 A; oC16封锁路口节点255        181 266 267 255        5.75
C17封锁路口节点286        182 293 292 295 296 290 285 286        8.05
* e! C5 P, V& R+ ^" w6 s4 PD1封锁路口节点369                320 349 368 369        4.88
D2封锁路口节点250                321 368 369 248 249 167 250        10.22
' s7 y8 V* k5 O1 ?D3封锁路口节点349                322 367 359 358 321 355 350 320 349        5.41
2 l# J1 e  i. HD7封锁路口节点248                326 347 320 349 368 369 248        9.46
E1封锁路口节点460                372 23 383 460        4.56
E2封锁路口节点373                373 373        0.00
4 m/ m% L4 f3 \" _) }  XE3封锁路口节点374                374 374        0.00
7 h# C3 K+ M* H2 E, j0 ?E4封锁路口节点378                375 424 425 426 427 378        4.62
E12封锁路口节点455        383 460 461 454 455        3.25
% Z; }9 G! h: l; e- u9 \F1封锁路口节点540                475 555 544 543 536 528 538 539 540        8.39
' [% l8 ~, _) Q0 }" NF2封锁路口节点526                476 544 543 536 528 527 525 526        6.32
F3封锁路口节点512                477 500 502 504 505 513 512        8.66

jerrybond6

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

不明白

baivfhpiaqg

楼主牛人……
/ h* i$ i1 W5 w7 R' x$ \1 Y第五问超牛……
( z' t: h8 Z9 R5 P6 I% I/ G  Z封锁方案那块结果差异很大。。
分享一下……
+ O' l$ N4 L: b" |) v5 b7 O0 K
服务平台标号        要道节点标号        到达最短时间（min）
2        38        3.9822
# @9 ~9 L' h0 v. Y, u+ x: f3 E4        62        0.35
5        48        2.4758
7        29        8.0155
8        30        3.0608
# s9 Q6 P/ J) G+ S" Q9        16        1.5325
10        22        7.708
9 [/ o9 X% ]( u3 H, `11        23        4.6751
, k* j; F+ t- f# Z1 z5 _- s12        12        0
13        24        2.3854
7 I6 }6 n9 q/ S' B" j  p1 r! T7 {14        21        3.265
/ v; G+ t; c" U( k+ p0 a# b2 C15        28        4.7518
16        14        6.7417

jerrybond6

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

jerrybond6

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

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

jerrybond6

baivfhpiaqg 发表于 2011-9-12 21:35
7 x# q. g1 l! j楼主牛人……
第五问超牛……
封锁方案那块结果差异很大。。

9 ~( s, a& ?+ o- m6 d2 B: U差异不大吧  你是8.1分钟  我是8.2   可能不同程序语言精度不同造成的 我是C++编程 另外 最大匹配也有多种方式 所有 结果是一样。

安树庭

楼主的想法很不错  呵呵 我也是做B题的 有几点我觉得可以值得商量一下  首先，**是管理点还是管理线段？   我们组通过计算发现   如果单纯把点划分给服务平台，会可能造成造成部分边没人管辖，比如ABCD一次在一条直线上，b属于A管辖  C属于D管辖   哪些线段BC归谁管辖呢？
( p3 u- A, ]7 R. Y8 a/ j
第二问我们也是8.02min   呵呵

第三问也是增设4个平台
- m  p6 {; p' \+ W) W/ M
第四问我们可能做的有点复杂了  我们利用第三问的模型，首先分析了6个城区的不合理性，还计算了哥哥城区应该在哪些地方增设平台，应该有点偏离组委会的意思
9 S  D  m) s+ R# C/ s( ^4 ?
最后一问我们用MATLAB仿真，计算得到了围堵路径  只需要调动ACF三个平台（共14名警力）的经历 共需要xmin   x好像是10左右  具体我忘记了  并且给出了维度路线  我们的唯独路线是个动态搜索过程，每个出动的警力有一条固定的路线

7 O( v( j9 |, M8 l
  ?* Y: e' o1 f# v  仅供交流   希望咱们都能取得好成绩  呵呵

安树庭

baivfhpiaqg 发表于 2011-9-12 21:35
' A) V) a! ]  S4 o: C楼主牛人……
第五问超牛……
/ l5 I" L9 M& s0 T1 k. J! E4 V7 _封锁方案那块结果差异很大。。

有可能跑到C区了 你的结果显然不合理

jerrybond6

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

# U7 G% z9 U$ {Orz    思路差不多