段明義，張 文

(中州大學(xué) 信息工程學(xué)院，河南 鄭州 450044)

?

一種改進(jìn)的交通網(wǎng)絡(luò)路徑選擇算法

段明義，張 文

(中州大學(xué) 信息工程學(xué)院，河南 鄭州 450044)

運(yùn)用人工智能領(lǐng)域的啟發(fā)式搜索方法，以交通網(wǎng)絡(luò)為研究對(duì)象，在深入分析經(jīng)典Dijkstra最短路徑算法的基礎(chǔ)上，提出了一個(gè)基于啟發(fā)式的最短路徑算法，并證明了該方法的有效性。經(jīng)過(guò)對(duì)改進(jìn)算法仔細(xì)分析后，討論了其改進(jìn)之處。結(jié)合具體應(yīng)用，從啟發(fā)函數(shù)、搜索范圍和排序方法等方面，提出了相應(yīng)的改進(jìn)策略，并將其應(yīng)用到仿真試驗(yàn)中。結(jié)果表明：在不同圖層下，該算法具有良好的伸縮性；與已有路徑選擇改進(jìn)算法相比,在不同路徑權(quán)值選擇下，都能夠有效地縮短路徑查找時(shí)間，從而更好地滿足出行需要。同時(shí)，也給出了不同地理距離下初始搜索半徑的參考值。

智能交通系統(tǒng)；限制搜索區(qū)域；啟發(fā)式方法；交通網(wǎng)絡(luò)；路徑搜索；左傾樹(shù)

0 引言

實(shí)現(xiàn)城市的繁榮、有序和快速發(fā)展，一個(gè)基本條件是良好的城市交通系統(tǒng)。但隨著各城市機(jī)動(dòng)車保有量的不斷增加，導(dǎo)致對(duì)交通需求的急劇增加，緊接而來(lái)的一系列如交通擁堵、交通事故頻發(fā)、環(huán)境污染嚴(yán)重及能源短缺等問(wèn)題，給人們生產(chǎn)、生活等帶來(lái)了諸多不便，這些都制約著一個(gè)城市的進(jìn)一步、可持續(xù)的發(fā)展。出行者在交通出行中，一個(gè)經(jīng)常關(guān)心的問(wèn)題是如何迅速選擇一條最優(yōu)的路徑。因此，出行最優(yōu)路徑選擇算法問(wèn)題的研究已迫在眉睫。

求解兩點(diǎn)間的最短路徑問(wèn)題，已經(jīng)有很多學(xué)者做了研究，給出了很多的算法，其中以Dijkstra算法[1]最為經(jīng)典。該算法可以在O(n2)(n為節(jié)點(diǎn)數(shù))時(shí)間復(fù)雜度情況下，求出某初始點(diǎn)到其他與其有路徑相通的點(diǎn)之間的最短路徑。當(dāng)節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，O(n2)級(jí)別的時(shí)間復(fù)雜度是可以接受的，實(shí)際系統(tǒng)中，節(jié)點(diǎn)個(gè)數(shù)往往較多，該級(jí)別的復(fù)雜度就顯得效率低下，因此，直接使用Dijkstra算法的情況不多。

文獻(xiàn)[2-3]針對(duì)堆排序算法做了分析；文獻(xiàn)[2]給出了一種基于左傾樹(shù)的堆排序改進(jìn)算法，在輸入數(shù)據(jù)排列任意的情況下，該算法實(shí)現(xiàn)排序的時(shí)間復(fù)雜性為O(nlogn)；通過(guò)只對(duì)最短路徑上節(jié)點(diǎn)的臨界點(diǎn)處理，在不涉及其他節(jié)點(diǎn)的情況下，文獻(xiàn)[4]對(duì)Dijkstra算法進(jìn)行優(yōu)化，使得計(jì)算的節(jié)點(diǎn)數(shù)大幅減少，從而提高了算法的速度；文獻(xiàn)[5]討論了啟發(fā)式算法在路徑規(guī)劃問(wèn)題中的一些改進(jìn)策略，該方法考慮到了一些計(jì)算機(jī)硬件因素；文獻(xiàn)[6]采用預(yù)先計(jì)算存儲(chǔ)的方法，程序運(yùn)行時(shí)，根據(jù)初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，直接調(diào)用數(shù)據(jù)庫(kù)查詢語(yǔ)句，查詢出事先計(jì)算好的兩點(diǎn)間的距離，如果圖中節(jié)點(diǎn)數(shù)目較多，額外存儲(chǔ)空間開(kāi)銷就較大。

