劉洋洋

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

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

1 Dijkstra 算法

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

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

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

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

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

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

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

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

圖2 改進后的Dijkstra 算法

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

2 算法改進

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

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

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

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

BEGIN

對C 中的每個約束點，計算其引導(dǎo)函數(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)路線。首先，本文設(shè)定省會鄭州為出發(fā)點和終點，然后選取少林寺、龍門石窟、白馬寺、云臺山四大景點為旅游目的地，最后規(guī)定約束條件為：游客從鄭州出發(fā)，以最優(yōu)路徑游覽以上四個景點后返回鄭州。條件設(shè)定完畢后，在Dijkstra 算法驗證系統(tǒng)的主界面地圖中標出以上四個景點的準確位置，然后點擊Dijkstra 算法驗證按鈕，通過改進后的Dijkstra 算法計算，系統(tǒng)成功得出了自駕游河南的最優(yōu)路徑。如圖3 所示，從圖中序號順序及高亮顯示的路徑可以看出，自駕游河南的最優(yōu)路線為：鄭州→白馬寺→龍門石窟→少林寺→云臺山→鄭州。經(jīng)實驗結(jié)果表明，改進后的Dijkstra 算法準確高效的計算出了多約束條件下多個景點間的最優(yōu)旅游路徑。

4 結(jié)論

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