周志進(jìn)
(貴陽(yáng)學(xué)院 貴州貴陽(yáng) 550005)
最短路徑算法就是用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑問(wèn)題,一般是指確定起點(diǎn)的最短路徑問(wèn)題,求起始節(jié)點(diǎn)到某一終點(diǎn)的最短路徑問(wèn)題,也常用于已知起點(diǎn)和終點(diǎn),求解兩節(jié)點(diǎn)之間的最短路徑。
MATLAB 是由美國(guó)MathWorks 公司出品的數(shù)學(xué)軟件,MATLAB 意為矩陣工程,將用于一維、二維與三維數(shù)值積分的函數(shù)進(jìn)行了統(tǒng)一,并經(jīng)過(guò)基本數(shù)學(xué)和內(nèi)插函數(shù)的輔助,提供數(shù)值分析、矩陣計(jì)算等諸多功能,為應(yīng)用數(shù)學(xué)、工程設(shè)計(jì)和數(shù)值計(jì)算提供全方位的解決方案,很大程度上擺脫了傳統(tǒng)程序設(shè)計(jì)語(yǔ)言的編輯模式。其高效的數(shù)值及符號(hào)計(jì)算功能,可以幫助用戶快速處理繁雜的數(shù)學(xué)運(yùn)算問(wèn)題,具備的圖形處理功能可以實(shí)現(xiàn)計(jì)算結(jié)果和編程的可視化。MATLAB本身是一個(gè)高級(jí)的矩陣語(yǔ)言,包括諸多算法、控制語(yǔ)句、函數(shù)等面向基本對(duì)象或問(wèn)題的應(yīng)用程序[1]。比如:在最短路徑計(jì)算中可以利用矩陣運(yùn)算和線性方程組的求解或是數(shù)據(jù)的統(tǒng)計(jì)分析來(lái)優(yōu)化相關(guān)問(wèn)題。
Dijkstra(迪杰斯特拉)算法是最經(jīng)典的單源最短路徑算法,也就是用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)最短路徑的算法。Dijkstra算法采用貪心算法策略,每次遍歷與起點(diǎn)距離最近且未訪問(wèn)過(guò)的節(jié)點(diǎn),直至擴(kuò)展到終點(diǎn)。該算法類似于Prim(普里穆)算法在單個(gè)節(jié)點(diǎn)源中搜索最小生成樹,不過(guò)Dijkstra算法要求圖中不存在負(fù)權(quán)邊[2]。首先假設(shè)一個(gè)輔助數(shù)組,即一個(gè)帶權(quán)的有向圖G,數(shù)組中起始點(diǎn)v到某一節(jié)點(diǎn)的最短路徑在算法執(zhí)行過(guò)程中便會(huì)算法,但需要注意的是,這個(gè)值在計(jì)算過(guò)程中是不斷逼近最終結(jié)果的,并不確定就等于最短路徑距離。按照最短路徑長(zhǎng)度的遞增次序,依次向節(jié)點(diǎn)中加入未確定最短路徑的頂點(diǎn)s,不斷尋找下一條長(zhǎng)度最短的路徑,也就是v至s的最短路徑,當(dāng)v到s中各頂點(diǎn)的最短路徑長(zhǎng)度小于等于v到其余已確定最短路徑的節(jié)點(diǎn)時(shí),便可認(rèn)為s到v的距離就是最短路徑長(zhǎng)度,而且v到頂點(diǎn)s,只包括s中頂點(diǎn)為中間點(diǎn)的最短路徑[3]。
基于MATLAB 的Floyd-Warshall 算法(簡(jiǎn)稱Floyd算法)也是一種著名的解決任意兩點(diǎn)間最短路徑的算法,F(xiàn)loyd算法是利用插點(diǎn)的方式在給定的加權(quán)圖上計(jì)算多源點(diǎn)的最短路徑算法,從本質(zhì)上講Floyd算法是一個(gè)動(dòng)態(tài)規(guī)劃算法。在動(dòng)態(tài)規(guī)劃算法中,最為關(guān)鍵也是核心理念的就是對(duì)于狀態(tài)的定義,這是因?yàn)镕loyd算法的單個(gè)執(zhí)行將找到所有頂點(diǎn)之間的最短路徑長(zhǎng)度,并通過(guò)對(duì)算法的簡(jiǎn)單修改來(lái)重建路徑,以此驗(yàn)證加權(quán)圖中所有頂點(diǎn)之間的最短路徑。以d[k][i][j]可以定位為例,在使用1至k號(hào)節(jié)點(diǎn)時(shí),計(jì)算點(diǎn)i到點(diǎn)j之間的最短路徑長(zhǎng)度。在加權(quán)圖中有n個(gè)點(diǎn),從1 到n。k則變?yōu)閯?dòng)態(tài)規(guī)劃算法的松弛操作,也就是描述從起點(diǎn)v到s的最短路徑上權(quán)值的上界,也被稱作最短路徑估計(jì),通過(guò)d[1][i][j]表示只使用1 點(diǎn)作為中間媒介,點(diǎn)i到點(diǎn)j的最短路徑長(zhǎng)度,以此定義狀態(tài),便可構(gòu)建動(dòng)態(tài)轉(zhuǎn)移方程。動(dòng)態(tài)轉(zhuǎn)移就是在加權(quán)圖上d[k][i][j]由1 至n轉(zhuǎn)移到1 至k的一種狀態(tài)轉(zhuǎn)移表示,對(duì)這個(gè)狀態(tài)進(jìn)行動(dòng)態(tài)轉(zhuǎn)移,且有兩種情況,i到j(luò)最短路徑不經(jīng)過(guò)k;i到j(luò)最短路徑經(jīng)過(guò)k。可以得出基于Floyd算法的動(dòng)態(tài)轉(zhuǎn)移方程:
式中,d[n][i][j]為加權(quán)圖中所有頂點(diǎn)之間的最短路徑長(zhǎng)度;k、n皆為頂點(diǎn);而且要注意Floyd算法雖然是一種可以在具有正負(fù)邊緣權(quán)重加權(quán)圖中找到最短路徑的算法,但是并沒(méi)有負(fù)周期,這就表示動(dòng)態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)在不使用任何點(diǎn)的情況下,滿足兩點(diǎn)之間最短路徑的長(zhǎng)度的邊界條件。這樣就可以得出Floyd算法代碼:
動(dòng)態(tài)規(guī)劃算法中都具有利用滾動(dòng)數(shù)組的方式減少算法的空間復(fù)雜度,以便更快速地求得最優(yōu)解,常見(jiàn)的Floyd 算法也都是采用二維數(shù)組表示狀態(tài)。動(dòng)態(tài)轉(zhuǎn)移方程在隱藏階段索引后就變?yōu)椋?/p>
證明了在第k-1階段和第k階段,點(diǎn)i和點(diǎn)k之間的最短路徑長(zhǎng)度是不變的,也可以說(shuō)明在第k階段到第k-1階段計(jì)算中,點(diǎn)k和點(diǎn)j之間的最短路徑長(zhǎng)度不變。上一階段的值可以放心用于計(jì)算第k階段時(shí)d[i][j]的值。
Bellman-Ford算法相比較上述兩種算法可以計(jì)算存在負(fù)權(quán)邊的情況,進(jìn)行n-1 次更新來(lái)找到所有節(jié)點(diǎn)的最短路徑長(zhǎng)度。雖然Bellman-Ford 算法與Dijkstra算法有些類似,都可以確定一個(gè)節(jié)點(diǎn)的最短路徑。但不同的是,Bellman-Ford 算法并不知道具體哪個(gè)階段的最短路徑確定了,只能知道比上次計(jì)算多確定一個(gè),這樣進(jìn)行n-1 次更新后才能確定所有節(jié)點(diǎn)的最短路徑。算法原理是從已知節(jié)點(diǎn)連到其余節(jié)點(diǎn)的所有邊中的最小邊在更新后就是其余節(jié)點(diǎn)的最短距離,進(jìn)而知道一個(gè)可確定的最短距離節(jié)點(diǎn),無(wú)所謂它具體是哪個(gè)節(jié)點(diǎn)。Bellman-Ford 算法的優(yōu)勢(shì)在于可以用來(lái)判斷是否存在負(fù)環(huán),在不存在負(fù)環(huán)情況下,進(jìn)行n-1次更新后便能確定每個(gè)節(jié)點(diǎn)的最短距離,再用所有邊更新一次依然不會(huì)改變結(jié)果。但如果存在負(fù)環(huán),更新一次會(huì)改變結(jié)果,造成這種情況的原因就是之前假設(shè)起點(diǎn)的最短距離是確定的且最短的,而在負(fù)環(huán)情況下,這個(gè)假設(shè)不再成立。Bellman-Ford算法的代碼表示為:
從代碼實(shí)現(xiàn)的復(fù)雜性就可以看出Bellman-Ford算法的效率并不高。當(dāng)前如果沒(méi)有存在負(fù)環(huán)基本不會(huì)采用此算法,而且下述的SPFA算法也是對(duì)Bellman-Ford算法的一種優(yōu)化。
SPFA算法主要應(yīng)用于給定的加權(quán)圖存在負(fù)權(quán)邊,這種情況下無(wú)法運(yùn)用Dijkstra 算法和Floyd 算法,而Bellman-Ford 算法的復(fù)雜度過(guò)高。因此,SPFA 算法成為可選的方式。首先,需要約定加權(quán)圖基本存在負(fù)權(quán)邊也不能存在負(fù)權(quán)回路,保證最短路徑一定存在。雖然可以在執(zhí)行該算法前做一次拓?fù)渑判?,?lái)判斷該加權(quán)圖是否存在負(fù)權(quán)回路,但這與算法的關(guān)系不大,因此不深入分析[4]。SPFA算法的本質(zhì)是動(dòng)態(tài)逼近法,通過(guò)假設(shè)一個(gè)節(jié)點(diǎn)隊(duì)列來(lái)不斷更新隊(duì)列中的首尾節(jié)點(diǎn),在首位節(jié)點(diǎn)進(jìn)入隊(duì)列后進(jìn)行松弛操作,如果該節(jié)點(diǎn)指向最短路徑距離則進(jìn)行調(diào)整,若指向的節(jié)點(diǎn)不在隊(duì)列中,則將該節(jié)點(diǎn)加入隊(duì)列,其中最短路徑在隊(duì)列計(jì)算中為估計(jì)值,隨著隊(duì)列的不斷更迭進(jìn)行調(diào)整從而不斷逼近最短距離長(zhǎng)度,如此循環(huán)直至隊(duì)列中不存在節(jié)點(diǎn),便能夠得到節(jié)點(diǎn)之間的最短路徑長(zhǎng)度。而SPFA算法無(wú)法處理帶有負(fù)權(quán)回路的圖的原因,就是在某個(gè)節(jié)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)n次,導(dǎo)致隊(duì)列一直無(wú)法計(jì)算出經(jīng)過(guò)該節(jié)點(diǎn)的最短路徑。SPFA算法是Bellman-Ford算法的一種隊(duì)列實(shí)現(xiàn)表示,減少了不必要的冗余計(jì)算,原理就是利用隊(duì)列中的點(diǎn)與所有與其相鄰的點(diǎn)進(jìn)行松弛,不斷進(jìn)行反復(fù)迭代來(lái)確定最短路徑。SPFA算法的代碼表示為:
SFPA算法有兩個(gè)優(yōu)化算法,為SLF策略和LLL策略,SLF 策略設(shè)要加入的節(jié)點(diǎn)是j,隊(duì)首節(jié)點(diǎn)為i,若dist(i)>dist(j),則將j插入隊(duì)首,否則插入隊(duì)尾。簡(jiǎn)單明了,可使算法計(jì)算速度提高10%。而LLL策略設(shè)隊(duì)首節(jié)點(diǎn)為i,隊(duì)列中所有dist 值的平均值為x,若dist(i)>x則將i插入隊(duì)尾,查找下一元素,直到某dist(i)≤x,則對(duì)i進(jìn)行松弛操作。SLF+LLL 可大幅提高SFPA 算法的效率。不過(guò)在實(shí)際應(yīng)用中,SFPA 算法的時(shí)間效率并不穩(wěn)定,若出現(xiàn)計(jì)算時(shí)間很長(zhǎng)的情況,可采用更為穩(wěn)定的Dijkstra算法來(lái)計(jì)算最短路徑長(zhǎng)度[5]。
在實(shí)際生活中各類基站的分布需要經(jīng)過(guò)實(shí)地勘探、測(cè)量與分析才能繪制出基本的圖形和方案,根據(jù)不同基站節(jié)點(diǎn)位置與傳輸距離,篩選出較短的間距。比如換熱站、通信基站等,適宜的間距可以最大程度減少資源傳輸?shù)睦速M(fèi)問(wèn)題。根據(jù)實(shí)際基站模型簡(jiǎn)化,再將應(yīng)用圖論簡(jiǎn)化為實(shí)際基站分布,便可將基站簡(jiǎn)化為數(shù)個(gè)節(jié)點(diǎn),確定一個(gè)起始點(diǎn)后,通過(guò)基于MATLAB的最短路徑算法來(lái)規(guī)劃出基站分布的最短間距,并利用MATLAB 程序繪制出基站分布圖,全面表示基站節(jié)點(diǎn)之間的距離。特別是很多基站位于城市之中,需要從多條支路方案中篩選出距離相對(duì)更近的路線,便可以通過(guò)基于MATLAB的Dijkstra算法確定最短路徑,有效降低基站建設(shè)和運(yùn)營(yíng)成本,從根本上解決運(yùn)作保障和傳輸距離之間的協(xié)調(diào)問(wèn)題[6]。
通過(guò)分析基于MATLAB的最短路徑算法,可以得到基于MATLAB的不同路徑算法在最短路徑長(zhǎng)度計(jì)算中的基本原理和代碼實(shí)現(xiàn)情況,并通過(guò)最短路徑算法的實(shí)際應(yīng)用,了解到最短路徑算法有著良好運(yùn)用效果,有助于解決各種最優(yōu)距離、最短距離問(wèn)題,具有較高的實(shí)用性。