基于二部圖匹配算法的圍堵模型

史魯杰 郭昱宇 朱麗梅

【摘要】 針對(duì)目前個(gè)別地區(qū)街面極端犯罪活動(dòng)的高發(fā)性，本文基于二部圖理論，以匈牙利算法進(jìn)行匹配分析，建立了圍堵犯罪嫌疑人的數(shù)學(xué)模型。將某市交通路線及路口數(shù)據(jù)轉(zhuǎn)化成圖，利用二部圖匹配的方法計(jì)算出接警后巡警圍堵成功的最短時(shí)間和最佳方案，提高巡警對(duì)犯罪活動(dòng)的打擊力度。同時(shí)，該模型利用計(jì)算機(jī)編程實(shí)現(xiàn)，具有良好的推廣價(jià)值。

【關(guān)鍵詞】 犯罪圍堵 二部圖 Floyd算法 匈牙利算法

一、引言

目前個(gè)別城市重點(diǎn)區(qū)域的極端犯罪活動(dòng)呈現(xiàn)高發(fā)性。城市火車站、地鐵站、地標(biāo)建筑等易成為極端分子的犯罪場(chǎng)所，因此許多城市加派警力巡邏檢查。但警力資源是有限的，特別是當(dāng)發(fā)生重大案件和緊急情況，如果不能及時(shí)圍堵犯罪嫌疑人，會(huì)對(duì)整個(gè)城市治安造成重大負(fù)面影響。本文建立起一種直接高效的圍堵模型，基于某市交通網(wǎng)絡(luò)數(shù)據(jù)，給出巡警對(duì)犯罪嫌疑人的圍堵方案，力爭(zhēng)最短時(shí)間內(nèi)處理犯罪活動(dòng)。

本文研究了對(duì)犯罪嫌疑人的圍堵方案。假設(shè)某市路口P處發(fā)生了重大刑事案件[1]。在案發(fā)3分鐘后接到報(bào)警，犯罪嫌疑人已駕車逃跑。為了快速圍堵搜捕嫌疑犯，設(shè)計(jì)調(diào)度巡警警力資源的最佳圍堵方案。

二、方案建立

2.1、二部圖的轉(zhuǎn)化

交通網(wǎng)絡(luò)數(shù)據(jù)可抽象成無向圖。以路口為頂點(diǎn)，路口之間有直接道路則記為有邊，否則無邊。全市交通網(wǎng)絡(luò)可形成包括582個(gè)頂點(diǎn)，928條邊的稠密圖[2]，記做G。以每條邊長為權(quán)值，構(gòu)建該圖帶權(quán)鄰接矩陣。本文利用Floyd算法計(jì)算每兩個(gè)頂點(diǎn)之間的最短距離，形成圖的帶權(quán)鄰接矩陣E582×582，為下一步二部圖匹配形成數(shù)據(jù)基礎(chǔ)。考慮到本算例鄰接矩陣過大，本文給出部分鄰接矩陣的數(shù)據(jù)。（圖1、2）

假設(shè)當(dāng)該市某路口發(fā)生突發(fā)案件時(shí)，調(diào)度中心在案發(fā)3分鐘后接到報(bào)警，并立即調(diào)度巡警警力圍堵嫌疑犯。調(diào)度中心已知接警時(shí)各個(gè)巡警的所在位置，巡警警車在嫌疑犯車輛行駛3分鐘后出發(fā)。嫌疑犯的逃跑路線和逃跑距離是隨機(jī)的。對(duì)任意時(shí)間，嫌疑犯的位置均不確定。

但在逃跑速度一定的情況下，對(duì)于任意時(shí)間t（分鐘），嫌疑犯駕車逃跑的所能到達(dá)的最大范圍是確定的[3]，即可知嫌疑犯逃跑范圍的邊界路口。若給定時(shí)間（t-3），當(dāng)巡警能夠從所在位置到達(dá)逃跑范圍中的所有邊界路口，即認(rèn)為圍堵成功[4]。

2.2匹配算法分析

取時(shí)間t內(nèi)嫌疑犯所有可能行駛路線中所包含路口節(jié)點(diǎn)的并集，記為P；將P的邊界點(diǎn)集記為P'。接警時(shí)巡警所在路口節(jié)點(diǎn)的并集記做Q。在集合P'和Q之間做最大匹配?？赏耆ヅ鋾r(shí)，即最佳圍堵方案。

所謂二部圖就是頂點(diǎn)集合V可分割為兩個(gè)互不相交的子集，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬于這兩個(gè)互不相交的子集的特殊無向圖[5]。

所以，可以將交通網(wǎng)絡(luò)中的節(jié)點(diǎn)分為警察部署的節(jié)點(diǎn)與疑犯可能到達(dá)的節(jié)點(diǎn)[6]。用t表示警方追捕的時(shí)間，則嫌疑犯的逃跑時(shí)間為t+3。

