最小生成树在旅游路线选择中的应用.doc

《最小生成树在旅游路线选择中的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、.编号：审定成绩：邮电大学研究生堂下考试答卷2013-2014学年第1学期论文题目：最小生成树在旅游路线选择中的应用学院名称：学生姓名：专业：学号：指导教师：邮电大学教务处制word范文.摘要随着生活节奏的加快，人民生活水平的提高，人们越来越热衷于四处旅游，同时，大家也不愿意将大部分的时间花费在路途上，人们旅游目的在于放松、赏景、游玩，旅游公司就不得不根据游客要求做出相应的旅游路线安排。很多旅游景点之间都相隔一定的距离，那么如何在众多旅游景点路线中选择最近的一条呢？因此，如何做到即保证游览各个景点又确保路途最近地从众多可行路线中选出最优路线成为了解决此问题的关

2、键。图论最小生成树理论常用于交通线路选择中，本文将其运用于旅游交通优化与线路组织上，即在赋权图中找出一颗最优树，以满足以最短路径最小连接各旅游目的城市和最小的建设成本。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim算法、Kruskal算法和破圈法。本文涉及的抽象图形结构较为简单，使用各类算法的差别在此并无明显体现，一般来说，Kruskal算法应用较为普遍，因此本文采用Kruskal算法实现最优路径求取。文过一个例子应用，将最小生成树的Kruskal算法实际化，通过算法步骤分析，以及在VC++6.0中程序的运行，最终求出的最小生成树与实际相符，该算法

3、思想成立，并具有一般性，能够增删节点、修改权值，也可运用到其他问题的解决中。关键词：旅游路线问题Kruskal算法最优路线最小生成树word范文.一、引言旅游交通是为旅游者由客源地到旅游目的地的往返，以及在旅游目的地各处旅游活动而提供的交通设施及服务，其便利程度，是衡量旅游业发达程度的重要标志。与一般交通不同，旅游交通过程本身也是旅游体验过程，对于游客来说，立足于最小的时间与经济成本获得最多的旅游体验，对于旅游组织者来说，则立足于最小的建设成本与最大的社会、经济、生态效益。道路是交通的载体，具有高度通达性、完善的旅游服务功能和景观化、生态化、人性化的道路是区域

4、旅游交通完善的重要标志，基于此，有学者提出“风景道”、“旅游交通干道”等规划建设理念与原则。其中，旅游交通系统的优化很大程度取决于合理的道路布局，而如何使道路通达性与建设成本之间获得平衡，达到性价比最优，成为道路系统优化的重要指标。因此，其实质上可以简化为最短距离连接各旅游目的地最优解问题[1]。旅游路线组织是旅游地理学研究的重要容，其研究主要以游客的行为空间模式为导向，旅游路线是旅游产品的组成部分，作为产品就必须满足游客的需求，因此游客的行为模式就成为旅游路线设计的重要依据。二、背景知识1、图和树图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形

5、通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。树是无圈连通无向图，如果树T的节点数为n，那么树的边数为n-1。2、生成树连通图G上的一个子图，该子图连通，无回路且包含图G的所有节点，称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。3、最小生成树对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因此这些生成树的各边权值之和也不一定相同，其中权值最小的生成树被称为该带权连通图的最小生成树[4]。三、最小生成树的求解方法构造最小生成树可以有多种算法。我们所学《图论及其算法

6、》教材中介绍了其中的三种算法Prim算法、Kruskal算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。word范文.1、Prim算法算法思想：普里姆算法通过逐个往生成树上添加顶点来构造连通网的最小生成树。算法具体步骤：（1）开始：选取连通网中的任意一个顶点添加到最小生成树中。（2）重复执行以下操作：Ø连通网的顶点集合分成两个部分：已经添加到最小生成树中的顶点集合和尚未添加到最小生成树中的顶点集合；Ø找出所有连通这两个集合中顶点的边；Ø从中选取一条权值最小的边添加到生成树中，同时将与这条边相连的顶点也添加到生成树中。（3）结束：所有的顶点都被添加到最

7、小生成树中。2、Kruskal算法算法思想：通过逐个往生成树上添加边来构造连通网的最小生成树。算法具体步骤：（1）将连通网中的所有顶点添加到最小生成树中，构造一个森林；（2）将各边按照权值从小到大排序；（3）按照排好的顺序向生成树中添加不使森林中产生回路的边(若构成回路则不添加，继续考察下一条边)。直至该森林变成一棵树为止。3、破圈法算法思想：通过逐个从连通网中删除边来构造最小生成树。算法具体步骤：（1）将连通网中各边按照权值从大到小排序；（2）按照排好的顺序从连通网中删除权值最大的边，条件是使删除该边后的子图仍然保持连通(若删除后子图不连通则改边保留，继续删

8、除下一条边)。直至子图中任何一条边都不