罪犯围捕中的数学方法

董金哲

摘 要:本文在图论的基础上建立了围捕犯罪嫌疑人的模型,该模型分为三个子模型:“封锁可行性模型”,“逃窜分层模型”和“交巡警分配模型”。“封锁可行性模型”可以确定包围圈,但是会产生封锁盲点(巡警无法封锁的路口,形成包围圈的漏洞)和封锁重复点(多个巡警封锁同一个路口,造成警力浪费及其它不良影响)。“逃窜分层模型”可以消除封锁盲点,彻底封锁逃逸线路;“交巡警分配模型”可以消除封锁重复点,解决警力资源浪费等缺点。

关键词:图论Floyd算法整数规划罪犯围捕

中图分类号:01 文献标识码:A 文章编号:1674-098X(2012)06(a)-0255-02

Mathematical Methods in Criminals Stalling

DONG Jin-zhe

(North China Electric Power University,Baoding, China)

Abstract: In this paper, a criminals stalling model based on graph theory and integer optimization is set up.This model is divided into three submodel: blockade feasibility model, runaway hierarchy model and constable assignment model. Blockade feasibility model can determine the encirclement, but with some unblocking crossing and some crossing is repetitive sealed. Runaway hierarchy model can deal with the unblocking crossing. Constable assignment model can remove repetitive sealed crossing.

Key Words:graph Theory;Floyd arithmetic;integer optimization;criminals stalling

1 围捕方法的建立

整个围捕模型是建立在图论与整数规划理论[1]的基础之上的,设城区有个路口,个交警服务站,根据图论,可将城市的交通网络抽象成一个无向图[2-4],线表示道路,点表示路口。即可分为三个子模型,分别为:“封锁可行性模型”,“逃窜分层模型”和“交巡警分配模型”。

1.1 封锁可行性模型

本模型主要讨论,某一时刻对逃犯所处范围进行封锁的可行性,最终确定哪些交巡警平台可以成功封锁哪些逃窜路口。

首先通过Floyd算法[5],求出节点间距离矩阵和,其中向量表示案发路口到其他个路口的最短距离:

矩阵表示个路口到个交巡警平台的最短距离,其中向量表示第个交巡警平台与个路口的最短距离向量:

（1）

建立0-1判别矩阵,设犯罪嫌疑人从被发现到开始围捕驾车可行驶的路程为,将加上;之后用减去。若结果小于0,则,表示交巡警平台能够在犯罪嫌疑人到达之前堵住该路口;若元素大于0,则,表示交巡警平台不能在犯罪嫌疑人到达之前封锁该路口。

（2）

通过判定矩阵可以看出,逃犯所在范围的外围路口:有的路口,无法赶在逃犯到达之前封锁,称为“封锁盲点”;有的路口可以对应多个可用的交巡警平台,这些路口称为“封锁重复点”。对于“封锁盲点”的问题,将在“逃窜分层模型”中处理。对于“封锁重复点”的问题,将在“交巡警分配模型”中进行处理。

1.2 逃窜分层模型

本模型可以对“封锁可行性模型”中的“封锁盲点”问题进行处理。

首先設定0-1关联矩阵,其元素表示:路口与路口通过公路直接相连;若元素,说明路口与路口不直接相连。

将逃犯逃窜距离后可以到达的路口集合设定为向量,包括个路口,每个路口记为:

通过以上的“封锁可行性模型”,得到判定矩阵;由可以看出,一层包围圈是否能封锁逃犯所处的所有区域。当逃犯从第一层包围圈的漏洞逃出以后,立即启用下一层“封锁可行性模型”——即“逃窜分层模型”相当于“封锁可行性模型”的一个序列。

选取第一层当中,不能成功封锁的路口,作为新的集合;与通过公路直接连接的点,作为新集合;取“非”集合与“”的交集,作为:

代表:通过前一层次中不能封锁的路口,向外逃窜,并且通过一条公路直接连接的路口组成的集合。

假设中有个路口,再次以这些路口为逃犯出发点,可以得到个新的距离向量,作为一个序列,合称:

以中的每个向量,按照“封锁可行性模型”再次计算,以此类推,一直到某一层没有“封锁盲点”为止。

1.3 交巡警分配模型

本模型主要解决两个问题,一是一个路口可能有多个交巡警平台对其进行封锁,二是一个交巡警平台可以封锁多个路口。我们构建二维整数目标规划[6,7],首先使每层被封锁的路口达到最大,其次是封锁各层时交巡警的移动距离达到最小。

设第层有个路口,总共有个交巡警服务平台可供调度,由此可从2.1封锁可行性模型中抽取出判别矩阵,其中:

由于一个交巡警平台智能被调度到一个路口,所以有约束:

同时建立一个实际调度矩阵,其中表示是否由第交巡警平台向第路口调度警力,其值为“1”时表示调度,为“0”时表示不调度。每个出口只需一名巡警,所以有:

每个巡警把守一个出口或者该巡警闲置,其中为距离矩阵,令:

第一目标是使每层尽可能多的路口被围堵,即:

第二目标是使封锁各层时交巡警的移动距离达到最小,即:

综上所述,总约束条件和目标函数为:

2 该方法的实际应用与检验

2.1 实际应用

下面,用该方法解决一个实际问题,并验证本方法的可行性。图1是某市区的交通图,其中实线表示市区道路;假设图中P点为嫌疑犯被发现的地点;从嫌疑犯被发现到开始围捕经过了3分钟;嫌疑人与巡警的移动速度均为30Km/h。

第一层,犯罪嫌疑人3分钟后能够达到的路口集合,包括13个点:33,7,31,34,8,30,9,35,46,47,48,36,45。

由关联矩阵,经过“逃窜分层模型”计算,得到下一层逃窜能够达到的路口编号。结合“封锁可行性模型”和“交巡警分配模型”,逐层计算,得到每一层包围圈,交巡警平台对每个路口的围堵具体方案

2.2 模型合理性检验

被封锁路口集合:

犯罪嫌疑人能够到达的路口集合:

犯罪嫌疑人能够到达的路口,用圆形符号(o)表示;交巡警最终封锁的所有路口,用星形(*)表示。包围散点图如图2。

3 结语

本为利用图论和整数规划的理论建立了一种在市区内围捕罪犯的方法,并且对一个实际的算例进行了求解,验证了该方法的可行性与可靠性。

参考文献

[1] (美)Frank R.Giordano,William P.Fox,Steven B.Horton,Maurice D.Weir,A First Course in Mathematical Modeling,北京:机械工业出版社,2009.8.

[2] R．B．巴帕特,朱尧辰,图与矩阵,国外科技新书评介,2011,9:7～8.

[3] 黄湘宁,祝延波,基于图论的节点分析,青海师范大学学报:自然科学版,2011,27(2):17～20.