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

史魯杰 郭昱宇 朱麗梅

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

【關鍵詞】 犯罪圍堵 二部圖 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