（武漢外國(guó)語(yǔ)學(xué)校，湖北武漢，430000）

最短路徑算法并行化策略的研究與實(shí)現(xiàn)

閔思晗,付逸飛

（武漢外國(guó)語(yǔ)學(xué)校，湖北武漢，430000）

現(xiàn)階段，隨著我國(guó)智能交通系統(tǒng)與通信系統(tǒng)的不斷發(fā)展完善，網(wǎng)絡(luò)新特性的出現(xiàn)，對(duì)于網(wǎng)絡(luò)中最短路徑問(wèn)題研究具有非常重要的意義。本文主要選取幾種最短路徑標(biāo)號(hào)串行算法，并在此基礎(chǔ)上分別通過(guò)網(wǎng)絡(luò)復(fù)制與網(wǎng)絡(luò)分割策略，對(duì)其最短路徑進(jìn)行求解，從而實(shí)現(xiàn)最短路徑算法并行策略的研究。

最短路徑算法；并行計(jì)算；網(wǎng)絡(luò)復(fù)制；網(wǎng)絡(luò)分割

最短路徑算法是實(shí)現(xiàn)資源分配與路線設(shè)計(jì)優(yōu)化的基礎(chǔ)，隨著信息科技的不斷完善與發(fā)展，現(xiàn)階段網(wǎng)絡(luò)最短路徑算法越來(lái)越多，不同的網(wǎng)絡(luò)環(huán)境與應(yīng)用，需求具有不同特性的最短路徑算法，并行計(jì)算技術(shù)的不斷發(fā)展為節(jié)省計(jì)算時(shí)間提供了有效的計(jì)算路徑，不斷提高了交通網(wǎng)絡(luò)最短路徑問(wèn)題的解決效率，實(shí)現(xiàn)大規(guī)模交通網(wǎng)絡(luò)最短路徑問(wèn)題的解決。

圖1：有向圖G=(V,A)

1 最短路徑算法比較分析

1.1 標(biāo)號(hào)算法

標(biāo)號(hào)算法在目前的最短路徑算法中，占有非常重要的地位，它可以依照不同的節(jié)點(diǎn)，對(duì)策略進(jìn)行相應(yīng)的分析與處理。

例如圖一中的有向圖G=(V,A)，將節(jié)點(diǎn)1作為圖中的源點(diǎn)，常用的標(biāo)號(hào)算法主要是指在該圖中，求解單個(gè)源點(diǎn)到其它各個(gè)源點(diǎn)的最短路徑，如該圖1所示，在建立過(guò)程中，每一個(gè)獨(dú)立的節(jié)點(diǎn)都具有不同信息分類(lèi)，例如長(zhǎng)度標(biāo)號(hào),父節(jié)點(diǎn)號(hào)及節(jié)點(diǎn)的當(dāng)前狀態(tài).

在迭代過(guò)程中，源點(diǎn)至節(jié)點(diǎn)的最短路徑中的上限值，主要在長(zhǎng)度標(biāo)號(hào)中保留，在最短路徑計(jì)算結(jié)束之時(shí)，長(zhǎng)度標(biāo)號(hào)成為該線路中唯一最短的路徑；在該有向圖中，其中位于節(jié)點(diǎn)之上的上一層節(jié)點(diǎn)標(biāo)號(hào)，在父節(jié)點(diǎn)中保存；節(jié)點(diǎn)的當(dāng)前狀態(tài)中的數(shù)值主要代表，其未訪問(wèn)以及永久標(biāo)號(hào)等狀態(tài)。

1.2 最具代表性的最短路徑標(biāo)號(hào)算法的選取

現(xiàn)階段，我國(guó)對(duì)最短路徑算法的研究已逐漸趨于成熟，但目前多種多樣的最短路徑算法，在測(cè)試網(wǎng)絡(luò)中的效率以及各項(xiàng)性能都不完善，在本文中最短路徑標(biāo)號(hào)算法的選取中，主要選取幾種具有代表性的算法來(lái)實(shí)現(xiàn)計(jì)算與求解。Bellman-Ford-Moore(BFM)（LC-1q）,D' Esopo-Pape（LC-2q），以及Dijkstra算法（LS）。

表一：三種最短路徑串行算法理論時(shí)間復(fù)雜性

這三種算法的性能理論具有相應(yīng)差別，雖然LC算法，理論上的復(fù)雜性上界比較大，但在稀疏網(wǎng)絡(luò)中具有良好的應(yīng)用性能，由于其自身的應(yīng)用特性，因此人們對(duì)于其期望性能的預(yù)測(cè)，存在很大的困難性，但與之相反，LS具有良好的預(yù)測(cè)性。