首先構(gòu)建嫌疑犯位置與警察位置的關(guān)系矩陣A，A[i][j]=1時(shí)說明到t時(shí)刻j點(diǎn)的警察能逮捕到i點(diǎn)的嫌疑犯，然后對(duì)A用匈牙利算法做最大匹配，將匹配的結(jié)果記錄在二維矩陣PP中。

其中，利用匈牙利算法匹配的具體算法實(shí)現(xiàn)過程如下：

Step1：首先置二維矩陣PP為空，然后任意給y個(gè)匹配給PP；

Step2：若PP已飽和則算法結(jié)束，否則跳到step3步 （所謂飽和點(diǎn)就是結(jié)點(diǎn)i已找到匹配j）；

Step3：在PP取一個(gè)非飽和結(jié)點(diǎn)xi，將xi并入空集合y中；

Step4：取與xi關(guān)聯(lián)的并且未標(biāo)記的結(jié)點(diǎn)yy；

Step5：若yy已飽和，則將與yy匹配的結(jié)點(diǎn)Z并入集合y，并標(biāo)記yy跳向step4。若yy未飽和，則做一條從xi到y(tǒng)y的可增廣路P，將PP與P的異或結(jié)果賦給PP，跳向step2。

三、算例結(jié)果

根據(jù)上述算法，利用C語言編程[7][8]，可計(jì)算得案發(fā)3分鐘后的圍堵調(diào)度方案及時(shí)間，具體結(jié)果見表1。

交巡警在接到報(bào)警后最長用時(shí)3.8922分鐘，可將嫌疑犯完全圍堵。

對(duì)于任意路口發(fā)生的犯罪案件，二部圖匹配模型不僅能夠快速給出圍堵的警力調(diào)度方案，同時(shí)還能計(jì)算理論上的圍堵所需時(shí)間[9][10]。

在已知交通網(wǎng)絡(luò)數(shù)據(jù)的情況下，只需給出案件發(fā)生的路口位置和嫌疑犯的逃跑速度[11]，從接到報(bào)警到得出調(diào)度方案的過程由計(jì)算機(jī)程序來處理，大大縮短了警力的反應(yīng)時(shí)間，為更快的抓捕嫌疑犯提供科學(xué)的圍堵方案。

四、結(jié)語

和諧穩(wěn)定和依法治國是我國當(dāng)今社會(huì)的主題，而恐怖活動(dòng)和極端犯罪的多發(fā)對(duì)社會(huì)治安構(gòu)成嚴(yán)重威脅。本文提出借用圖論理論給出圍堵犯罪嫌疑人逃逸的數(shù)學(xué)模型，直接快捷，貼近實(shí)際圍堵情況。模型利用計(jì)算機(jī)編程，實(shí)現(xiàn)過程高效快速，可為警務(wù)部門圍堵罪犯提供參考。同時(shí)，模型及算法在消防、急救、公交規(guī)劃等方面具有一定推廣價(jià)值。

參 考 文 獻(xiàn)

[1]全國大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì).2011年競(jìng)賽題[EB/OL].http：//www.mcm.edu.cn

[2]鄭繼明，姚翀.圍堵在逃嫌疑犯的優(yōu)化模型研究.科學(xué)技術(shù)與工程，2012，12（33）：8980-8983

[3]陳馳，任愛珠.消防站布局優(yōu)化的計(jì)算機(jī)方法，清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2003，43（10）：1390-1393

[4]殷代君.廣義最大覆蓋模型在應(yīng)急設(shè)施選址中的應(yīng)用研究.中外企業(yè)家，2010，3：169-170

[5]圖論算法理論、實(shí)現(xiàn)及應(yīng)用.王桂平，王衍，任嘉辰.北京：北京大學(xué)出版社，2001.1

[6]陳仁愛，劉婷，馮賢財(cái)，等.基于優(yōu)化模型的街面逃逸犯罪嫌疑人的圍堵方案探討.科技信息，2012，3：65-66

[7]林祖順，李堅(jiān)，葉欣杰，等.基于“關(guān)鍵點(diǎn)封鎖”數(shù)學(xué)模型的圍堵逃犯問題研究.福建電腦，2012，1：54-56

[8]吳美文.基于離散定位模型的城市消防站優(yōu)化布局方法，系統(tǒng)仿真技術(shù)，2006，2（1）：58-62

[9]董金哲.罪犯圍捕中的數(shù)學(xué)方法.科技創(chuàng)新導(dǎo)報(bào)，2012（16）：255-256

[10]陳艷艷，郭國旗.城市消防站的優(yōu)化布局.消防科技，1999，（1）：26-28

[11]周安銀，尹銳.交巡警未來發(fā)展趨勢(shì)的思考.重慶城市管理學(xué)院學(xué)報(bào)，2011，11（4）：24-25