一種改進(jìn)的鄰接視點優(yōu)化算法

一種改進(jìn)的鄰接視點優(yōu)化算法

1dij保護(hù)方式的概念網(wǎng)絡(luò)分析是gis中非常重要的空間分析功能之一。最短路徑分析是網(wǎng)絡(luò)分析的主要算法。該算法的效率決定了網(wǎng)絡(luò)分析的功能和效率。在大量的最短路算法中,Dijksta算法是一種最經(jīng)典的方法,很多算法都是在該算法的基礎(chǔ)上經(jīng)過改進(jìn)發(fā)展而來的。本文就是在詳細(xì)研究該算法的基礎(chǔ)上,結(jié)合矢量數(shù)據(jù)的拓?fù)潢P(guān)系,滿足實際應(yīng)用中的網(wǎng)絡(luò)分析需求而優(yōu)化的一種算法。本文首先詳細(xì)介紹Dijksta算法,并舉例說明該算法的缺陷,并在此基礎(chǔ)上提出一種新的優(yōu)化方法。2dijksta算法2.1計算距離中的uij設(shè)D=(V,A,w)是一個非負(fù)權(quán)網(wǎng)絡(luò),V=(v1,v2,…,vn)。則D中最短(vi,vj)∈A路的長滿足方程:u1=0uj=min(uk+wkj)(j=2,3,…,n)(1)如果D中從頂點v1到其余各頂點最短路的長按照大小排序為:ui1≤ui2≤?≤uinui1≤ui2≤?≤uin這里i1=1,ui1=0,則由(1)式有uij=min{uik+wikij}k≠j=min{mink<j{uik+wikij},mink>j{uik+wikij}}(j=2,3,...,n)當(dāng)k>j時,uik≥uij,且wikij≥0,從而uij≤uik+wikijuij≤uik+wikij即uij≤min{uik+wikij}k>j所以uij=min{uik+wikij}k<j容易證明:ui1=0uij=min{uik+wikij}k<j的解(ui1,ui2,…,uin)中的uij是D中最短(ui,uj)路的長度,j=1,2,…,n。這就是Dijkstra的理論證明,為了便于說明,采用下面的方法來舉例說明。在圖1所示的一個簡單網(wǎng)絡(luò)中,根據(jù)其距離與結(jié)點之間的關(guān)系,形成鄰接矩陣與距離矩陣,在此基礎(chǔ)上,用著色的方法表示Dijkstra的計算方法,計算從A點到D點的最短距離如下:第一步A著色,d(A)=0,d(D)=∞。第二步y(tǒng)=Ad(B1)=min(d(B1),d(A)+a(A,B1))=min(∞,0+4)=4d(B2)=min(d(B2),d(A)+a(A,B2))=min(∞,0+5)=5d(B3)=min(d(B3),d(A)+a(A,B3))=min(∞,0+3)=3d(B3)=3為最小,對B3著色。第三步D尚未著色,繼續(xù)執(zhí)行第二步。第二步令y=B3d(B1)=min(d(B1),d(B3)+a(B3,B1))=min(4,∞)=4d(B2)=min(d(B2),d(B3)+a(B3,B2))=min(5,3+3)=5d(C2)=min(d(C2),d(B3)+a(B3,C2))=min(∞,3+3)=6d(B1)=3為最小,對B1著色。第三步D尚未著色,繼續(xù)執(zhí)行第二步。第二步令y=B1d(B2)=min(d(B2),d(B1)+a(B1,B2))=min(5,4+3)=5d(C1)=min(d(C1),d(B1)+a(B1,C1))=min(∞,4+4)=8d(B2)=5為最小,對B2著色第三步D尚未著色,繼續(xù)執(zhí)行第二步。第二步令y=B2d(C3)=min(d(C3),d(B2)+a(C3,B2))=min(∞,5+2)=7d(C2)=6d(C2)=5為最小,對C2著色。第三步D尚未著色,繼續(xù)執(zhí)行第二步。第二步令y=C2d(D)=min(d(D),d(C2)+a(C2,D))=min(∞,6+5)=11d(C3)=min(d(C3),d(C2)+a(C2,C3))=min(7,6+2)=7d(C3)=7為最小,對C3著色。第三步D尚未著色,繼續(xù)執(zhí)行第二步。第二步令y=C3d(D)=min(d(D),d(C3)+a(C3,D))=min(10,6+4)=10d(C1)=min(d(C1),d(C3)+a(C1,C3))=min(8,7+2)=9d(C1)=9為最小,對C1著色。第三步D尚未著色,繼續(xù)執(zhí)行第二步。d(D)=min(d(D),d(C1)+a(C1,D))=min(10,9+4)=10對D著色,停止計算。得到從A到D的最短距離為10。2.2關(guān)聯(lián)矩陣使用Dijkstra算法基于網(wǎng)絡(luò)的權(quán)矩陣求解最短路問題的計算機算法和程序中,運用了關(guān)聯(lián)矩陣、鄰接矩陣和距離矩陣的概念。在存儲圖形數(shù)據(jù)和運算時,需要定義N×N的數(shù)組,其中N為網(wǎng)絡(luò)的結(jié)點數(shù),當(dāng)網(wǎng)絡(luò)的結(jié)點數(shù)較大時,將占用大量的計算機內(nèi)存。如果不對Dijkstra算法進(jìn)行優(yōu)化,該算法很難在實際中得到應(yīng)用。3判斷矩陣pj隨著網(wǎng)絡(luò)空間數(shù)據(jù)的增大,網(wǎng)絡(luò)結(jié)點數(shù)的增加,直接使用Dijkstra算法是不現(xiàn)實的,要想處理大數(shù)據(jù)量的最短路徑分析,必須進(jìn)行優(yōu)化。下面還以上面的例子說明基于Dijkstra算法的一種優(yōu)化算法——鄰接結(jié)點算法。首先做以下準(zhǔn)備工作:(1)依據(jù)最大相鄰結(jié)點數(shù)的概念,求出網(wǎng)絡(luò)的最大相鄰結(jié)點數(shù)m=4。(2)構(gòu)造鄰接矩陣fJ。以結(jié)點為行,以相鄰的結(jié)點為列,矩陣的行數(shù)為網(wǎng)絡(luò)的實際結(jié)點數(shù),列數(shù)為網(wǎng)絡(luò)的最大相鄰結(jié)點數(shù)m。與結(jié)點i相連的邊號為矩陣的第i行。如果該結(jié)點的相鄰結(jié)點數(shù)少于最大相鄰結(jié)點數(shù)m,則用0代替。如圖1網(wǎng)絡(luò)的鄰接矩陣和圖3中的鄰接矩陣。(3)構(gòu)造判斷矩陣pJ。對照鄰接矩陣,用鄰接矩陣?yán)锏母鱾€元素對應(yīng)邊號的邊長代替同一位置的邊號就構(gòu)成了判斷矩陣pJ。如圖1網(wǎng)絡(luò)的判斷矩陣和圖3中的判斷矩陣。(4)在鄰接矩陣fJ和判斷矩陣pJ基礎(chǔ)上求網(wǎng)絡(luò)上任意兩點間的最短路徑。然后,開始計算A到D的最短路徑,步驟如下:①初始化臨時標(biāo)識向量T,Ti=0,i=1,2,…,8。(著色)②查找判斷矩陣的起始行中不為∞的值,初始化距離向量D和標(biāo)記向量P:D2=4,P2=1,D3=5,P3=1,D4=3,P4=1,③計算距離向量中的最小值fmin=3。④把對應(yīng)的標(biāo)識向量賦值T4=-1,并得到結(jié)點i=4。⑤查找鄰接矩陣的i行中不為0的值,按照方程uj=min(uk+wkj)(j=2,3,...,n)uj=min(uk+wkj)(j=2,3,...,n)循環(huán)計算與結(jié)點i相連的所有的其他結(jié)點與起點(結(jié)點1)的距離,并判斷該距離是否小于距離向量中對應(yīng)的值,如果小,則:賦值距離向量D和標(biāo)記向量P:以第4行的結(jié)點6為例:u6=u4+u46=D4+U46=3+3=66<D6=∞則賦值距離向量D6=6,標(biāo)記向量P6=4。重復(fù)第③～⑤步:計算距離向量中的最小值fmin。標(biāo)識向量值為-1的不計算在內(nèi),fmin=4;把對應(yīng)的標(biāo)識向量賦值T2=-1,并得到結(jié)點i=2;查找鄰接矩陣的i行中不為0的值,按照方程uj=min(uk+wkj)(j=2,3,...,n)uj=min(uk+wkj)(j=2,3,...,n)循環(huán)計算與結(jié)點i相連的所有的其他結(jié)點與起點(結(jié)點1)的距離,并判斷該距離是否小于距離向量中對應(yīng)的值,如果小,則:賦值距離向量D和標(biāo)記向量P:以第2行的結(jié)點5為例:u5=u2+u25=D2+U25=4+4=88＜D5=∞則賦值距離向量D5=8,標(biāo)記向量P5=2。重復(fù)第③～⑤步:直到距離向量中的最小值為終止結(jié)點8時,該最小值就是要求的最短距離。如果還沒有計算到終止結(jié)點8,最小值為∞,則不存在最短路徑,即不連通。通過標(biāo)記向量P,可以很容易跟蹤出經(jīng)過的路徑。上述的鄰接結(jié)點算法避免了使用含有大量無窮值的關(guān)聯(lián)矩陣,使之更適合帶有拐向限制設(shè)置的最短路徑算法和大量結(jié)點(超過8000個結(jié)點)的實際數(shù)據(jù)。實踐證明,該算法可以節(jié)約大量的內(nèi)存,對于結(jié)點數(shù)比較大的網(wǎng)絡(luò),或帶有大量拐向限制設(shè)置的網(wǎng)絡(luò),具有較好的適用性。經(jīng)過筆者的應(yīng)用驗證,該優(yōu)化算法不但節(jié)約內(nèi)存而且效率很高