障礙物存在的最短路徑算法及其在車載導(dǎo)航中的應(yīng)用

引言

路徑選擇問(wèn)題是解決車載導(dǎo)航系統(tǒng)中的核心問(wèn)題，歸根結(jié)底是最短路徑問(wèn)題。現(xiàn)有的最短路徑算法有很多，如迪杰斯特拉（Dijkstra）、弗洛伊德（Floyd）及其改進(jìn)算法、盲目捜索法，啟發(fā)式A*算法、人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法等［%而這其中又是以迪杰斯特拉及其改進(jìn)算法最經(jīng)典,是研究得最多的一種算法，并取得了一定的成果，然而，對(duì)這些成果進(jìn)行分析發(fā)現(xiàn)，研究的這些算法都是靜態(tài)的，以圖論為基礎(chǔ)的方法，并沒(méi)有考慮到障礙物的影響。因此，本文主要對(duì)有障礙物影響的情況下的最短路徑算法進(jìn)行研究，并利用MapX控件實(shí)現(xiàn)了最短路徑的算法，在車載導(dǎo)航中取得了較好的應(yīng)用。

1Dikjsrta算法存在的問(wèn)題

Dikjsrta算法是由荷蘭數(shù)學(xué)家E.W.Dikjsrta于1959年提出單源最短路算法，是目前求解最短路問(wèn)題的理論上最完備、應(yīng)用最廣的經(jīng)典算法，它可完成從指定圖中所有其他節(jié)點(diǎn)的最短路徑，它是主要路徑長(zhǎng)度遞增產(chǎn)生最短路徑算法，此算法在諸多教材中均有闡述。從所介紹的算法不難看出存在兩點(diǎn)不足:①只考慮靜態(tài)的最短路徑，沒(méi)有及時(shí)反映出存在障礙物（如交通阻塞、修路等情況）下的最短路徑；②圖的存儲(chǔ)結(jié)構(gòu)中存在著大量的8,浪費(fèi)了大量的存儲(chǔ)空間。因此本文從以上兩個(gè)方面加以改進(jìn)。

2Dikjsrta算法的改進(jìn)

2.1有障礙物存在時(shí)的改進(jìn)Dikjsrta算法

通過(guò)對(duì)各類公交流量的分析和研究，可將城市道路障礙物分為阻塞和繁忙兩種狀態(tài)，如修路行不通為阻塞狀態(tài)、上下班堵車為繁忙狀態(tài)，在這兩種狀態(tài)情況下，必須另錄一條最短路徑以獲得時(shí)間最短。將障礙物反映到圖上，則存在兩種情況：一是正好在相應(yīng)節(jié)點(diǎn)上（如圖1節(jié)點(diǎn)2上），貝嶼其相連的節(jié)點(diǎn)上各邊權(quán)值變?yōu)?；二是在相應(yīng)的某一條邊上（如節(jié)點(diǎn)1-3）之間，貝懼相鄰接的鄰接矩陣變?yōu)?。其改進(jìn)算法如下：

建立鄰接矩陣A[v,][vJ]?若v障礙物正好處于圖的節(jié)點(diǎn)，則此節(jié)點(diǎn)是車載不允許經(jīng)過(guò)的節(jié)點(diǎn)，A[:][Vj]=8,亦矩陣中V所在的列的元素均取8。若障礙物正好位于兩節(jié)點(diǎn)之前,即此段路程不通必須加以回避，設(shè)e,j=(v?Vj)為必須回避的邊,則A[v；][vj]=8。

初始化。S={vs)(vseV),dist[vi]=A[vs][vi],path[Vj]={vs},vieV,i=1,2,…，n。

