基于Prim算法的旅游线路设计

林越

摘 要：三亚市位于海南岛的最南端，是中国最南部最著名的滨海旅游城市。本文以三亚市旅游风景区为例， 以五日游为主题， 结合旅游景区景点知名度、门票价格、景点距离和各景点的停留时间，把各景点看成图的各顶点，距离与知名度综合看成图的边的权重，然后利用 Prim算法寻找该图的最小生成树，给出了最佳旅游线路的设计方案。为游客或考察者到三亚市参观考察提供理论依据和参考。

关键词：Prim算法；旅游线路；最小生成树；线路规划

对于观光旅游、文化考察或旅行社，选择设计合理的旅游线路达到省时省钱的最佳效果是首先考虑的事情。三亚市位于海南岛最南端，是中国最南部的滨海旅游城市。三亚市地处热带地区，是海南最美丽的旅游胜地，由其独特的地理位置及气候，吸引着大批的游客观光旅游。

把每个旅游景点看作图中的一个节点，各景点之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给各景点间的公路网就转化为加权网络图，遍游洛阳市的各个景点的最佳旅行线路问题就转化为在给定的加权网络图中寻找从定点出发，行遍所有顶点至少一次再回到定点，使得总权（路程或时间）最小，此即最佳旅行商回路问题。由于旅行商问题NP-难题，该问题转化为用Prim算法找加权网络图的生成树代替其的近似解。

一、旅游线路的设计原则与图的生成

三亚市区主要景点分布图和三亚周边地区旅游图，各旅游点之间的路程、每个景点的最佳逗留时间等信息可以登陆三亚旅游官方政务网（www.sanyatour.gov.cn）。首先假设公路没有等级差别，即可将所有路面状况视为等同。其次假设经过每个景点只逗留一次，对于游客来说，要求在最短时间内用最少的钱来旅游最多的景点，考虑到无论采取哪种方案，在门票的花费上均相同，且路费在速度确定的情况下可由路程的多少来求得，故可以简化模型而只考虑路程的因素，从而把问题转化为求最短的旅游线路问题。

把每个旅游景点看作图中的一个节点，各景点之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给各景点间的公路网就转化为加权网络图G，遍游洛阳市的各个景点的最佳旅行线路问题就转化为在给定的加权网络图中寻找从给定点出发，行遍所有顶点至少一次再回到定点，使得总权（路程或时间）最小，此即最佳旅行商回路问题。

注：1南山祠，2天涯海角，3大小洞天，4亚龙湾森林公园，5大东海，6三亚湾，7鹿回头，8千古情，9蜈支洲岛，10呀诺达，11珠江南田温泉，12亚马逊丛林水乐园，13三亚奇幻艺术体验馆，14槟榔谷，15凤凰岛，16西岛，17分界洲岛，18猴岛，19鸟巢度假村，20凤凰岭公园

二、Prim算法及路径的求法

（一）算法设计

Prim算法是构造最小生成树的一种常用方法，其基本思想是：设无向连通带权图，其中，是图中的最小生成树，其中是边的集合，当，时，算法结束算法从，，开始，重复执行如下贪心选择：

从，的所有边中选取一条权值最小的边将其加入集合，同时将加入，直到为止，此时，选取到的条边就构成了的一棵最小生成树。

（二）路径求法的提出

在基本Prim算法中，两个城市之间的距离为欧式距离，即

在旅游路线规划的问题中，如果考虑目前景点内的旅游人数，那么距离将是一个向量，即。为了与欧式距离区别，这里用表示，则：

从修改后的距离公式可以看出：当时刻游客要到达的旅游景点内的旅游人数大于其承载量时，这两个旅游景点之间的距离就会增大，反之则减小。结合Prim算法就可以动态地经行旅游路线的规划。

三、算法的实现

本文针对旅游者主要关心的问题——旅游景点的知名度和旅游路线主题等问题，将各景点的知名图设定为一定的权值，并且考虑在各个不同景点停留的时间，将Prim算法加以改进，以此来满足该算法在旅游景点路线选择上的需要，并通过VC++加以实现，最终得到一条三亚市景区的最优旅游线路。Prim算法主要数据结构如下：

#include

#include

#defineMAXV20//最大顶点个数

Typedefstruct

int no；//顶点编号

DataTypeinfo；//顶点其它信息，用于存放顶点其他记录

VertexType；//顶点类型

Typedefstruct//图的定义

intedges[MAXU][MAXU]；//邻接矩阵

intvexnum，arcnum；//顶点弧，弧段数

VertexTypevexs [MAXU]；//存放顶点信息（包括顶点名称，知名度权重）

intmin；//景点停留时间

Mgraph；//图的邻接矩阵类型

把各景点数据代入以上算法，可以得到一个最优旅游线路：

鹿回头凤凰岛三亚湾天涯海角南山祠大小洞天亚马逊丛林水乐园凤凰岭公园千古情三亚奇幻艺术体验馆珠江南田温泉槟榔谷呀诺达亚龙湾森林公园鸟巢度假村大东海蜈支洲岛西岛猴岛分界洲岛。

四、结束语

本文把游客旅行線路的模型，进行了合理的假设，简化了次要因素，把问题转化为图论上最佳旅行商回路问题来解决，使问题得到了比较合理的解决。关于考察者行走线路的模型，考虑到最小时间与均衡时间不可能同时达到，给出时间均衡的条件下的模型和算法，以及初步的结果。因为在建模时考虑的景点数较多，没有区分市内景点和周边地区的景点，也没有考虑旅途休息，有一定的局限性。若作为旅游参考，要根据实际情况来选择使用。

参考文献：

[1]杜玲玲.改进的Prim算法在GIs中的应用[J].测绘信息与工程，2006（1）：28-29.

[2]蒋三庚.旅游规划[M].北京：首都经济贸易大学出版社，2002.

[3]吴凯.旅游线路设计与优化中的运筹学问题[J].旅游科学，2004.

[4]董跃华，李云浩，姜在东.用破圈法实现普里姆算法[J].江西理工大学学报，2008.

[5]刘平原，张霓.普里姆（Prim）算法另解[J].科学中国人，2007.

[6]段智，袁振洲.基于Prim算法的农村公路网布局重要度最大树求解方法[J].公路，2007（5）：111-114.

基金项目：三亚市院地合作项目（NO：2015YD24）。