基于二部图匹配算法的围堵模型

史鲁杰 郭昱宇 朱丽梅

【摘要】 针对目前个别地区街面极端犯罪活动的高发性，本文基于二部图理论，以匈牙利算法进行匹配分析，建立了围堵犯罪嫌疑人的数学模型。将某市交通路线及路口数据转化成图，利用二部图匹配的方法计算出接警后巡警围堵成功的最短时间和最佳方案，提高巡警对犯罪活动的打击力度。同时，该模型利用计算机编程实现，具有良好的推广价值。

【关键词】 犯罪围堵 二部图 Floyd算法 匈牙利算法

一、引言

目前个别城市重点区域的极端犯罪活动呈现高发性。城市火车站、地铁站、地标建筑等易成为极端分子的犯罪场所，因此许多城市加派警力巡逻检查。但警力资源是有限的，特别是当发生重大案件和紧急情况，如果不能及时围堵犯罪嫌疑人，会对整个城市治安造成重大负面影响。本文建立起一种直接高效的围堵模型，基于某市交通网络数据，给出巡警对犯罪嫌疑人的围堵方案，力争最短时间内处理犯罪活动。

本文研究了对犯罪嫌疑人的围堵方案。假设某市路口P处发生了重大刑事案件[1]。在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速围堵搜捕嫌疑犯，设计调度巡警警力资源的最佳围堵方案。

二、方案建立

2.1、二部图的转化

交通网络数据可抽象成无向图。以路口为顶点，路口之间有直接道路则记为有边，否则无边。全市交通网络可形成包括582个顶点，928条边的稠密图[2]，记做G。以每条边长为权值，构建该图带权邻接矩阵。本文利用Floyd算法计算每两个顶点之间的最短距离，形成图的带权邻接矩阵E582×582，为下一步二部图匹配形成数据基础。考虑到本算例邻接矩阵过大，本文给出部分邻接矩阵的数据。（图1、2）

假设当该市某路口发生突发案件时，调度中心在案发3分钟后接到报警，并立即调度巡警警力围堵嫌疑犯。调度中心已知接警时各个巡警的所在位置，巡警警车在嫌疑犯车辆行驶3分钟后出发。嫌疑犯的逃跑路线和逃跑距离是随机的。对任意时间，嫌疑犯的位置均不确定。

但在逃跑速度一定的情况下，对于任意时间t（分钟），嫌疑犯驾车逃跑的所能到达的最大范围是确定的[3]，即可知嫌疑犯逃跑范围的边界路口。若给定时间（t-3），当巡警能够从所在位置到达逃跑范围中的所有边界路口，即认为围堵成功[4]。

2.2匹配算法分析

取时间t内嫌疑犯所有可能行驶路线中所包含路口节点的并集，记为P；将P的边界点集记为P'。接警时巡警所在路口节点的并集记做Q。在集合P'和Q之间做最大匹配。可完全匹配时，即最佳围堵方案。

所谓二部图就是顶点集合V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集的特殊无向图[5]。

所以，可以将交通网络中的节点分为警察部署的节点与疑犯可能到达的节点[6]。用t表示警方追捕的时间，则嫌疑犯的逃跑时间为t+3。

首先构建嫌疑犯位置与警察位置的关系矩阵A，A[i][j]=1时说明到t时刻j点的警察能逮捕到i点的嫌疑犯，然后对A用匈牙利算法做最大匹配，将匹配的结果记录在二维矩阵PP中。

其中，利用匈牙利算法匹配的具体算法实现过程如下：

Step1：首先置二维矩阵PP为空，然后任意给y个匹配给PP；

Step2：若PP已饱和则算法结束，否则跳到step3步 （所谓饱和点就是结点i已找到匹配j）；

Step3：在PP取一个非饱和结点xi，将xi并入空集合y中；

Step4：取与xi关联的并且未标记的结点yy；

Step5：若yy已饱和，则将与yy匹配的结点Z并入集合y，并标记yy跳向step4。若yy未饱和，则做一条从xi到yy的可增广路P，将PP与P的异或结果赋给PP，跳向step2。

三、算例结果

根据上述算法，利用C语言编程[7][8]，可计算得案发3分钟后的围堵调度方案及时间，具体结果见表1。

交巡警在接到报警后最长用时3.8922分钟，可将嫌疑犯完全围堵。

对于任意路口发生的犯罪案件，二部图匹配模型不仅能够快速给出围堵的警力调度方案，同时还能计算理论上的围堵所需时间[9][10]。

在已知交通网络数据的情况下，只需给出案件发生的路口位置和嫌疑犯的逃跑速度[11]，从接到报警到得出调度方案的过程由计算机程序来处理，大大缩短了警力的反应时间，为更快的抓捕嫌疑犯提供科学的围堵方案。

四、结语

和谐稳定和依法治国是我国当今社会的主题，而恐怖活动和极端犯罪的多发对社会治安构成严重威胁。本文提出借用图论理论给出围堵犯罪嫌疑人逃逸的数学模型，直接快捷，贴近实际围堵情况。模型利用计算机编程，实现过程高效快速，可为警务部门围堵罪犯提供参考。同时，模型及算法在消防、急救、公交规划等方面具有一定推广价值。

参 考 文 献

[1]全国大学生数学建模竞赛组委会.2011年竞赛题[EB/OL].http：//www.mcm.edu.cn

[2]郑继明，姚翀.围堵在逃嫌疑犯的优化模型研究.科学技术与工程，2012，12（33）：8980-8983

[3]陈驰，任爱珠.消防站布局优化的计算机方法，清华大学学报：自然科学版，2003，43（10）：1390-1393

[4]殷代君.广义最大覆盖模型在应急设施选址中的应用研究.中外企业家，2010，3：169-170

[5]图论算法理论、实现及应用.王桂平，王衍，任嘉辰.北京：北京大学出版社，2001.1

[6]陈仁爱，刘婷，冯贤财，等.基于优化模型的街面逃逸犯罪嫌疑人的围堵方案探讨.科技信息，2012，3：65-66

[7]林祖顺，李坚，叶欣杰，等.基于“关键点封锁”数学模型的围堵逃犯问题研究.福建电脑，2012，1：54-56

[8]吴美文.基于离散定位模型的城市消防站优化布局方法，系统仿真技术，2006，2（1）：58-62

[9]董金哲.罪犯围捕中的数学方法.科技创新导报，2012（16）：255-256

[10]陈艳艳，郭国旗.城市消防站的优化布局.消防科技，1999，（1）：26-28

[11]周安银，尹锐.交巡警未来发展趋势的思考.重庆城市管理学院学报，2011，11（4）：24-25