高峰　秦堯　劉穆　嘎瑪次仁

摘? 要：最短路徑原本是圖論中的一個(gè)經(jīng)典算法文通，其目的是為了尋找圖中兩個(gè)定點(diǎn)間的最短距離。它的特點(diǎn)是以一個(gè)起始點(diǎn)為中心點(diǎn)向外擴(kuò)展到每一個(gè)節(jié)點(diǎn)。隨著工程學(xué)在各行業(yè)的廣泛應(yīng)用，最短路徑的應(yīng)用已經(jīng)不止僅限于路程算法，它還擴(kuò)展到交通工程、城市建設(shè)、計(jì)算科學(xué)等領(lǐng)域，該文旨在研究最短路徑算法的原理和代表算法——Dijkstra（迪杰斯特拉）算法，并將這種算法應(yīng)用到警務(wù)工作中，希望在未來(lái)能將最短路徑算法應(yīng)用到警力科學(xué)分布等工作中。

關(guān)鍵詞：最短距離? 算法? 路徑? 應(yīng)用

中圖分類(lèi)號(hào)：TP301 ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2019）07（b）-0013-02

1? 最短路徑

線(xiàn)性規(guī)劃問(wèn)題是大數(shù)據(jù)智能算法的有監(jiān)督學(xué)習(xí)范疇，即存在目標(biāo)變量，需要探索特征變量和目標(biāo)變量之間的關(guān)系，在目標(biāo)變量的監(jiān)督下學(xué)習(xí)和優(yōu)化算法。最短路徑算法就是一個(gè)典型的線(xiàn)性規(guī)劃問(wèn)題;令S為一個(gè)源點(diǎn)，T為目標(biāo)點(diǎn)，Cij>0為路徑（i，j）為鏈路距離。于是，需要最小的Z，使

最短路徑算法開(kāi)始于阻抗矩陣。阻抗矩陣中的數(shù)值表示兩個(gè)節(jié)點(diǎn)直接連接的阻抗，表示不直接連接。而后在即將分析的Dijkstra（迪杰斯拉特）算法，就是迭代計(jì)算從中心節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短距離。雖然它的計(jì)算機(jī)效率并不突出，但是它的很多擴(kuò)展算法或者改進(jìn)算法仍然具有很強(qiáng)的應(yīng)用性。

2? 迪杰斯特拉算法分析

Dijkstra算法（迪杰斯特拉）算法主要計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，算法的核心是以起點(diǎn)為中心向外層擴(kuò)散，途徑每一個(gè)點(diǎn)，直至擴(kuò)散到終結(jié)點(diǎn)。雖然該算法需要遍歷計(jì)算所有節(jié)點(diǎn)，效率略低，但是卻能給出多種相似的解決方案，同時(shí)可以輔助其他算法，增加迪杰斯特拉算法效率。迪杰斯特拉算法作為最短經(jīng)典的經(jīng)典算法，應(yīng)用范圍十分廣泛，如圖論、運(yùn)籌學(xué)、數(shù)據(jù)結(jié)構(gòu)等。

該算法的思想是，設(shè)有一個(gè)帶權(quán)的向圖，將圖中的頂點(diǎn)集合分為兩組，第一組為已求出最短路徑的頂點(diǎn)集合，第二組為其他未確定最短路徑的頂點(diǎn)集合，按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入到第一組頂點(diǎn)中。利用遞歸算法一次將所有最短距離的點(diǎn)加入第一組集合，從而求出第一組頂點(diǎn)到第二組頂點(diǎn)的最短路徑頂點(diǎn)之和。如舉例說(shuō)明，圖1是一個(gè)頂點(diǎn)集合圖。

根據(jù)上面算面解釋?zhuān)O(shè)置兩個(gè)頂點(diǎn)集合，分別為S集合和U集合（見(jiàn)表1），根據(jù)迪杰斯特拉算法，我們可以使用數(shù)據(jù)結(jié)構(gòu)節(jié)點(diǎn)算法，將一個(gè)頂點(diǎn)到其他頂點(diǎn)的所有路徑計(jì)算出來(lái)，最后比較權(quán)的大小，最終取權(quán)值最小的為最短路徑，如A到C點(diǎn)，有以下路徑：

A->B->C=7;A->B->D->C=8;A->E->B->C=10;A->E->D->C=13

根據(jù)上面的結(jié)果，我們發(fā)現(xiàn)A->E是最長(zhǎng)路徑的兩種，迪杰斯特拉算法可以首先放棄經(jīng)過(guò)E點(diǎn)的可能性。

3? 最短路徑算法應(yīng)用及開(kāi)發(fā)技術(shù)

預(yù)案處置是一種警務(wù)力量安排的方法，依據(jù)多年警務(wù)事件實(shí)踐的經(jīng)驗(yàn)和相關(guān)法律法規(guī)制度的規(guī)定，總結(jié)出針對(duì)各種類(lèi)型案件的行之有效的工作方法和制定的處理案件流程，使得干警在各類(lèi)不同案件的處理流程具有更強(qiáng)的程序化和規(guī)范化，節(jié)約警力資源，實(shí)現(xiàn)指導(dǎo)員、處警員、各警種的協(xié)調(diào)配置，最大限度發(fā)揮處置效果[2]。