因此，路徑搜索在交通網(wǎng)絡(luò)中是一個(gè)比較復(fù)雜的問(wèn)題，設(shè)計(jì)算法時(shí)，需要考慮多種方面的因素，然后給出最終解決方案。本文將啟發(fā)式的思想引入Dijkstra算法中，并對(duì)搜索區(qū)域加以限制，提出限制搜索區(qū)域的啟發(fā)式最短路徑算法(Restricted Searching Area Heuristic Shortest Path Algorithm, RSAHSPA)，該算法能夠有效縮短路徑搜索時(shí)間，為使用者提供出行依據(jù)。

1 路徑搜索算法描述

1.1 尋徑問(wèn)題網(wǎng)絡(luò)模型

尋徑問(wèn)題是在圖論中研究的熱點(diǎn)之一，目標(biāo)是設(shè)計(jì)一個(gè)算法，尋找圖中從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條通路。城市路網(wǎng)除具有一般路網(wǎng)的特點(diǎn)之外，還有其特殊之處：數(shù)據(jù)量大和結(jié)構(gòu)復(fù)雜。這都使得城市路網(wǎng)的結(jié)構(gòu)變得非常復(fù)雜，現(xiàn)實(shí)中的城市路網(wǎng)實(shí)體只有抽象化為圖論中的網(wǎng)絡(luò)圖后，才能做最佳路徑分析，一般的方法是采用GIS技術(shù)生成其對(duì)應(yīng)的電子地圖。本文的研究在已生成的電子地圖上進(jìn)行，以此討論最短路徑算法的實(shí)現(xiàn)過(guò)程。

1.2 Dijkstra尋徑算法

定義1 圖是由1個(gè)頂點(diǎn)集V和1個(gè)弧集VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，Graph=(V,VR)，其中，VR={|v,w∈V∧P(v,w)}，表示從v到w的1條弧，P(v,w)定義了弧的意義或信息，一般設(shè)置為該弧的權(quán)重[7]。

Dijkstra算法采用貪婪策略，描述如下。

算法1：

(1)初始，從節(jié)點(diǎn)集合V′={vs|vs∈V}出發(fā)，vs為路徑初始節(jié)點(diǎn)。

(3)在所有滿足vi∈V′∧vj∈M的弧中，選擇權(quán)重最小的邊，設(shè)該邊在M中依附的節(jié)點(diǎn)為vj，若vj=ve(ve為路徑目標(biāo)節(jié)點(diǎn))，則算法結(jié)束。

(5)返回(2)。

當(dāng)圖中節(jié)點(diǎn)個(gè)數(shù)很多的時(shí)候，Dijkstra算法的性能就顯得有些低。此時(shí)，為了提高搜索的效率，可以在犧牲一定精確性的情況下達(dá)到提高查找速度的目的。啟發(fā)式算法就是這樣一種策略。在每次擴(kuò)展過(guò)程中，盡量選擇離最終路徑近的那些節(jié)點(diǎn)。

1.3 啟發(fā)式方法

定義2 設(shè)評(píng)價(jià)函數(shù)f(vj)=g(vs,vj)+h(vj,ve)[8]，式中，g(vs,vj)為從初始節(jié)點(diǎn)vs經(jīng)過(guò)尋徑算法到達(dá)節(jié)點(diǎn)vj的權(quán)值之和，且g(vs,vs)=0；h(vj,ve)為節(jié)點(diǎn)vj的代價(jià)函數(shù)，h(ve,ve)=0，它預(yù)測(cè)從vj到終點(diǎn)ve的代價(jià)。一個(gè)點(diǎn)是否能被優(yōu)先選用進(jìn)行搜索，主要由評(píng)價(jià)函數(shù)f(vj)的值來(lái)決定。

