基于Prim算法的旅游線路設(shè)計(jì)

林越

摘 要：三亞市位于海南島的最南端，是中國(guó)最南部最著名的濱海旅游城市。本文以三亞市旅游風(fēng)景區(qū)為例， 以五日游為主題， 結(jié)合旅游景區(qū)景點(diǎn)知名度、門票價(jià)格、景點(diǎn)距離和各景點(diǎn)的停留時(shí)間，把各景點(diǎn)看成圖的各頂點(diǎn)，距離與知名度綜合看成圖的邊的權(quán)重，然后利用 Prim算法尋找該圖的最小生成樹，給出了最佳旅游線路的設(shè)計(jì)方案。為游客或考察者到三亞市參觀考察提供理論依據(jù)和參考。

關(guān)鍵詞：Prim算法；旅游線路；最小生成樹；線路規(guī)劃

對(duì)于觀光旅游、文化考察或旅行社，選擇設(shè)計(jì)合理的旅游線路達(dá)到省時(shí)省錢的最佳效果是首先考慮的事情。三亞市位于海南島最南端，是中國(guó)最南部的濱海旅游城市。三亞市地處熱帶地區(qū)，是海南最美麗的旅游勝地，由其獨(dú)特的地理位置及氣候，吸引著大批的游客觀光旅游。

把每個(gè)旅游景點(diǎn)看作圖中的一個(gè)節(jié)點(diǎn)，各景點(diǎn)之間的公路看作圖中對(duì)應(yīng)節(jié)點(diǎn)間的邊，各條公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)，所給各景點(diǎn)間的公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，遍游洛陽(yáng)市的各個(gè)景點(diǎn)的最佳旅行線路問題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從定點(diǎn)出發(fā)，行遍所有頂點(diǎn)至少一次再回到定點(diǎn)，使得總權(quán)（路程或時(shí)間）最小，此即最佳旅行商回路問題。由于旅行商問題NP-難題，該問題轉(zhuǎn)化為用Prim算法找加權(quán)網(wǎng)絡(luò)圖的生成樹代替其的近似解。

一、旅游線路的設(shè)計(jì)原則與圖的生成

三亞市區(qū)主要景點(diǎn)分布圖和三亞周邊地區(qū)旅游圖，各旅游點(diǎn)之間的路程、每個(gè)景點(diǎn)的最佳逗留時(shí)間等信息可以登陸三亞旅游官方政務(wù)網(wǎng)（www.sanyatour.gov.cn）。首先假設(shè)公路沒有等級(jí)差別，即可將所有路面狀況視為等同。其次假設(shè)經(jīng)過每個(gè)景點(diǎn)只逗留一次，對(duì)于游客來說，要求在最短時(shí)間內(nèi)用最少的錢來旅游最多的景點(diǎn)，考慮到無論采取哪種方案，在門票的花費(fèi)上均相同，且路費(fèi)在速度確定的情況下可由路程的多少來求得，故可以簡(jiǎn)化模型而只考慮路程的因素，從而把問題轉(zhuǎn)化為求最短的旅游線路問題。

把每個(gè)旅游景點(diǎn)看作圖中的一個(gè)節(jié)點(diǎn)，各景點(diǎn)之間的公路看作圖中對(duì)應(yīng)節(jié)點(diǎn)間的邊，各條公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)，所給各景點(diǎn)間的公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖G，遍游洛陽(yáng)市的各個(gè)景點(diǎn)的最佳旅行線路問題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)出發(fā)，行遍所有頂點(diǎn)至少一次再回到定點(diǎn)，使得總權(quán)（路程或時(shí)間）最小，此即最佳旅行商回路問題。

注：1南山祠，2天涯海角，3大小洞天，4亞龍灣森林公園，5大東海，6三亞灣，7鹿回頭，8千古情，9蜈支洲島，10呀諾達(dá)，11珠江南田溫泉，12亞馬遜叢林水樂園，13三亞奇幻藝術(shù)體驗(yàn)館，14檳榔谷，15鳳凰島，16西島，17分界洲島，18猴島，19鳥巢度假村，20鳳凰嶺公園

二、Prim算法及路徑的求法

（一）算法設(shè)計(jì)

Prim算法是構(gòu)造最小生成樹的一種常用方法，其基本思想是：設(shè)無向連通帶權(quán)圖，其中，是圖中的最小生成樹，其中是邊的集合，當(dāng)，時(shí)，算法結(jié)束算法從，，開始，重復(fù)執(zhí)行如下貪心選擇：

從，的所有邊中選取一條權(quán)值最小的邊將其加入集合，同時(shí)將加入，直到為止，此時(shí)，選取到的條邊就構(gòu)成了的一棵最小生成樹。

