吳昕宇 羅雪穎
摘要:考慮游客不會在游覽路線上往返、游覽路線不會重復,基于此,本文采用Dijkstra算法解決這個問題。首先,運用圖論知識,將8個景點(包括景石)看成一個賦權無向圖,各景點為圖的頂點,兩景點之間步行最短路線為圖相應兩頂點問的邊,距離為圖兩頂點問邊的權值,得到賦權圖。然后,用Dijkstra算法即可求解最短路線。
關鍵詞:Dijkstra算法圖論知識最短路線
引言
在物質生活條件得到極大發展的今天,人們越來越追求精神文明的建設,越來越多的人愛上旅行而背上背包去旅行。這就致使旅游資源供不應求,一到假期便游人如織,在這樣的情況下,規劃游客的最優路線,規劃游客的觀光時間,最大限度地利用旅游資源便十分重要。
2010年,江蘇省啟動潘安湖土地整理項目,在一片廢墟上建成了一個6500畝湖面的國家級水利風景區。2016年,賈汪被列為“國家全域旅游示范區”首批創建單位。本文選取潘安湖景區的部分景點,完成徐州潘安湖風景區游覽最短路線設計問題。
1模型建立
從景石出發步行游覽①游客服務中心,②陽光草坪,③森林小劇場,④兒童科普體驗區,⑤兒童戲水場,⑥濕地博物館,⑦濕地商業街。建立數學模型,找出所有景點至少觀光1次的距離最短的路線,計算該路線的長度。
本問題要求設計從景石出發,經過①②③④⑤⑥各景點,最終到達⑦濕地商業街,① ⑥所有景點至少觀光1次的距離最短的路線。在實際旅游觀光中,游客在各景點的旅游路線不會重復,而且游客不會在旅游路線上往返,基于此,本文將采用Dijkstra算法來解決此問題。
2.1無向圖定義
一個無向圖G是由一個非空有限集合V(G)和V(G)中某些元素的無序對集合E(G)構成的二元組,記為G=(v(G),E(G))。其中,V(G)={v1,v2,L,v,)稱為圖G的頂點集或節點集,V(G)中的每一個元素
邊上賦權的無向圖稱為賦權無向圖或無向網絡,題目所給出的各景點之間步行最短距離即為無向圖邊上權值。
以各景點為圖G的頂點,兩景點之間步行最短路線為圖G相應兩頂點間的邊,得到圖G。對G的每一邊e,賦以一個實數w(e),即景點之間步行最短距離,稱為e的權,得到賦權圖G。G的子圖的權是指子圖的各邊的權和。
問題便演化為求賦權圖G中指定的兩個頂點uo,vo間的具有最小權的軌。這條軌叫做uo,vo間的距離,記作d(uo,vo)。
2模型求解
本文采用Dijkstra算法編程求解。Dijkstra算法也稱為雙標號法。所謂雙標號,也就是對圖中的點vf賦予兩個標號(,(u),1):第一個標號(p(v1)表示從起點V1到V1的最短路的長度,第二個標號λ3表示在v1到v1的最短路上V1前面一個鄰點的下標,即用來表示路徑,從而可對終點到始點進行反向追蹤,找到U1到vn的最短路。Dijkstra算法適用于每條邊的權數都大于或等于零的情況。下面是Dijkstra算法的內容:
按距離uo從近到遠為順序,依次求uo到G各頂點的最短路線距離,直至。
3模型分析
本文建立的最短路線尋求模型可以推廣應用于交通運輸、車輛路徑規劃、飛機航線安排、城市規劃、經濟管理、物流貨物配送、通訊與網絡技術、計算機科學、信息技術與災害應急調度等領域。如交通查詢系統中需要給用戶提供多條可供選擇的最短路徑。
參考文獻
[1]史峰,王輝等.MATLAB智能算法30個案例分析[D].北京航空航天大學出版社,178-197.
[2]劉雪塵,基于博弈論的多模式動態路徑規劃技術研究[D],吉林大學,2017.