引入代價(jià)函數(shù)h(vj,ve)后，每次對(duì)節(jié)點(diǎn)的擴(kuò)散不再是盲目的，而是有方向性的。其值越大，算法的解也就越偏離最優(yōu)解，但同時(shí)時(shí)間耗費(fèi)也越小；其值越小，搜索所花費(fèi)的時(shí)間越大，算法的解也就越逼近最佳解?；趩l(fā)式的路徑搜索算法如下。

算法2：

(4)返回(1)。

定理1 設(shè)有序序列V′={vs,v1,v2,…,vj,…,vn,ve}，j=1,…,n，為使用啟發(fā)式方法求出的從初始點(diǎn)vs到目標(biāo)點(diǎn)ve的路徑上的點(diǎn)，該路徑P′=(vs,v1,v2,…,vj,…,vn,ve)，j=1,…,n，distmin(vk,vl)用來(lái)記錄節(jié)點(diǎn)vk到節(jié)點(diǎn)vl最小權(quán)值之和，若滿足(?vj)[h(vj,ve)≤distmin(vj,ve)∧(vj∈V′)]，則P′為最短路徑。

fp(ve)=gp(vs,ve)+hp(ve,ve)=gp(vs,ve)。

引入記號(hào)d(vk,vl)來(lái)表示邊的權(quán)，則：

即：

2 算法的改進(jìn)

2.1 評(píng)價(jià)函數(shù)

評(píng)價(jià)函數(shù)f(vj)的任務(wù)主要是用來(lái)估計(jì)搜索路徑上某節(jié)點(diǎn)vj的重要性。理論上講，它可以是任意的函數(shù)，具體應(yīng)用中采用什么樣的形式，主要由應(yīng)用而定。一個(gè)節(jié)點(diǎn)的價(jià)值一般從兩方面考慮：搜索到該節(jié)點(diǎn)時(shí)算法已經(jīng)付出的代價(jià)g(vs,vj); 如果選擇從該節(jié)點(diǎn)出發(fā)到達(dá)目標(biāo)節(jié)點(diǎn)ve，算法將要付出的代價(jià)h(vj,ve)。 一般來(lái)說(shuō)，已經(jīng)付出的代價(jià)g(vs,vj)的值是一定的，而最關(guān)鍵的就是根據(jù)具體應(yīng)用來(lái)選擇合適的h(vj,ve)。

在網(wǎng)絡(luò)地圖中，設(shè)兩點(diǎn)vj和ve的坐標(biāo)分別為(xj，yj)與(xe，ye)，常用的啟發(fā)式函數(shù)主要有：

曼哈頓距離：h(vj,ve)=(|xj-xe|+|yj-ye|)；

切比雪夫距離：h(vj,ve)=max{|xj-xe|,|yj-ye|}。

其他形式的代價(jià)函數(shù)也可以選擇，只要滿足最優(yōu)解條件即可。歐氏距離代表了兩點(diǎn)間的直線距離，是一般情況的首選。在此，考慮到計(jì)算機(jī)做乘方和開(kāi)方運(yùn)算，耗時(shí)比加減大很多，故選擇曼哈頓距離作為啟發(fā)函數(shù)。

2.2 搜索區(qū)域

Dijkstra算法的搜索區(qū)域，可近似地看成以初始節(jié)點(diǎn)Vs為圓心所構(gòu)成的一系列同心圓，各個(gè)節(jié)點(diǎn)依離初始節(jié)點(diǎn)的距離遠(yuǎn)近而先后被搜索到。整個(gè)過(guò)程沒(méi)有涉及終點(diǎn)Ve所在的方向或位置，因此，其被搜索到的概率與其他節(jié)點(diǎn)Vj是相同的。若圖中頂點(diǎn)數(shù)目較多，或初始節(jié)點(diǎn)Vs與終點(diǎn)Ve間距離較大，算法實(shí)際運(yùn)行效率將大大降低[10-11]。

啟發(fā)式的搜索方法能夠改變這種狀況。文獻(xiàn)[12]提出了一種矩形限制搜索區(qū)域，縮小了搜索的范圍，提高了效率。在此基礎(chǔ)上，本文將搜索區(qū)域進(jìn)一步縮小，限制在一個(gè)條狀范圍內(nèi)，如圖1所示。以初始節(jié)點(diǎn)Vs和終點(diǎn)Ve分別畫半徑為r(r為搜索半徑，該值可調(diào)整)的圓，與兩圓相切的直線分別為L(zhǎng)1和L2，則兩直線與兩圓圍成的條狀區(qū)域即為搜索區(qū)域。

