大規(guī)模網(wǎng)絡(luò)最短路徑的分層優(yōu)化算法研究.pdf

1、最短路徑問題作為圖論與網(wǎng)絡(luò)優(yōu)化理論經(jīng)典問題之一，其研究歷經(jīng)了半個多世紀(jì)的發(fā)展歷程，受到了來自運(yùn)籌學(xué)、計算機(jī)科學(xué)、地理信息科學(xué)、交通運(yùn)輸?shù)缺姸鄬W(xué)科領(lǐng)域人員越來越多的關(guān)注。道路交通網(wǎng)絡(luò)中的出行路線的選取是最短路徑問題的一個最基本應(yīng)用。最短路徑問題還廣泛存在于其它眾多實(shí)際系統(tǒng)中。例如，計算機(jī)網(wǎng)絡(luò)中的信息流只有在經(jīng)由最短路由器序列進(jìn)行傳輸時其效率才最佳；在社會關(guān)系網(wǎng)絡(luò)中，人們更傾向于通過最少的朋友以及朋友的朋友這種連接關(guān)系來建立與陌生人之間的聯(lián)

2、系。
　　考慮到實(shí)際系統(tǒng)的規(guī)模通常異常龐大，而經(jīng)典最短路徑算法在處理大規(guī)模問題時普遍存在計算復(fù)雜度過高、存儲消耗過大等問題，因而圍繞大規(guī)模網(wǎng)絡(luò)的各類加速技術(shù)、加速算法研究成為近年來關(guān)注的重點(diǎn)。在這些研究中普遍涉及數(shù)據(jù)的預(yù)先計算環(huán)節(jié)，并通過預(yù)處理生成的輔助數(shù)據(jù)來加速后續(xù)算法的執(zhí)行。本論文在總結(jié)現(xiàn)有研究成果和經(jīng)驗的基礎(chǔ)之上，致力于探索更加高效、高精度的啟發(fā)式路徑引導(dǎo)算法，采用分層優(yōu)化的基本思路實(shí)現(xiàn)對問題的降解和抽象。論文主要內(nèi)容和研究

3、成果如下：
　　1.從復(fù)雜網(wǎng)絡(luò)理論這一新角度出發(fā)，將其中有關(guān)層次性及社團(tuán)結(jié)構(gòu)方面的研究成果引入到對大規(guī)模網(wǎng)絡(luò)分層的描述、網(wǎng)絡(luò)動態(tài)分割質(zhì)量的衡量以及后續(xù)最短路徑算法的設(shè)計之中，取得了良好的效果。
　　2.提出了一種最小化各子網(wǎng)絡(luò)穿越距離比的網(wǎng)絡(luò)分割模型，并設(shè)計了相應(yīng)的實(shí)現(xiàn)算法，為非平面結(jié)構(gòu)網(wǎng)絡(luò)的劃分及網(wǎng)絡(luò)動態(tài)分割質(zhì)量的衡量提供了一種新的思路和依據(jù)。
　　3.構(gòu)建了一種網(wǎng)絡(luò)層次抽象的空間模型。通過提取分割后網(wǎng)絡(luò)中的邊界點(diǎn)、

4、子網(wǎng)絡(luò)之間邊并構(gòu)造各子網(wǎng)絡(luò)內(nèi)部邊，以及通過將各子網(wǎng)絡(luò)及其鄰接關(guān)系映射為節(jié)點(diǎn)和邊，進(jìn)而得到高一級網(wǎng)絡(luò)分層和抽象網(wǎng)絡(luò)分層。這兩種分層模型在很大程度上減少了原網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的數(shù)目，從而大大降低了分層網(wǎng)絡(luò)中搜索算法的復(fù)雜度。
　　4.提出了一種基于子圖坐標(biāo)引導(dǎo)的快速分層最短路徑算法。針對初始點(diǎn)與目標(biāo)點(diǎn)位于同一子圖的情形，通過重構(gòu)搜索區(qū)域的方式來加快算法的執(zhí)行；而針對初始點(diǎn)與目標(biāo)點(diǎn)位于不同子圖的情形，定義了子圖坐標(biāo)及子圖距離來限制可搜索的子

5、圖范圍，并通過調(diào)節(jié)候選子圖對數(shù)目α、距離系數(shù)β和重疊節(jié)點(diǎn)基準(zhǔn)值γ這三個參數(shù)的取值，進(jìn)而實(shí)現(xiàn)算法在計算效率與精度之間的不同折衷。
　　5.提出了一種通用性更為廣泛的基于子圖終止技術(shù)的快速分層最短路徑算法。算法通過不斷維護(hù)和更新初始點(diǎn)s與目標(biāo)點(diǎn)t之間的距離值的上界(d)(s, t)，計算 s-t間經(jīng)由當(dāng)前節(jié)點(diǎn)u離開某一子圖時的距離估計下限(d)(s,u,t)來作出判斷：一旦距離估計下限值(d)(s,u,t)超出了上界(d)(s, t)