2 最短路徑算法并行化策略的研究

2.1 網(wǎng)絡(luò)復(fù)制策略

在求解最短路徑的過(guò)程中，可以利用系統(tǒng)的主處理器，將網(wǎng)絡(luò)復(fù)制于各處理器中，網(wǎng)絡(luò)源點(diǎn)按照處理器個(gè)數(shù)進(jìn)行相應(yīng)劃分，并將其分配于各處理器中；之后各個(gè)處理器，將不同源點(diǎn)所計(jì)算出的不同最短路徑，發(fā)送至主處理器，進(jìn)而實(shí)現(xiàn)對(duì)其的分析與整理。

在對(duì)各處理器中的不同源點(diǎn)進(jìn)行分配時(shí)，應(yīng)根據(jù)其間的計(jì)算負(fù)載平衡，對(duì)其進(jìn)行平均分配，在對(duì)源點(diǎn)最短路徑進(jìn)行計(jì)算時(shí)，各個(gè)處理器間不用進(jìn)行信息的互換，因此一定程度上節(jié)省了所需時(shí)間，提高了工作效率。

2.2 網(wǎng)絡(luò)分割策略

網(wǎng)絡(luò)分割最短路徑算法，主要是指在分布式網(wǎng)絡(luò)中實(shí)現(xiàn)單源最短路徑的解決，在工作過(guò)程中，它首先可將系統(tǒng)中的整體網(wǎng)絡(luò)劃分為多個(gè)子網(wǎng)，同時(shí)將其均勻分配至各處理器中。在該網(wǎng)絡(luò)分割系統(tǒng)中，包括邊界節(jié)點(diǎn)以及內(nèi)部節(jié)點(diǎn)，它們都是系統(tǒng)的重要組成部分，在該算法實(shí)施當(dāng)中，必須要保持各處理器間的部分通信暢通。在利用該方法進(jìn)行最短路徑求解的過(guò)程中，需要對(duì)邊界節(jié)點(diǎn)的標(biāo)號(hào)進(jìn)行系統(tǒng)的更新，在對(duì)其進(jìn)行更新時(shí)，還應(yīng)該將其整理成相應(yīng)的消息，并將其發(fā)送給相鄰子網(wǎng)中的處理器，由該處理器對(duì)其進(jìn)行計(jì)算。

2.2.1 網(wǎng)絡(luò)分割

在網(wǎng)絡(luò)分割時(shí)應(yīng)該注意盡量的將邊界節(jié)點(diǎn)的數(shù)量降到最低，這樣可節(jié)省開(kāi)支，同時(shí)對(duì)于子網(wǎng)中的負(fù)載量應(yīng)使其趨于平衡，這樣才能盡量減少處理器在工作時(shí)的時(shí)間，提高其工作效率。交通網(wǎng)絡(luò)中可采用模擬退火算法，而隨機(jī)網(wǎng)格可以采用方形分割法。

模擬退火算法在算法中可以解決大規(guī)模的組合優(yōu)化問(wèn)題，可以有效解決最短路徑計(jì)算問(wèn)題。具體算法如下所示：本文以邊界節(jié)點(diǎn)量與子網(wǎng)節(jié)點(diǎn)量間的方差建立函數(shù)（p代表分割后的子網(wǎng)數(shù)，nbi代表在第i個(gè)子網(wǎng)中所包含的邊界節(jié)點(diǎn)的個(gè)數(shù)，nb則代表總邊界節(jié)點(diǎn)數(shù)）

由以上公式可以得出在模擬退火算法方法中，當(dāng)函數(shù)值達(dá)到最小時(shí)，各邊界節(jié)點(diǎn)與子網(wǎng)中節(jié)點(diǎn)數(shù)值差距較小，因此其可以最大化的滿足網(wǎng)格分割要求。

2.2.2 終止檢測(cè)分析

在利用并行標(biāo)號(hào)算法的網(wǎng)格分割求解最短路徑時(shí)，其消息的轉(zhuǎn)換與交流，會(huì)造成時(shí)間的過(guò)度消耗，同步過(guò)程也會(huì)造成時(shí)間的損耗。終止檢測(cè)頻率，對(duì)計(jì)算途中的各個(gè)處理器的等待時(shí)間有很大影響，在本文終止檢測(cè)方法的選取中，主要采用令牌傳遞法，該方法不需對(duì)最優(yōu)終止檢測(cè)頻率進(jìn)行預(yù)測(cè)。

3 最短路徑算法分析