圖1 搜索區(qū)域示意圖Fig.1 Schematic diagram of searching area

實(shí)際算法實(shí)現(xiàn)時(shí)，為了進(jìn)一步簡(jiǎn)化計(jì)算，可以將搜索區(qū)域的橫坐標(biāo)值進(jìn)一步簡(jiǎn)化為(xs-r,xe+r)，而縱坐標(biāo)軸限定在兩平行線L1，L2間不變。

初始時(shí)，根據(jù)經(jīng)驗(yàn)，設(shè)置r值，運(yùn)行算法，進(jìn)行搜索，如果搜索到終點(diǎn)，則算法結(jié)束，否則，按預(yù)設(shè)增量增大r值，在一個(gè)更大的搜索區(qū)域上進(jìn)行搜索，直至搜索到終點(diǎn)。最壞的情況即是搜索擴(kuò)展到了整個(gè)區(qū)域。實(shí)際算法中，搜索半徑r值設(shè)定為一個(gè)遞增序列ri，形如ri={1, 1.5, 2, 2.5, 3, …}，如果根據(jù)前一個(gè)半徑序列的值沒(méi)有在搜索區(qū)域內(nèi)找到終點(diǎn)，則選擇半徑序列中的下一個(gè)值來(lái)進(jìn)行搜索。

由于程序首先考慮的是位于條狀區(qū)域內(nèi)的點(diǎn)，而不是所有的點(diǎn)，這樣就減少了對(duì)無(wú)用節(jié)點(diǎn)的考察，加速了程序的運(yùn)行。

2.3 排序方法

定義3 堆是滿足下列性質(zhì)的數(shù)列{k1,k2,…,kn}：

前者稱為小頂堆，后者稱為大頂堆[7]。在此主要關(guān)注前者，并且采用一種改進(jìn)的堆結(jié)構(gòu)來(lái)進(jìn)行排序。

左傾樹(shù)排序方法是眾多排序方法中較快的一種。在原始輸入數(shù)據(jù)任意排列的情況下，該算法的時(shí)間復(fù)雜度可以達(dá)到O(nlog2n)[2]。左傾樹(shù)實(shí)際上就是經(jīng)典堆結(jié)構(gòu)的一個(gè)改進(jìn)。

定義4 左傾樹(shù)T是1棵具有特殊性質(zhì)的二叉樹(shù),其中每個(gè)結(jié)點(diǎn)滿足下列性質(zhì)。

(1)給樹(shù)中每個(gè)節(jié)點(diǎn)k賦予1個(gè)Ek值：如果該節(jié)點(diǎn)具有不多于1個(gè)孩子，則Ek=1；如果該節(jié)點(diǎn)有兩個(gè)孩子k1和k2，則Ek=min{Ek1,Ek2}+1。

(2)根節(jié)點(diǎn)的值小于(僅考慮小頂堆)以該節(jié)點(diǎn)為根的子樹(shù)上所有節(jié)點(diǎn)的值；如果節(jié)點(diǎn)k無(wú)左孩子，則它必然無(wú)右孩子；如果k同時(shí)具有兩個(gè)孩子(分別為k1和k2)，則左孩子節(jié)點(diǎn)的Ek值Ek1大于等于右孩子節(jié)點(diǎn)的Ek值Ek2。

用左傾樹(shù)實(shí)現(xiàn)排序的過(guò)程和普通的堆排序相似，也分為構(gòu)造和排序兩個(gè)階段：第1階段執(zhí)行構(gòu)造過(guò)程，輸入含有n個(gè)節(jié)點(diǎn)的待排序序列，經(jīng)過(guò)n-1次左傾樹(shù)的合并過(guò)程，構(gòu)造1棵新的左傾樹(shù)；第2階段執(zhí)行排序過(guò)程，再經(jīng)過(guò)n-1次左傾樹(shù)的合并過(guò)程，從而最終實(shí)現(xiàn)排序。

