罪犯围捕中的数学方法
2012-04-29董金哲
董金哲
摘 要:本文在图论的基础上建立了围捕犯罪嫌疑人的模型,该模型分为三个子模型:“封锁可行性模型”,“逃窜分层模型”和“交巡警分配模型”。“封锁可行性模型”可以确定包围圈,但是会产生封锁盲点(巡警无法封锁的路口,形成包围圈的漏洞)和封锁重复点(多个巡警封锁同一个路口,造成警力浪费及其它不良影响)。“逃窜分层模型”可以消除封锁盲点,彻底封锁逃逸线路;“交巡警分配模型”可以消除封锁重复点,解决警力资源浪费等缺点。
关键词:图论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,则,表示交巡警平台不能在犯罪嫌疑人到达之前封锁该路口。……
