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

三亚市区主要景点分布图和三亚周边地区旅游图,各旅游点之间的路程。每个景点的最佳逗留时间等信息可以登陆三亚旅游官方政务网(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

intno;//顶点编号

DataTypeinfo;//顶点其它信息,用于存放顶点其他记录

VertexType;//顶点类型

Typedefstruct//图的定义

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

intvexnum,arcnum;//顶点弧,弧段数

VertexTypevexs[MAXU];//存放顶点信息(包括顶点名称,知名度权重)

intmin;//景点停留时间

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

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

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

四。结束语

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

Prim算法的旅游线路设计