基于改進Dijkstra 算法的自駕游最優(yōu)路徑規(guī)劃研究

劉洋洋

（鄭州師范學院地理與旅游學院，河南 鄭州450044）

隨著經(jīng)濟的高速發(fā)展和私家車的大量普及，相比傳統(tǒng)的旅行社組織的團體旅游，如今的游客們越來越傾向于靈活隨性的自駕游。與傳統(tǒng)的集體參團旅游不同，自駕游是一種新的旅游形態(tài)，在選擇景點、參與過程和個人體驗等方面，自駕游能為游客提供更加隨性自如的旅游空間，與以往的旅游方式相比，自駕游所體現(xiàn)的自由化與個性化、靈活性與舒適性、選擇性與季節(jié)性等內在特點，具有更加獨特的魅力和吸引力。據(jù)調查顯示，游客一般喜歡在節(jié)假日外出旅游，但由于假期時間有限，再加上交通條件、天氣條件、駕駛路線等各種因素的影響和制約，因此對游客來說，旅游景點的選擇和出行路線的規(guī)劃就顯得尤為重要。自駕游時，首先需要制定一條科學合理的旅游路線，但由于目前常用的地圖導航軟件一般只提供從游客位置到單個旅游目的地兩點之間的最優(yōu)路徑，并不能對多個旅游景點間的最優(yōu)路徑進行規(guī)化。鑒于此點，為滿足游客自駕游時的具體需求，本文改進了用于求兩點間最短路徑的Dijkstra 算法，以幫助游客實現(xiàn)多景點間的最優(yōu)旅游路線[1-5]。

1 Dijkstra 算法

Dijkstra（迪杰斯特拉）算法是解決最短路徑問題的經(jīng)典算法，常用于在非負權值圖中計算一個節(jié)點到其他所有節(jié)點的最短路徑[7-8]。該算法的計算流程如下所示：

1.1 首先初始化存放已確定的最短路徑節(jié)點集合Y 和未確定的最短路徑節(jié)點集合Q，然后通過權圖的鄰接矩陣來初始化起始點到其他所有節(jié)點的最短路徑長度N。如果起始點到其他節(jié)點有連接弧，則對應的值為連接弧的權值，如果沒有，則默認對應的值為極大值。

1.2 其次選擇N 中的最小值N[i],記N[i]為起始點v 到點i的最短路徑長度，把點i 從集合Q 中取出來放入集合Y 中。

1.3 然后根據(jù)節(jié)點i 來更新修改數(shù)組N 中起始點v 到集合Q 中的節(jié)點M所對應的路徑長度值。

圖1 采用貪婪思想的Dijkstra 算法

1.4 最后重復上述步驟1.2 和步驟1.3 的操作，直到找出起始點到所有節(jié)點的最短路徑為止。

Dijkstra 算法的核心思想是以遍歷的形式找到圖中所有節(jié)點的最短路徑，從而確立目標點的最短路徑。在使用Dijkstra 算法計算最優(yōu)路徑時，為了提高算法效率，一般會在尋找路徑的窮舉過程中加入貪婪思想[9-10]。大致過程如下所示：

1.4.1 設C 為約束節(jié)點的集合，P 為找到的路徑，G 為圖，x為任一約束點，s 為路徑起點，t 為終點。

1.4.2 首先計算s 到C 中每個約束點的距離，并按距離對C中的約束點進行排序，優(yōu)先選擇離s 近的約束點，最后選擇離S遠的約束點。

1.4.3 在計算s 到C 中每個約束點的距離時，會生成以s 為根的最短路樹，從這棵樹中，可直接取到Dijkstra（s，x，G）的結果。如果想取到Dijkstra（s，x，G-C+x）的結果，可修改生成最短路樹的過程，使其遇到約束點時不再生長，即約束點必須是最短路樹的葉節(jié)點[10]。加入貪婪思想的Dijkstra 算法雖能提高算法效率，但在很多情況下計算效果并不理想，如圖1 所示，在計算s到t 的路徑過程中，加入貪婪思想的Dijkstra 算法會按照黑線順序來窮舉約束節(jié)點，這樣很容易計算失敗。相反，如果按紅線順序窮舉約束節(jié)點，成功率就會提高很多。

圖2 改進后的Dijkstra 算法

圖3 河南自駕游最優(yōu)路線

2 算法改進

針對上述問題，該文對Dijkstra 算法進行了改進，使其在計算每個約束點到s、t 的距離時，優(yōu)先選擇離s 近且離t 遠的點，然后再選擇離s 遠且離t 近的點。最后針對每個約束點，計算一個權重，該權重是以約束點為自變量的函數(shù)，稱為指導函數(shù)h。得出權重結果后，對權重進行排序，權重小的優(yōu)先處理。

h（c）= |sc| - |ct| + |xc| （|sc|表示s 到c 的最短距離）(1)

采用改進后的算法，只需經(jīng)過幾輪迭代，便可精確計算出s到x 的最優(yōu)路徑，然后再依次得出x 到剩余約束點的距離，如圖2 所示。在運用該算法進行計算時，各約束點到s、t 的距離只需要計算一次，不用在每次迭代中都重復計算，有效的提高了計算成功率和計算效率。

實現(xiàn)該算法的偽代碼如下所示：FindPath（s，t，G，C）： return P

BEGIN

對C 中的每個約束點，計算其引導函數(shù)h(c)，按h(c)對C 進行排序

3 實驗驗證

對Dijksatra 算法進行優(yōu)化后，本文以C#語言為編程語言，以.net 為開發(fā)環(huán)境，以SQL Server 為數(shù)據(jù)庫，對ArcGIS 進行了二次開發(fā)，成功搭建了基于景點間最優(yōu)路徑規(guī)劃的Dijkstra 算法驗證系統(tǒng)。

鑒于河南省豐富的旅游資源，本文選取了該省若干知名景點作為實驗對象，規(guī)劃了一條自駕游河南的最優(yōu)路線。首先，本文設定省會鄭州為出發(fā)點和終點，然后選取少林寺、龍門石窟、白馬寺、云臺山四大景點為旅游目的地，最后規(guī)定約束條件為：游客從鄭州出發(fā)，以最優(yōu)路徑游覽以上四個景點后返回鄭州。條件設定完畢后，在Dijkstra 算法驗證系統(tǒng)的主界面地圖中標出以上四個景點的準確位置，然后點擊Dijkstra 算法驗證按鈕，通過改進后的Dijkstra 算法計算，系統(tǒng)成功得出了自駕游河南的最優(yōu)路徑。如圖3 所示，從圖中序號順序及高亮顯示的路徑可以看出，自駕游河南的最優(yōu)路線為：鄭州→白馬寺→龍門石窟→少林寺→云臺山→鄭州。經(jīng)實驗結果表明，改進后的Dijkstra 算法準確高效的計算出了多約束條件下多個景點間的最優(yōu)旅游路徑。

4 結論

隨著私家車的大量普及，自駕游已逐漸成為人們外出旅游的首選方式。基于游客自駕游時對景點間最優(yōu)路徑的需求，該文對Dijkstra 算法進行了改進，加入了指導函數(shù)h，使其能夠有效實現(xiàn)多景點間最優(yōu)路徑的計算。最后，實驗結果表明，改進后的Dijkstra 算法成功規(guī)實現(xiàn)了以鄭州為起點和終點，以少林寺、龍門石窟、云臺山和白馬寺為旅游景點的多景點間的自駕游最優(yōu)路徑，從而驗證了該算法的合理性和實用性。