本實(shí)驗(yàn)中主要采用并行函數(shù)庫(kù)編程，實(shí)現(xiàn)對(duì)最短路徑的計(jì)算，同時(shí)在計(jì)算過(guò)程中，利用6臺(tái)節(jié)點(diǎn)機(jī)實(shí)現(xiàn)對(duì)算法加速比以及其效率的檢驗(yàn)，在測(cè)試網(wǎng)絡(luò)的選取中，主要應(yīng)用了3個(gè)實(shí)際的道路網(wǎng)格以及3個(gè)隨機(jī)網(wǎng)格，在稀疏性質(zhì)中保證二者的相似性，同時(shí)添加內(nèi)部節(jié)點(diǎn)與邊緣節(jié)點(diǎn)之間的連接弧，從而使二者的特征更加相似。

算法加速比：本文采取的算法模式都屬于粗粒度并行算法。在此基礎(chǔ)下可以看出網(wǎng)絡(luò)復(fù)制策略以及網(wǎng)絡(luò)分割策略都有很好的加速比，同時(shí)LC與LS綜合比較，以由于串行算法自身的標(biāo)點(diǎn)節(jié)點(diǎn)的選取以及刪除等造成的影響，使得LC的整體加速比優(yōu)于LS，因此從而證實(shí)LC比LS更適用于并行化。兩種策略下運(yùn)用機(jī)器以及相關(guān)源點(diǎn)對(duì)最短路徑加速比進(jìn)行分析。

表二：兩種策略最短路徑并行加速比

根據(jù)上述表格變化趨勢(shì)分析，在實(shí)際路網(wǎng)以及隨機(jī)網(wǎng)格中，網(wǎng)絡(luò)復(fù)制加速比會(huì)隨著節(jié)點(diǎn)數(shù)的增加而變小，而網(wǎng)絡(luò)分割中其加速比會(huì)隨網(wǎng)絡(luò)規(guī)模的不斷增大而增大。因此說(shuō)明大規(guī)模交通網(wǎng)中網(wǎng)絡(luò)分割比網(wǎng)絡(luò)復(fù)制并行算法更具有優(yōu)越性。

算法可拓展性：兩種并行算法都具有很好的可拓展性，在網(wǎng)絡(luò)復(fù)制中，網(wǎng)絡(luò)規(guī)模越小其擴(kuò)展性越好，在網(wǎng)格分割中則恰恰相反，因此證實(shí)了網(wǎng)絡(luò)分割，較適用于大規(guī)模網(wǎng)絡(luò)最短路徑求解。

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

綜上所述，現(xiàn)階段，我國(guó)對(duì)于最短路徑算法并行化策略的研究已逐漸趨于完善，對(duì)于最短路徑的算法也具有多種多樣性，本文在研究中主要選取了幾種效率較高的串行最短路徑標(biāo)號(hào)算法，同時(shí)利用網(wǎng)絡(luò)復(fù)制與分割策略對(duì)其進(jìn)行應(yīng)用，從而進(jìn)一步提升其計(jì)算效率，為交通運(yùn)輸中最短路徑并行算法的選擇與應(yīng)用提供相應(yīng)的依據(jù)。

[1] 孫文彬,譚正龍,王江,周長(zhǎng)江,何俊芳.最短路徑算法的并行化策略分析[J].地理與地理信息科學(xué),2013,04:17-20.

[2] 盧照.基于城市路網(wǎng)最短路徑并行搜索算法的研究[D].陜西師范大學(xué),2010.

[3] 郭紹忠,王偉,周剛,胡艷.基于GPU的單源最短路徑算法設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程,2012,02:42-44.

[4] 張鐘.大規(guī)模圖上的最短路徑問(wèn)題研究[D].中國(guó)科學(xué)技術(shù)大學(xué),2014.

Research and implementation of the parallel strategy of shortest path algorithm

Min Sihan,Fu Yifei
(Wuhan foreign language school,Wuhan,Hubei,430000)

At present,with the continuous development of the intelligent transportation system and communication system in our country,the emergence of the new features of the network is very important for the research of the shortest path problem in the network.In this paper,we select some of the shortest path label serial algorithm,and on this basis,respectively,through the network replication and network segmentation strategy,the shortest path to solve the problem,so as to achieve the shortest path algorithm parallel strategy.

shortest path algorithm;parallel computing;network replication;network partition

閔思晗（1998-），女，武漢外國(guó)語(yǔ)學(xué)校高三在讀，

付逸飛（1999-），男，武漢外國(guó)語(yǔ)學(xué)校高二在讀