您现在的位置: 论文网 >> 管理学论文 >> 旅游管理论文 >> 基于Prim算法的旅游线路设计论文

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

出处:论文网
时间:2017-10-10

基于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;//图的邻接矩阵类型

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

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

  四、结束语

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

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

论文搜索
关键字:旅游线路 算法 基于 线路 旅游 设计
最新旅游管理论文
浅析肇庆黎槎古村文化旅游品牌建设策略
鄂西生态旅游市场现状分析
对旅游产业投资基金的分析和优化研究
基于唐代服饰文化的乾陵旅游纪念品参与式创
浅析湖北省旅游景观设计中地域文化的表达
基于旅游发展导向的美丽乡村建设研究
慈溪观海卫镇乡村旅游电子商务基础分析
旅游英语翻译中的文化差异与处理方式
旅游英语课程教学现状及改革探讨
中医药健康旅游产业存在的问题与对策研究
热门旅游管理论文
论生态旅游的可持续发展
深度发掘文化内涵促进旅游产业可持续发展
旅游产品开发存在的问题及改进
关于旅行社业削价竞争的思考
我国导游队伍建设现状及对策分析
我国国内旅游业发展的现状、趋势及对策
对旅游市场营销的探讨
旅游资源的市场策略探析
试论江西乡村旅游的可持续发展
论云南旅游资源优势及其开发对策