葉美麗

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西 商洛 726000）

1 引言

旅游線路的設(shè)計(jì)是旅游者和旅行社都十分關(guān)注的問題，好的旅游線路設(shè)計(jì)，不僅可以使游客盡享優(yōu)美風(fēng)光，而且使游客的抱怨值降到最低?？茖W(xué)設(shè)計(jì)旅游線路是旅行社的需要，也是一個(gè)地區(qū)旅游業(yè)發(fā)展的需要。旅游景區(qū)是一個(gè)旅游目的地系統(tǒng)中的重要吸引物，在地理位置上具有不可移動(dòng)的性質(zhì)，因而，在旅游景區(qū)的位置已定的情況下，謀求最短旅游線路，不僅可以減少旅游者的生理疲勞，而且可以相對(duì)增加游玩時(shí)間，提高旅游效率，也可使旅游公司降低成本。本文將采用prim算法來研究陜西省著名旅游景區(qū)間最短旅游線路的構(gòu)建。

2 實(shí)證分析

2.1 陜西省旅游景區(qū)概述

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

表1 陜西省著名旅游景區(qū)統(tǒng)計(jì)

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

2.2 引入最小生成樹

圖1 旅游路線規(guī)劃圖

對(duì)于連通網(wǎng)絡(luò) G=（V，E），邊是帶權(quán)的（在此處，邊是連接景區(qū)之間的交通線路，權(quán)是該交通線路的長(zhǎng)度，即景區(qū)之間的距離），因而G的生成樹的各邊也是帶權(quán)的，我們把生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并把權(quán)最小的生成樹稱為G的最小生成樹（Minimum Spanning Tree）。最小生成樹是數(shù)據(jù)結(jié)構(gòu)中的一種思想，它應(yīng)用于圖論中有向連通圖、無向連通圖、網(wǎng)絡(luò)等，生成樹是對(duì)連通圖所做的一種遍歷，最小生成樹是對(duì)連通網(wǎng)絡(luò)所做的一種特殊遍歷，除在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用之外，現(xiàn)實(shí)生活中有許多重要用途。在旅游線路的設(shè)計(jì)中使用此方法，構(gòu)造旅游線路的最短路徑。

2.3 構(gòu)建連通圖

2.3.1 構(gòu)建鄰接矩陣。假定，在同等路徑長(zhǎng)度的道路選擇上，首選高速公路和國(guó)道，最壞狀態(tài)下，選擇省級(jí)公路。測(cè)得有道路連接的各個(gè)景區(qū)之間的最小距離值，以公里為單位，其中，各旅游景區(qū)之間的距離值如表2。

表2 陜西省及各旅游景區(qū)間距離值

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

圖2 連通圖

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

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

圖3 最小生成樹T14

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

圖4 最短旅游線路圖

3 結(jié)語(yǔ)

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