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

劉洋洋

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

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

1 Dijkstra 算法

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

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

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

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

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

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

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

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

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

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

圖2 改進(jìn)后的Dijkstra 算法

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

2 算法改進(jìn)

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

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

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

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

BEGIN

對(duì)C 中的每個(gè)約束點(diǎn)，計(jì)算其引導(dǎo)函數(shù)h(c)，按h(c)對(duì)C 進(jìn)行排序

3 實(shí)驗(yàn)驗(yàn)證

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

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

4 結(jié)論

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