預(yù)警模塊是根據(jù)公安機(jī)關(guān)長(zhǎng)期經(jīng)驗(yàn)總結(jié)出的各類(lèi)案件、事件的處理方法，并將這些方法設(shè)置成未來(lái)處理相關(guān)案件的制度流程，并最終形成預(yù)案制度。預(yù)案可以分為：群體性事件處理預(yù)案、火災(zāi)爆炸處理預(yù)案、自然災(zāi)害處理預(yù)案、化學(xué)危險(xiǎn)品處置預(yù)案等。

首先，當(dāng)接警中心接到報(bào)案后，會(huì)根據(jù)案件的發(fā)生地點(diǎn)甚至是地理坐標(biāo)位置作為查詢(xún)條件，然后根據(jù)事件的具體情況選擇輸入一個(gè)攔截半徑，以攔截半徑為圓面查詢(xún)?cè)摲秶鷥?nèi)的警力裝備情況和相關(guān)屬性信息。

其次，輸入預(yù)案信息，調(diào)出方案，根據(jù)情況對(duì)比進(jìn)行調(diào)整。然后，生成最短路徑線(xiàn)路，根據(jù)第一步的攔截半徑圓面合理通知警力和使用裝備，最終形成理想的路徑合理安排調(diào)度。為了確保事件現(xiàn)場(chǎng)的快速處置，還可以根據(jù)線(xiàn)路的長(zhǎng)短安排巡警控制交通，甚至是幾條線(xiàn)路的交通;出警的原則是“路線(xiàn)固定、盡量集中”。

根據(jù)以上的步驟，我們可以選用ArcGIS Engine作為最短路徑的地理信息系統(tǒng)的開(kāi)發(fā)引擎，ArcGIS Engined的功能十分強(qiáng)大，它既支持簡(jiǎn)單的地圖應(yīng)用，同時(shí)又滿(mǎn)足對(duì)地理信息系統(tǒng)較高要求的分析應(yīng)用。為了能夠展現(xiàn)大數(shù)據(jù)分析中隨需而變的理念，ArcGIS Engine針對(duì)程序員開(kāi)發(fā)的需求增加了開(kāi)發(fā)包軟件，能在開(kāi)發(fā)中很容易地實(shí)現(xiàn)動(dòng)態(tài)制圖和隨需要變化的GIS功能，ArcGIS Engine還增加了構(gòu)建定制地圖的個(gè)性需求，從而為地理信息系統(tǒng)做出了非常好的解決方案[3]。ArcGIS Engine為了更好地靈活支持工業(yè)標(biāo)準(zhǔn)的編程環(huán)境，開(kāi)發(fā)出更加睿智的地圖界面，ArcGIS Engine在組件中增加協(xié)同關(guān)系組件，使地理信息系統(tǒng)數(shù)據(jù)和其他信息無(wú)縫對(duì)接。豐富的API接口幫助文檔和示例代碼使開(kāi)發(fā)者不必?fù)?dān)心開(kāi)發(fā)語(yǔ)言不同會(huì)是開(kāi)發(fā)的障礙;但是ArcGIS Engine開(kāi)發(fā)包絕不是給普通用戶(hù)使用，它更多是為了供開(kāi)發(fā)編程人員使用，具有很強(qiáng)的專(zhuān)業(yè)性。程序員使用ArcGIS Engine開(kāi)發(fā)出的應(yīng)用軟件，可以跨平臺(tái)使用，既可以構(gòu)建在基于Intel架構(gòu)的微軟視窗系統(tǒng)，也可以輕松部署在大型服務(wù)器系統(tǒng)，如UNIX和Linux上，程序員不必將過(guò)多的精力放在擔(dān)心不同系平臺(tái)的應(yīng)用效果上，而是更好地將更多的聰明才智集中在軟件的應(yīng)用開(kāi)發(fā)上。

4? 結(jié)語(yǔ)

最短路徑的應(yīng)用領(lǐng)域廣泛，既可以使用在警務(wù)的人員調(diào)配、車(chē)輛調(diào)度等領(lǐng)域，還可以使用在上下班高峰期的車(chē)輛紅燈調(diào)低的交通疏導(dǎo)上，同時(shí)還可以輔助其他算法，如克里金插值算法，不僅得到點(diǎn)、線(xiàn)圖形，還能根據(jù)需要設(shè)置一個(gè)面里的相關(guān)值應(yīng)用，因此最短路徑算法在預(yù)警應(yīng)用領(lǐng)域非常廣泛。

參考文獻(xiàn)

[1] 李崇貴，陳崢，豐德恩，等.ArcGIS Engine組件式開(kāi)發(fā)及利用[M].北京：科學(xué)出版社，2012.

[2] 姚遠(yuǎn).公安警務(wù)調(diào)度系統(tǒng)的研究與實(shí)現(xiàn)[D].上海交通大學(xué)，2008.

[3] 許軍.地理信息系統(tǒng)的應(yīng)用[D].北京郵電大學(xué)，2009.