摘要：本文提出了適用于智能交通系統(tǒng)的基于雙向搜索的改進(jìn)算法。典型的最短路徑算法被認(rèn)為是Dijkstra算法，其時間復(fù)雜度是O（n2）。但一個城市的路網(wǎng)地圖有很多節(jié)點，該算法的時間復(fù)雜度高和解決速度慢。為了改變這種情況，我們從算法的設(shè)計方面進(jìn)行了討論，提出了改進(jìn)的雙向搜索算法。實踐證明，改進(jìn)后的算法能夠提高了搜索速度，適用于智能交通系統(tǒng)。

關(guān)鍵詞：物聯(lián)網(wǎng)；智能交通；路徑規(guī)劃；雙向搜索算法

中圖分類號：U492.22 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599 （2012） 17-0000-02

1 引言

智能交通系統(tǒng)的核心即動態(tài)車輛的路徑規(guī)劃問題，如何能提高路徑規(guī)劃算法的速度是保證整個智能交通更好更快發(fā)展的前提。目前具有代表性的最短路徑算法是Dijkstra算法，其時間復(fù)雜度為O（n2）。但因Dijstra 算法是一個NP完備算法，面對城市交通路網(wǎng)的眾多結(jié)點，此算法的時間復(fù)雜度高，很難滿足導(dǎo)航系統(tǒng)中的實時性要求。本文從算法設(shè)計方面對現(xiàn)有的雙向搜索算法進(jìn)行優(yōu)化，實驗證明，能夠達(dá)到提高算法效率的目的，使其適用于智能交通中的車輛導(dǎo)航系統(tǒng)。

2 算法的優(yōu)化原理

所謂雙向搜索指的是搜索沿兩個方向同時進(jìn)行，正向搜索：從初始結(jié)點向目標(biāo)結(jié)點方向搜索；逆向搜索：從目標(biāo)結(jié)點向初始結(jié)點方向搜索；每個新結(jié)點生成后，不僅要與本隊列中的每個結(jié)點判重，還要和對方隊列中的節(jié)點判重，如果有相同結(jié)點，即發(fā)生雙向搜索相遇事件，搜索完成，搜索步數(shù)等于兩個方向搜索步數(shù)之和，生成的搜索樹是菱形的，極大的減少了搜索結(jié)點的數(shù)量，提高了搜索效率。實驗表明，和單向搜索展開的結(jié)點數(shù)相比，雙向搜索展開的結(jié)點數(shù)至少可以減少1/2，搜索效率明顯提高。

此算法的最優(yōu)狀態(tài)是正向和逆向的搜索在圖中相遇，最不利的情況是正向搜索和逆向搜索沒有相遇的結(jié)點，這樣反而使算法的搜索時間增加了一倍。因此適當(dāng)?shù)姆艑捤阉鹘K止條件才能真正縮短搜索時間。我們的優(yōu)化就是在不增加算法的時間復(fù)雜度基礎(chǔ)上，解決在雙向搜索中結(jié)點沒有相遇的情況。

算法的優(yōu)化

在搜索過程中，將每次搜索到的新結(jié)點向源結(jié)點和目標(biāo)結(jié)點的連線做投影，計算從正向搜索到的新結(jié)點的投影到源結(jié)點的距離和從逆向搜索到的新結(jié)點的投影到目標(biāo)結(jié)點的距離，并計算這兩個距離的和，如果距離之和比源結(jié)點和目標(biāo)結(jié)點的連線的直線距離長，我們認(rèn)為雙向搜索不會有重合點，立刻停止某一方向的路徑搜索，繼續(xù)另一方向的結(jié)點搜索，雙向搜索中選擇某個方向繼續(xù)進(jìn)行搜索或某個方向停止搜索，主要取決于哪個方向的結(jié)點個數(shù)較少，就向那個方向進(jìn)行擴展。眾所周知，“兩點之間直線距離最短”，如果我們所要尋找的結(jié)點恰好在同一條邊上，這條邊就是我們要找的最短路徑，否則，和兩點間連線的夾角最小的邊是最短路徑的可能性較大。如圖1所示，在城市路網(wǎng)中搜索兩點A和E之間的最短路徑的優(yōu)化后算法的步驟如下：

（1）結(jié)點A為出發(fā)地，結(jié)點E為目的地。在結(jié)點A和結(jié)點E之間，建立一條連線AE，若AE之間存在一條邊和AE連線重合，則這條邊就是我們所求的最短路徑。