（二）路徑求法的提出

在基本Prim算法中，兩個(gè)城市之間的距離為歐式距離，即

在旅游路線規(guī)劃的問題中，如果考慮目前景點(diǎn)內(nèi)的旅游人數(shù)，那么距離將是一個(gè)向量，即。為了與歐式距離區(qū)別，這里用表示，則：

從修改后的距離公式可以看出：當(dāng)時(shí)刻游客要到達(dá)的旅游景點(diǎn)內(nèi)的旅游人數(shù)大于其承載量時(shí)，這兩個(gè)旅游景點(diǎn)之間的距離就會(huì)增大，反之則減小。結(jié)合Prim算法就可以動(dòng)態(tài)地經(jīng)行旅游路線的規(guī)劃。

三、算法的實(shí)現(xiàn)

本文針對(duì)旅游者主要關(guān)心的問題——旅游景點(diǎn)的知名度和旅游路線主題等問題，將各景點(diǎn)的知名圖設(shè)定為一定的權(quán)值，并且考慮在各個(gè)不同景點(diǎn)停留的時(shí)間，將Prim算法加以改進(jìn)，以此來滿足該算法在旅游景點(diǎn)路線選擇上的需要，并通過VC++加以實(shí)現(xiàn)，最終得到一條三亞市景區(qū)的最優(yōu)旅游線路。Prim算法主要數(shù)據(jù)結(jié)構(gòu)如下：

#include

#include

#defineMAXV20//最大頂點(diǎn)個(gè)數(shù)

Typedefstruct

int no；//頂點(diǎn)編號(hào)

DataTypeinfo；//頂點(diǎn)其它信息，用于存放頂點(diǎn)其他記錄

VertexType；//頂點(diǎn)類型

Typedefstruct//圖的定義

intedges[MAXU][MAXU]；//鄰接矩陣

intvexnum，arcnum；//頂點(diǎn)弧，弧段數(shù)

VertexTypevexs [MAXU]；//存放頂點(diǎn)信息（包括頂點(diǎn)名稱，知名度權(quán)重）

intmin；//景點(diǎn)停留時(shí)間

Mgraph；//圖的鄰接矩陣類型

把各景點(diǎn)數(shù)據(jù)代入以上算法，可以得到一個(gè)最優(yōu)旅游線路：

鹿回頭鳳凰島三亞灣天涯海角南山祠大小洞天亞馬遜叢林水樂園鳳凰嶺公園千古情三亞奇幻藝術(shù)體驗(yàn)館珠江南田溫泉檳榔谷呀諾達(dá)亞龍灣森林公園鳥巢度假村大東海蜈支洲島西島猴島分界洲島。

四、結(jié)束語(yǔ)

本文把游客旅行線路的模型，進(jìn)行了合理的假設(shè)，簡(jiǎn)化了次要因素，把問題轉(zhuǎn)化為圖論上最佳旅行商回路問題來解決，使問題得到了比較合理的解決。關(guān)于考察者行走線路的模型，考慮到最小時(shí)間與均衡時(shí)間不可能同時(shí)達(dá)到，給出時(shí)間均衡的條件下的模型和算法，以及初步的結(jié)果。因?yàn)樵诮r(shí)考慮的景點(diǎn)數(shù)較多，沒有區(qū)分市內(nèi)景點(diǎn)和周邊地區(qū)的景點(diǎn)，也沒有考慮旅途休息，有一定的局限性。若作為旅游參考，要根據(jù)實(shí)際情況來選擇使用。

參考文獻(xiàn)：

[1]杜玲玲.改進(jìn)的Prim算法在GIs中的應(yīng)用[J].測(cè)繪信息與工程，2006（1）：28-29.

[2]蔣三庚.旅游規(guī)劃[M].北京：首都經(jīng)濟(jì)貿(mào)易大學(xué)出版社，2002.

[3]吳凱.旅游線路設(shè)計(jì)與優(yōu)化中的運(yùn)籌學(xué)問題[J].旅游科學(xué)，2004.

[4]董躍華，李云浩，姜在東.用破圈法實(shí)現(xiàn)普里姆算法[J].江西理工大學(xué)學(xué)報(bào)，2008.

[5]劉平原，張霓.普里姆（Prim）算法另解[J].科學(xué)中國(guó)人，2007.

[6]段智，袁振洲.基于Prim算法的農(nóng)村公路網(wǎng)布局重要度最大樹求解方法[J].公路，2007（5）：111-114.

基金項(xiàng)目：三亞市院地合作項(xiàng)目（NO：2015YD24）。