合并過(guò)程描述如下(僅考慮兩棵樹(shù)的情況)：

(1)如果有一棵左傾樹(shù)為空樹(shù)，合并后的結(jié)果為另一棵左傾樹(shù)。

(2)將根節(jié)點(diǎn)值小的左傾樹(shù)的右子樹(shù)與另一棵左傾樹(shù)進(jìn)行合并，使用合并后的結(jié)果代替該右子樹(shù)。

(3)如果合并后的結(jié)果不滿足左傾樹(shù)的條件，則可以通過(guò)交換該左傾樹(shù)的左右子樹(shù)，使之成為一棵左傾樹(shù)。

假設(shè)一棵左傾樹(shù)含有n個(gè)節(jié)點(diǎn)，由于“左傾”的性質(zhì)，從該樹(shù)根結(jié)點(diǎn)出發(fā)，一路沿著右子樹(shù)向前走，最多走log2(n+1)步(等于樹(shù)的高度)。又因?yàn)樽髢A樹(shù)的合并過(guò)程總是從右子樹(shù)方向進(jìn)行的，這樣至多只需要O(log2n)步就可以訪問(wèn)該樹(shù)右邊的子樹(shù)，同時(shí)完成合并工作，這是最壞的情況。顯然，左傾樹(shù)樹(shù)型最壞的情況是當(dāng)它的左右子樹(shù)較為平衡時(shí)；最佳樹(shù)型是當(dāng)它的所有節(jié)點(diǎn)的右指針為空時(shí)。

3 結(jié)果與分析

試驗(yàn)?zāi)康氖菫榱俗C明改進(jìn)算法在某市電子地圖不同圖層上尋徑的有效性，并分析搜索半徑r和兩點(diǎn)間直線距離k對(duì)有效性的影響。仿真試驗(yàn)在處理器為Intel酷睿i5 4570(3.2 GHz)、內(nèi)存4 GB、硬盤1 TB、操作系統(tǒng)為Microsoft Windows 7的微機(jī)環(huán)境下進(jìn)行。

3.1 尋徑時(shí)間

該市電子地圖有多個(gè)不同的圖層，分別含有508，1 033，2 013，3 998條邊。選定固定的兩個(gè)地理位置作為起點(diǎn)和終點(diǎn)，兩點(diǎn)間直線距離為k=10 km，同時(shí)，搜索半徑r設(shè)定為2 km，以尋徑時(shí)間作為衡量算法效率的指標(biāo)參數(shù)，分別從地理距離和擁堵時(shí)間兩方面來(lái)設(shè)定邊的權(quán)值，以對(duì)Dijkstra算法、RRSA算法和RSAHSPA算法的效率進(jìn)行測(cè)試，其中RRSA指矩形限制搜索區(qū)域算法[12]。

圖2描述了在地理距離最短權(quán)值下3種算法的尋徑時(shí)間，在開(kāi)始邊數(shù)為508的條件下，Dijkstra、RRSA和RSAHSPA所花費(fèi)的尋徑時(shí)間分別為2 110，1 143，632 ms。隨著邊數(shù)的逐漸增加，3種算法花費(fèi)的尋徑時(shí)間都逐漸增加，但Dijkstra比RRSA和RSAHSPA增加得更快，同時(shí)，RRSA和RSAHSPA所花費(fèi)的尋徑時(shí)間增加變化緩慢，并且RSAHSPA算法一直低于RRSA算法。當(dāng)圖層邊數(shù)增加為3 998條時(shí)，3種算法的尋徑時(shí)間分別為34 412，6 617，3 216 ms。圖3描述了在擁堵時(shí)間最短權(quán)值下3種算法的尋徑時(shí)間，因此，本文所提方法優(yōu)于其他兩種方法。

圖2 尋路訪問(wèn)時(shí)間對(duì)比(按地理距離最短)Fig.2 Comparison of path finding access time(by geographical distance shortest)

圖3 尋路訪問(wèn)時(shí)間對(duì)比(按擁堵時(shí)間最短)Fig.3 Comparison of path finding access time(by congestion time shortest)

3.2 初始半徑r的選擇