選擇Vk，使得dist[Vk]=min(dist[v』VieV-S),S=SU{Vk}。Vk為目前求得的下一條從Vs出發(fā)的最短路徑的終點(diǎn)。如果Vk夭Vt，轉(zhuǎn)向(4),否則結(jié)束,dist[Vt]即為回避的點(diǎn)、邊、路徑障礙下從Vs到頂點(diǎn)vt的最短路徑。

修改從v出發(fā)到集合V-S任一頂點(diǎn)Vi的最短路徑長(zhǎng)度。設(shè)V為路徑path[Vk]倒數(shù)第二個(gè)節(jié)點(diǎn)。若dist[Vk]+A[Vk][Vi]<dist[Vi],則dist[i]=dist[Vk]+A[Vk][Vi],path[Vi]=path[Vk]U{財(cái)，轉(zhuǎn)向(3)。

圖1所示是一種有路障的加權(quán)圖G',圖1中，假設(shè)節(jié)點(diǎn)2號(hào)有路障，另外1-3號(hào)節(jié)點(diǎn)的路段正在修路不能通行，其存儲(chǔ)的鄰接矩陣如圖2所示。

圖2圖G'的鄰接矩陣

2.2存儲(chǔ)結(jié)構(gòu)的改進(jìn)

無(wú)論是有無(wú)障礙物的Dikjsrta算法，采用矩陣來(lái)存儲(chǔ)點(diǎn)與點(diǎn)間的拓?fù)潢P(guān)系，行數(shù)和列數(shù)相同，矩陣中i行J列的值對(duì)應(yīng)著點(diǎn)i和點(diǎn)J之間的權(quán)值，起點(diǎn)和終點(diǎn)為同一點(diǎn)時(shí)權(quán)值用0表示，兩點(diǎn)之間沒(méi)有直接通路時(shí)權(quán)值用8表示。矩陣中含有大量的0和8,增加了無(wú)效循環(huán)次數(shù)，在存儲(chǔ)上也占用了大量的空間，浪費(fèi)了大量的空間。為提高內(nèi)存的利用率，本文采用的鄰接表存儲(chǔ)如圖3所示。

用鏈表數(shù)組MGrpah表示存儲(chǔ)矩陣G時(shí)，可將其每一行用一個(gè)單鏈表來(lái)表示，鏈表中只有非8元素，每個(gè)節(jié)點(diǎn)有兩個(gè)元素，一個(gè)為所在的列值，一為點(diǎn)的權(quán)值。其偽代碼如下:

Typedfstruct

{Intr,v；

Mnode*next；

}Mnode；

ClassMGraph{

Public:

Mnode*first,*current；

Mgraph(){current=null；first=current；}

Voidsetfirst(Mnode*p){first=p；current=first；}

Mnode*GotoFirst(){if(first){current=first；returncurrent；}

Elsereturnnull；}

VoidAdd(Mnode*p){current->next=p；current=p；}

Mnode*Next(){if(current->next){current=current->next；returncurrent；}

ElsereturnNULL；}

}

然后可用一維數(shù)組D來(lái)存儲(chǔ)各頂點(diǎn)到源點(diǎn)的最短距離,并用一維數(shù)組P來(lái)存儲(chǔ)前驅(qū)點(diǎn)，再用一個(gè)輔助雙向鏈表來(lái)存儲(chǔ)正在參與比較的節(jié)點(diǎn)(使用雙向鏈表的目的是在刪除節(jié)點(diǎn)時(shí)降低時(shí)間復(fù)雜度)。其代碼如下：

Typedefstruct{intr；Node*next,*prev；}chinaNode；

Classpath{

public:

chainNode*first,*current；

intn；

path(){n=0；current=null；first=null；}

voidsetfirst(chainnode*p){first=p；current=first；n=1；}

voidAddTail(chainNode*p){current->next=p；p->prev=current；current=p；n++}

intdelete(chainNode*p)；

chainNode*Next(){if(current->next){current=current->next；

returncurrent；}elsereturnnull；}

boolIsEmpty(){returnn==0；}

}

2.3改進(jìn)算法的實(shí)現(xiàn)步驟

改進(jìn)算法的實(shí)現(xiàn)步驟如下：

將與V。直接相連的節(jié)點(diǎn)的D[vJ初始化為其權(quán)值,其余的置為機(jī)器所允許的最大值。

將與V。直接相連的頂點(diǎn)加入到鏈表Path中。

在Path中找到權(quán)值最小的節(jié)點(diǎn)w,并在Path中刪除此頂點(diǎn)，如果剩余節(jié)點(diǎn)數(shù)為。則結(jié)束。

修改最短路徑：在G里與w直接相連的其余各節(jié)點(diǎn)Vj的權(quán)值中比較D[Vj]與D[w]+s(w,vD的大小，如果D[vJ小于D[w]+s(w,Vj),并且如果D[Vj]為8,則將Vj加入到Path中，然后將P[vJ的前驅(qū)設(shè)置為w,并修改最短路徑D[vJ=D[w]+s(w,V)。重復(fù)步驟(4)。

根據(jù)以上思路，利用MapX控件，結(jié)合可視化編程語(yǔ)言,對(duì)武漢市地圖矢量化，去除多余的結(jié)點(diǎn)，構(gòu)建拓?fù)潢P(guān)系，結(jié)合改進(jìn)的算法，進(jìn)行編程，其實(shí)現(xiàn)的界面如圖4所示。

3結(jié)語(yǔ)

本文在研究現(xiàn)有的Dikjsrta算法的基礎(chǔ)上，討論了有障礙物存在的Dikjsrta的算法，并對(duì)其存儲(chǔ)結(jié)構(gòu)進(jìn)行了一點(diǎn)小的改進(jìn)，給出了具體的實(shí)現(xiàn)過(guò)程，提高了存儲(chǔ)效率。存在的不足是沒(méi)有對(duì)時(shí)間與空間復(fù)雜度進(jìn)行量化，另外，對(duì)其搜索方法

也沒(méi)有加以改進(jìn)，這將是下一步努力改進(jìn)的方向。

圖4障礙特存在的最短路徑展示圖

20211116_6193be3cc09ae__障礙物存在的最短路徑算法及其在車載導(dǎo)航中的應(yīng)用