2011 国赛B答案 个人计算版

jerrybond6

第一部分：
(1) 管辖区划分：   （贪心算法）
交巡警服务平台        所管辖路口节点
A1          1 67 68 69 71 73 74 75 76 78
( u) b! q- f( p$ b4 H* [5 KA2            2 39 40 43 44 70 72
& j* N7 A4 h4 ]7 c0 S: cA3          3 54 55 65 66
A4          4 57 60 62 63 64
1 ~4 y9 m$ X3 h4 v. R! g5 e: gA5          5 49 50 51 52 53 56 58 59
4 V" v) Q7 Q# Q" D$ ?2 G( ^5 zA6          6
A7      7 30 32 47 48 61
  T6 P+ _$ S" T9 _, Z7 L- n. B2 fA8          8 33 46
A9          9 31 34 35 45
A10         10
A11  11 26 27
A12        12 25
- _/ G7 s) r0 g* O0 a6 uA13        13 21 22 23 24
A14        14
. \$ O+ H' l# q* O( G* HA15        15 28 29
* s# g. [* {2 v, {* Y: s; B+ LA16        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条交通要到全封锁最快方案： （二分答案+网络流（二分图匹配匈牙利算法亦可）验证）
& o3 m/ l( |; I1 X对A区13条交通要道实现全封锁的最短时间为：8.02 min
调度方案                               警方达到关键路口的最短路径        警方达到关键路口的所需时间
A1封锁路口节点62                         1 75 76 64 63 4 62                                 4.89
$ y0 ^& Q& E9 O0 i9 RA2封锁路口节点28                                   2 40 39 38                                 3.98
4 d* K# l; A3 r$ a( F" mA3封锁路口节点16                                3 45 35 36 16                                 6.03
A4封锁路口节点48                           4 57 58 59 51 50 5 47 48                 7.40
1 c9 j$ a0 p+ E/ F( m6 MA5封锁路口节点30                                    5 47 48 30                                 3.18
9 E+ [$ f0 R, W2 nA7封锁路口节点29                                     7  30 29                                 8.02
; E# P; c+ g0 r% ?- AA10封锁路口节点22                                   10 26 11 22                                 7.71
$ ?4 b# ?2 y: fA11封锁路口节点24                                       11 25 24                                 3.81
A12封锁路口节点23                                   12 25 24 13 23                         6.48
$ |$ J6 @& }' g+ [* U, _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

# Z8 G: M% x! H2 y( N9 \(3)增设交巡警服务平台的节点：         29、39、61、92


4 k2 T% U7 A7 K* ?& y
第二部分：
(1) 综合评价合理性，设计新方案(模糊数学，隶属度函数创建，综合评价值=适应度函数，用遗传算法重新布局)
; K* S7 E7 D0 E& j/ z5 d计算结果略，不同模型，不同结果，非定论。

) n$ ^* z2 r% u+ n  ~% o" ]# ?* a* Z(2)最佳围堵方案(dijkstra算法，匈牙利算法，二分，等步长时间枚举模拟验证)
2 c0 M2 L% X3 S' Q编写基于dijkstra算法的模拟程序，确定逃犯的活动范围。
( {9 H$ X1 i5 b0 J* y7 b进一步确定逃犯可能的活动区域的轮廓。
$ \( y, h% M4 M* w+ l; E- X用第一部分(2)中的算法确定最短围堵时间。
- j7 a% @$ B( L逃犯逃出该城市的最短时间为22min.
从3---22min,以0.1min为步长枚举验证可行解。
从可行解中找出最有方案。

最佳围堵方案：用时10.22min, 调用平台数目:33个， 具体如下：
/ V0 U/ c6 C, I& z7 f/ o$ R
7 y- j: p2 H' ?, S2 Z6 D调度方案          警方达到关键路口的最短路径        警方达到关键路口的所需时间
0 {0 W2 g  \% L2 ?9 RA11封锁路口节点471        11 25 12 471        10.19
  j& k' a2 o$ fA12封锁路口节点468        12 25 24 470 469 468        8.75
. @* e  [5 d# n8 y. IA13封锁路口节点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
8 C# p, o8 U+ xC3封锁路口节点183                168 189 192 193 194 175 196 183        9.06
4 {" U* n5 R0 pC5封锁路口节点306                170 273 274 179 296 297 306        8.69
C7封锁路口节点204                172 226 224 223 222 178 204        9.62
0 P# l8 o4 t" ^: RC9封锁路口节点210                174 213 212 211 210        7.10
% c4 x* b, s1 {) xC10封锁路口节点199        175 196 198 199        5.51
C11封锁路口节点184        176 184        1.41
C12封锁路口节点177        177 177        0.00
! {# x4 I2 t: D6 d: P/ t( o7 E. r4 pC13封锁路口节点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
( V5 f: k- Y2 Z. {0 j/ c) ~D1封锁路口节点369                320 349 368 369        4.88
D2封锁路口节点250                321 368 369 248 249 167 250        10.22
% b7 C7 h4 v5 N. w4 n. U5 MD3封锁路口节点349                322 367 359 358 321 355 350 320 349        5.41
4 i! |% M8 N0 UD7封锁路口节点248                326 347 320 349 368 369 248        9.46
3 c7 I3 c0 O/ s2 Q: hE1封锁路口节点460                372 23 383 460        4.56
E2封锁路口节点373                373 373        0.00
E3封锁路口节点374                374 374        0.00
: g8 v" A, }: m" s- u  l& e2 E' kE4封锁路口节点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
: M; G) I( }7 \5 FF2封锁路口节点526                476 544 543 536 528 527 525 526        6.32
5 Y6 d/ {: l+ w3 Q0 g4 e4 nF3封锁路口节点512                477 500 502 504 505 513 512        8.66

xiaocheng2016

谢谢楼主！！！！！！！！！！！！

二泉映月

pyppinbo 发表于 2011-9-13 20:59
( ?# Z4 F+ }: d5 y7 G2个平台。。。。

2个平台时必要加的，随便想都是平台越多越好，加了4个的只是效果和5个差不了多少，这个东西看你谈什么方面

二泉映月

baivfhpiaqg 发表于 2011-9-12 23:24
- ]0 K4 f5 t! c7 ~! a2 N2 n不大明白……
3 ]) T  ^0 Y; L$ W; c* G0 ~$ o: m进行全封锁和C区有什么关系呢
跑到C区的就30和48俩个要道。。。我在最短时间内进行封锁即 ...

可以和C区的联合封锁啊

wuyuwenxmyz

楼主，真是牛人啊！

munich

一切等着看结果吧。。。

jerrybond6

?????????????????????????????????????

Tobielf

顶起，同时很挫的发现，自己第二问 二小问思路和 评分标准是一样的，但是编码实现的时候有点问题，悲剧吖！不合格的程序员，无证程序员啊！！
好伤心，希望15号的HNCPC能顺利一点！
8 H8 c: B/ x5 f, @回来再把数模的算法纠正下看看结果
LZ你就尽情的BS我吧

pyppinbo

2个平台。。。。

wen2316058

围观，表示也是做的B题，但是没同学你做的好啊。。。。