保持上述試驗(yàn)運(yùn)行環(huán)境不變，針對(duì)RSAHSPA算法修改k數(shù)值，以地理距離最短作為路徑權(quán)重的情況為例，測(cè)試搜索半徑r值對(duì)算法所花費(fèi)尋徑時(shí)間的影響。取k=10 km，初始半徑r分別選擇r=1,1.5,2,2.5,3 km，運(yùn)行結(jié)果圖4所示。

圖4 不同初始r值對(duì)算法訪問(wèn)時(shí)間的影響(k=10 km)Fig.4 Influence of different initial r values on accesstime of algorithm (k=10 km)

另外，取k=5 km，初始半徑r分別選擇r=0.5,0.7，1,1.5,2 km，運(yùn)行結(jié)果圖5所示。

圖5 不同初始r值對(duì)算法訪問(wèn)時(shí)間的影響(k=5 km)Fig.5 Influence of different initial r values on accesstime of algorithm (k=5 km)

為了對(duì)照，再取k=20 km，初始半徑r分別選擇r=1,2,4,6,8 km，運(yùn)行結(jié)果圖6所示。

圖6 不同初始r值對(duì)算法訪問(wèn)時(shí)間的影響(k=20 km)Fig.6 Influence of different initial r values on accesstime of algorithm (k=20 km)

試驗(yàn)結(jié)果表明，在不同數(shù)值k的條件下，隨著圖層中邊數(shù)的增加，相同r值下，RSAHSPA算法的尋徑時(shí)間都會(huì)逐漸增大；在同一個(gè)數(shù)值k的條件下，不同的初始r值對(duì)RSAHSPA算法的尋徑時(shí)間影響顯著。例如，在圖4的k=10 km條件下，初始r=2, 2.5, 3 km的運(yùn)行曲線幾乎在一起，說(shuō)明在設(shè)置r=2 km 的搜索區(qū)域內(nèi)，已經(jīng)能夠找到一條起點(diǎn)到終點(diǎn)的最短路徑，此時(shí)，增加r值，對(duì)尋徑時(shí)間影響不大；r=1, 1.5 km需要更多的運(yùn)行時(shí)間，說(shuō)明在這樣的搜索范圍內(nèi)沒(méi)有找到最短路徑，需要增加r值在一個(gè)更大的范圍內(nèi)進(jìn)行搜索，因此時(shí)間花費(fèi)更多。圖5和圖6中，當(dāng)r分別增加至1 km和4 km后，再增大搜索半徑，對(duì)尋徑時(shí)間影響不大。根據(jù)圖4～圖6結(jié)果分析，r=k/5時(shí)算法運(yùn)行效果最好，繼續(xù)增加r值，效率提高不明顯。

4 結(jié)論

本文將啟發(fā)式方法應(yīng)用到經(jīng)典的最短路徑算法之中，給出了網(wǎng)絡(luò)地圖中的一個(gè)新的路徑搜索算法。同時(shí)，在啟發(fā)式函數(shù)搜索范圍和排序方法方面，討論了算法的改進(jìn)之處，并將其應(yīng)用到實(shí)現(xiàn)的算法中。仿真試驗(yàn)結(jié)果證明了新的路徑搜索算法的優(yōu)越之處，與已有路徑選擇改進(jìn)算法相比，能夠有效縮短路徑查找時(shí)間，從而更好地滿足出行需要。

[1] DIJKSTRA E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematics, 1959, 1(1): 269-271.

[2] 湯彬. 一個(gè)用左傾樹(shù)實(shí)現(xiàn)O(nlog2n)排序的算法[J]. 微型電腦應(yīng)用, 1996 (1): 79-83. TANG Bin. A Sorting Algorithm Taking O(nlog2n) Time Using Leftist Tree[J]. Microcomputer Applications, 1996 (1): 79-83.

[3] WEISS M A, 陳越. 數(shù)據(jù)結(jié)構(gòu)與算法分析: C語(yǔ)言描述 [M]. 2版. 北京:人民郵電出版社, 2005. WEISS M A, CHEN Yue. Data Structures and Algorithm Analysis in C Language[M]. 2nd ed. Beijing: Posts & Telecom Press, 2005.