（2）若不滿足上述條件，則我們從出發(fā)點A和目的地E同時向中部搜索與AE這條直線夾角最小的邊，在搜索過程中，每次都選擇結(jié)點個數(shù)較少的那個方向先擴展。

（3）重復(fù)步驟（2）直到兩個方向的搜索能匯合于同一結(jié)點或同一條邊。把兩個方向搜索過的結(jié)點聚集，就能得出從A到E的完整最短路徑。

（4）在搜索過程中，將雙向搜索到的新結(jié)點向AE直線做投影，計算從A方向搜索到的結(jié)點的投影到A的距離和從E方向搜索到的結(jié)點的投影到E的距離，并計算這兩個距離之和，如果距離之和比AE直線距離長，我們就認(rèn)為雙向搜索不會有重合點，立刻停止某一方向的路徑搜索，繼續(xù)向結(jié)點個數(shù)較少的那個方向進(jìn)行擴展，搜索結(jié)果為單向擴展的結(jié)點為所求的最短路徑。

3 路徑規(guī)劃算法設(shè)計

3.1 算法的實現(xiàn)。設(shè)置兩個隊列c：array[0..1，1..maxn] of jid，分別表示正向搜索和逆向搜索的擴展隊列；兩個頭指針head：array[0..1] of integer 分別表示正向搜索和逆向搜索中當(dāng)前將擴展結(jié)點的頭指針；設(shè)置兩個尾指針tail：array[0..1] of integer 分別表示正向搜索和逆向搜索的尾指針。

主程序：選擇節(jié)點數(shù)較少且隊列未空、未滿的方向先擴展

if （tail[0]<=tail[1]） and not（（head[0]>=tail[0]）or（tail[0]>=maxn）） then expand（0）；

if （tail[1]<=tail[0]） and not（（head[1]>=tail[1]）or（tail[1]>=maxn）） then expand（1）；

如果一方搜索終止，繼續(xù)另一方的搜索，直到兩個方向都終止

if not（（head[0]>=tail[0]）or（tail[0]>=maxn）） then expand（0）；

if not（（head[1]>=tail[1]）or（tail[1]>=maxn）） then expand（1）；

Until （（head[0]>=tail[0]）or（tail[0]>=maxn）） And （（head[1]>=tail[1]）or（tail[1]>=maxn））

通過實驗表明，雙向搜索和單向搜索展開的結(jié)點數(shù)相比至少減少了1/2，在本項目中采用的鄰接表存儲并采用雙向搜索算法，能大大減少存儲空間并有效降低算法的時間復(fù)雜度。

3.2 實驗及結(jié)果分析。為了驗證算法的可行性，我們分別用經(jīng)典的Dijstra算法和優(yōu)化后的雙向搜索算法對長春市區(qū)的部分街道進(jìn)行最短路徑的搜索。在搜索過程中，我們主要搜索的是長春市的主干道，忽略了一些小的胡同。如下部分長春市地圖中共存儲189個結(jié)點和567條弧。對同一起點和終點完成最短路徑搜索，兩種算法搜索的結(jié)點個數(shù)和花費的時間如表1所示。

4 結(jié)論

本文的路徑規(guī)劃算法采取鄰接表的存儲方式，并在此拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上對雙向搜索法進(jìn)行優(yōu)化，對雙向搜索算法中雙向結(jié)點搜索不相遇而導(dǎo)致的時間復(fù)雜度增加問題，通過停止一方搜索給出了解決的辦法，使此算法適用于智能交通中對路徑規(guī)劃速度的要求，并給出了在此拓?fù)浣Y(jié)構(gòu)中交通管制帶來的單向行駛問題在本算法中的解決方式。大部分的雙向搜索都能在圖中相遇，雖然個別沒有在圖中相遇的，此算法也能得到相應(yīng)的解，通過實驗表明此算法雖然不能每次都得到一個最優(yōu)解，但最終的理論研究和案例分析的結(jié)果表明改進(jìn)后的算法能夠克服以往算法的不足，符合智能交通中路徑規(guī)劃的快速性要求，在實際應(yīng)用中是可行的。

參考文獻(xiàn)：

[1]趙亦林.車輛定位與導(dǎo)航系統(tǒng)[M].譚國真.北京：電子工業(yè)出版社，1999：110-132.

[2]Lu Ruqian.Artificial intelligence[M].Beijing：Science Press，1989

[基金項目]吉林省教育廳科研計劃項目（吉教科[2012] 380）