基于prim算法的陜西省旅游景點線路規劃

葉美麗

（商洛學院數學與計算機應用學院，陜西 商洛 726000）

1 引言

旅游線路的設計是旅游者和旅行社都十分關注的問題，好的旅游線路設計，不僅可以使游客盡享優美風光，而且使游客的抱怨值降到最低。科學設計旅游線路是旅行社的需要，也是一個地區旅游業發展的需要。旅游景區是一個旅游目的地系統中的重要吸引物，在地理位置上具有不可移動的性質，因而，在旅游景區的位置已定的情況下，謀求最短旅游線路，不僅可以減少旅游者的生理疲勞，而且可以相對增加游玩時間，提高旅游效率，也可使旅游公司降低成本。本文將采用prim算法來研究陜西省著名旅游景區間最短旅游線路的構建。

2 實證分析

2.1 陜西省旅游景區概述

陜西簡稱陜或秦，位于我國內陸腹地，黃河中游，是中國毗鄰省市區最多的省份。陜西省旅游景點眾多，周、秦、漢、唐這些中國古代的輝煌時期給陜西留下了豐厚的人文遺產，黃土高原、秦嶺巴山的自然風光也令人陶醉。陜西全省南北長約870 km，東西寬200～500 km，土地面積 20.58萬 km2，占全國土地面積的2.1%。北山和秦嶺把陜西分為三大自然區：北部是陜北高原，南部是秦巴山區，中部是關中平原，。陜西境內主要河流有黃河、渭河、漢江、嘉陵江等。因而，陜西省的古文化資源非常豐富，旅游景區眾多，其中世界遺產景點2個，世界地質公園1個，國家5A景區7個和國家風景名勝區3個，以西安火車站A為起點（見表 1）。

表1 陜西省著名旅游景區統計

圖是一種非線性結構，在工程、數學、計算機等方面有廣泛的用途。圖由兩個集合V和E組成，其中，V是頂點的有窮非空集合，E是V中頂點偶對的有窮集合，通常情況下，將圖G中的頂點集和邊集分別記為V（G）和E（G）。將陜西省的旅游景區作為圖中的頂點，那么連接景區之間的交通線路即為圖中的邊。游客在陜西省進行旅游活動時，一般以西安火車站作為旅游起點，故將西安火車站看作是圖中的一個頂點?；谝陨咸攸c，整個圖可以看作是有向連通圖。

2.2 引入最小生成樹

圖1 旅游路線規劃圖

對于連通網絡 G=（V，E），邊是帶權的（在此處，邊是連接景區之間的交通線路，權是該交通線路的長度，即景區之間的距離），因而G的生成樹的各邊也是帶權的，我們把生成樹各邊的權值總和稱為生成樹的權，并把權最小的生成樹稱為G的最小生成樹（Minimum Spanning Tree）。最小生成樹是數據結構中的一種思想，它應用于圖論中有向連通圖、無向連通圖、網絡等，生成樹是對連通圖所做的一種遍歷，最小生成樹是對連通網絡所做的一種特殊遍歷，除在數據結構中的應用之外，現實生活中有許多重要用途。在旅游線路的設計中使用此方法，構造旅游線路的最短路徑。

2.3 構建連通圖

2.3.1 構建鄰接矩陣。假定，在同等路徑長度的道路選擇上，首選高速公路和國道，最壞狀態下，選擇省級公路。測得有道路連接的各個景區之間的最小距離值，以公里為單位，其中，各旅游景區之間的距離值如表2。

表2 陜西省及各旅游景區間距離值

2.3.2 構建連通圖。將陜西省的各個著名景區和西安火車站為起點均抽象化為頂點，頂點之間的道路抽象化為連接兩個頂點之間的邊，將圖1和矩陣構造成連通圖G14=(V，E)，其中各景點形成的頂點集合為：V(G)={A，B，C，D，E，F，G，H，I，J，K，M，N}，邊的 集 合為 ：E(G)={(A，B)，(A，D)，(A，J)，(A，L)，(A，K)，(A，M)，(B，F)，(B，H)，(B，J)，(B，K)，(C，G)，(C，I)，(C，M)，(D，L)，(D，M)，(D，N)，(E，F)，(F，H)，(F，J)，(G，M)，(H，I)，(I，M)，(J，N)，(K，L)，(K，N)，(L，N)}，其中 ，采用抽象分析法，假定各個頂點之間的邊長不代表各景區之間的距離值，得到如下連通圖G14（圖2）。

圖2 連通圖

2.4 采用prim算法，求最短旅游線路

2.4.1 最小生成樹。在構造最小生成樹算法中有多種算法，其中，大多數構造算法都利用了最小生成樹的MST性質。在此，采用prim算法，利用最小生成樹的MST性質來構造網絡G14的最小生成樹 T14=（U，TE）。初始，U=Φ，TE=Φ。游客到陜西進行旅游活動時，首先要到達西安火車站，將其作為旅游起點，因此，首先從集合V中取頂點A將生成樹T14置為一個僅有一個結點A的樹，U={u0}，U是V的真子集，，然后在所有的一個端點在T中，另一個端點不在T的邊中，找一條權最小的邊（u，v），并把該條邊（u，v）和不在T中的頂點v并入到T的邊集和頂點集中。如此進行下去，直到把所有頂點都并入T中。最后得到最小生成樹T14，如圖3。

圖3 最小生成樹T14

2.4.2 求得最短旅游線路。陜西省到達各個旅游景區的最短旅游線路圖（圖4），即若選擇西安火車站作為旅游的起點和終點， 那么旅游線路遵循 A，M，G，C，I，H，E，F，J，N，D，L，K，B，A 才是最短路徑。 也就是說西安火車站-太白山-天臺山-絲綢之路-法門寺佛文化-黃帝陵-黃河壺口瀑布-合陽洽川-華山-金絲峽-終南山-大雁塔-大唐芙蓉園-華清池-秦始皇陵及兵馬俑-西安火車站，是最短旅游線路。

圖4 最短旅游線路圖

3 結語

求最短旅游線路的問題，也是求耗費時間最短的問題，在旅游線路設計模型方面，通過構建最小生成樹問題，求得從起地出發，游歷其余各個景區的路線，然后回到終點。在一次難得的外出旅游時機中，在有限的時間內游覽更多的旅游景區是游客的訴求，最短旅游線路的設計不僅可以使旅途最短，提高游客時間利用率，減少旅途勞頓，而且能夠使自駕車游客的旅游路線更加有序，使游客的旅游過程更加完美。