[4] 章永龍. Dijkstra最短路徑算法優(yōu)化[J]. 南昌工程學(xué)院學(xué)報(bào), 2006, 25(3): 31-32. ZHANG Yong-long. Optimization of Dijkstra Algorithm [J]. Journal of Nanchang Institute of Technology, 2006, 25(3): 31-32.

[5] 張本群. 基于啟發(fā)式算法的路徑規(guī)劃[J]. 計(jì)算機(jī)仿真, 2012, 29(10): 341-343. ZHANG Ben-qun. Path Planning Based on Heuristic Algorithm [J]. Computer Simulation, 2012, 29(10): 341-343.

[6] AGRAWAL R, JAGADISH H V. Materialization and Incremental Update of Path Information[C]∥Proceedings of the 5th International Conference on Data Engineering. Los Angeles:IEEE, 1989: 374.

[7] 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) [M]. 北京:清華大學(xué)出版社, 1997. YAN Wei-min, WU Wei-min. Data Structure (in C Language) [M]. Beijing: Tsinghua University Press, 1997.[8] 馬少平. 人工智能[M]. 北京:清華大學(xué)出版社, 2004: 32-34. MA Shao-ping. Artificial Intelligence[M]. Beijing: Tsinghua University Press, 2004: 32-34.

[9] 尼爾松 N J. 人工智能[M]. 北京:機(jī)械工業(yè)出版社, 1999:145-150. NILSSON N J. Artificial Intelligence: A New Synthesis [M]. Beijing: China Machine Press, 1999:145-150.

[10]張錦明, 洪剛, 文銳, 等. Dijkstra最短路徑算法優(yōu)化策略[J]. 測(cè)繪科學(xué), 2009, 34(5): 105-106. ZHANG Jin-ming, HONG Gang, WEN Rui, et al. Optimization Strategies of the Dijkstra’s Shortest Route Algorithm [J]. Science of Surveying and Mapping, 2009, 34(5): 105-106.

[11]鄧方安, 雍龍泉, 周濤, 等. 基于“矩陣乘法”的網(wǎng)絡(luò)最短路徑算法[J]. 電子學(xué)報(bào), 2009, 37(7): 951-956. DENG Fang-an,YONG Long-quan, ZHOU Tao, et al. Shortest Path Problem Algorithm in Network Based on Matrix Multiplication [J]. Acta Electronica Sinica, 2009, 37(7): 951-956.

[12]王海梅, 周獻(xiàn)中. 一種限制搜索區(qū)域的最短路徑改進(jìn)算法[J]. 南京理工大學(xué)學(xué)報(bào): 自然科學(xué)版, 2009, 33(5): 638-642. WANG Hai-mei, ZHOU Xian-zhong. Improved Shortest Path Algorithm for Restricted Searching Area[J]. Journal of Nanjing University of Science and Technology: Natural Science Edition, 2009, 33(5): 638-642.

An Improved Path Selecting Algorithm for Traffic Network

DUAN Ming-yi, ZHANG Wen

(School of Information Engineering, Zhongzhou University, Zhengzhou Henan 450044, China)

By using heuristic search method in artificial intelligence, focusing on transport network, on the basis of in-depth analysis of the classical Dijkstra shortest path algorithm, a shortest path algorithm based on heuristic and proved the effectiveness of this method is proposed. After a careful analysis of the improved algorithm, the respects needed to be improved are discussed. Combining with specific applications, the corresponding improvement strategies are proposed from the aspect of heuristic function, searching range and sorting method, and these improvements are applied to the simulation experiment. The result shows that (1)the proposed algorithm has good scalability in different layers; (2) compared with the existing improved path selecting algorithm, the proposed one can effectively shorten the path finding time under different path weight options, thereby to better meet the travel needs. The reference values of the initial search radius for different geographical distance are also given.

ITS; restricted searching area; heuristics; traffic network; path searching; leftist tree

2016-02-16

河南省科技攻關(guān)計(jì)劃項(xiàng)目(162102210327)

段明義(1978-)，男，河南鄭州人，碩士，副教授.(duanmingyi@126.com)

10.3969/j.issn.1002-0268.2016.11.018

U491, TP311

A

1002-0268(2016)11-0120-06