當(dāng)前位置:首頁(yè) > 物聯(lián)網(wǎng) > 《物聯(lián)網(wǎng)技術(shù)》雜志
[導(dǎo)讀]摘要:車載導(dǎo)航系統(tǒng)中的動(dòng)態(tài)路線選擇是其必備功能之一,文中分析了經(jīng)典Dijkstra算法存在的不足,并在此基礎(chǔ)上,采用優(yōu)化的鄰接矩陣存儲(chǔ)結(jié)構(gòu),討論了有障礙物存在情況下的最短路徑問(wèn)題。同時(shí)用VC++與MapX實(shí)現(xiàn)了有障礙物存在的動(dòng)態(tài)最短路徑算法。實(shí)驗(yàn)結(jié)果表明,該算法能有效求出有障礙物存在時(shí)的最短路徑。

引言

路徑選擇問(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)用

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國(guó)汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開(kāi)發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來(lái)越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來(lái)越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開(kāi)幕式在貴陽(yáng)舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語(yǔ)權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營(yíng)業(yè)績(jī)穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤(rùn)率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長(zhǎng) 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營(yíng)商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國(guó)電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長(zhǎng)三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡(jiǎn)稱"軟通動(dòng)力")與長(zhǎng)三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