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

编号：审定成绩：重庆邮电大学研究生堂下考试答卷2013-2014学年第1学期论文题目：最小生成树在旅游路线选择中的应用学院名称：学生姓名：专业：学号：指导教师：重庆邮电大学教务处制摘要随着生活节奏的加快，人民生活水平的提高，人们越来越热衷于四处旅游，同时，大家也不愿意将大部分的时间花费在路途上，人们旅游目的在于放松、赏景、游玩，旅游公司就不得不根据游客要求做出相应的旅游路线安排。很多旅游景点之间都相隔一定的距离，那么如何在众多旅游景点路线中选择最近的一条呢？因此，如何做到即保证游览各个景点又确保路途最近地从众多可行路线中选出最优路线成为了解决此问题的关键。图论最小生成树理论常用于交通线路选择中，本文将其运用于旅游交通优化与线路组织上，即在赋权图中找出一颗最优树，以满足以最短路径最小连接各旅游目的城市和最小的建设成本。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim算法、Kruskal算法和破圈法。本文涉及的抽象图形结构较为简单，使用各类算法的差别在此并无明显体现，一般来说，Kruskal算法应用较为普遍，因此本文采用Kruskal算法实现最优路径求取。文中通过一个例子应用，将最小生成树的Kruskal算法实际化，通过算法步骤分析，以及在VC++6.0中程序的运行，最终求出的最小生成树与实际相符，该算法思想成立，并具有一般性，能够增删节点、修改权值，也可运用到其他问题的解决中。关键词：旅游路线问题Kruskal算法最优路线最小生成树一、引言旅游交通是为旅游者由客源地到旅游目的地的往返，以及在旅游目的地各处旅游活动而提供的交通设施及服务，其便利程度，是衡量旅游业发达程度的重要标志。与一般交通不同，旅游交通过程本身也是旅游体验过程，对于游客来说，立足于最小的时间与经济成本获得最多的旅游体验，对于旅游组织者来说，则立足于最小的建设成本与最大的社会、经济、生态效益。道路是交通的载体，具有高度通达性、完善的旅游服务功能和景观化、生态化、人性化的道路是区域旅游交通完善的重要标志，基于此，有学者提出“风景道”、“旅游交通干道”等规划建设理念与原则。其中，旅游交通系统的优化很大程度取决于合理的道路布局，而如何使道路通达性与建设成本之间获得平衡，达到性价比最优，成为道路系统优化的重要指标。因此，其实质上可以简化为最短距离连接各旅游目的地最优解问题[1]。旅游路线组织是旅游地理学研究的重要内容，其研究主要以游客的行为空间模式为导向，旅游路线是旅游产品的组成部分，作为产品就必须满足游客的需求，因此游客的行为模式就成为旅游路线设计的重要依据。二、背景知识1、图和树图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。树是无圈连通无向图，如果树T的节点数为n，那么树的边数为n-1。2、生成树连通图G上的一个子图，该子图连通，无回路且包含图G的所有节点，称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。3、最小生成树对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因此这些生成树的各边权值之和也不一定相同，其中权值最小的生成树被称为该带权连通图的最小生成树[4]。三、最小生成树的求解方法构造最小生成树可以有多种算法。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim算法、Kruskal算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。1、Prim算法算法思想：普里姆算法通过逐个往生成树上添加顶点来构造连通网的最小生成树。算法具体步骤：（1）开始：选取连通网中的任意一个顶点添加到最小生成树中。（2）重复执行以下操作：连通网的顶点集合分成两个部分：已经添加到最小生成树中的顶点集合和尚未添加到最小生成树中的顶点集合；找出所有连通这两个集合中顶点的边；从中选取一条权值最小的边添加到生成树中，同时将与这条边相连的顶点也添加到生成树中。（3）结束：所有的顶点都被添加到最小生成树中。2、Kruskal算法算法思想：通过逐个往生成树上添加边来构造连通网的最小生成树。算法具体步骤：（1）将连通网中的所有顶点添加到最小生成树中，构造一个森林；（2）将各边按照权值从小到大排序；（3）按照排好的顺序向生成树中添加不使森林中产生回路的边(若构成回路则不添加，继续考察下一条边)。直至该森林变成一棵树为止。3、破圈法算法思想：通过逐个从连通网中删除边来构造最小生成树。算法具体步骤：（1）将连通网中各边按照权值从大到小排序；（2）按照排好的顺序从连通网中删除权值最大的边，条件是使删除该边后的子图仍然保持连通(若删除后子图不连通则改边保留，继续删除下一条边)。直至子图中任何一条边都不能删除（即删除任意一条边都会造成该子图不连通）为止。4、三种算法的比较（1）普里姆算法：主要是对顶点进行操作；采用邻接矩阵作为存储结构，在行过程中对连通网中的每一个顶点都考察到了。普里姆算法适用于求边稠密的连通网的最小生成树。（2）克鲁斯卡尔算法：主要是对边进行操作，时间复杂度主要取决于对边按照权值进行排序的时间，边的个数为e，排序的时间复杂度可以做到O(eloge)，因此算法的时间复杂度为O(eloge)。克鲁斯卡尔算法适用于求边稀疏的连通网的最小生成树。（3）破圈法：主要是对边进行操作，时间复杂度主要取决于对边按照权值进行排序的时间，边的个数为e，排序的时间复杂度可以做到O(eloge)，因此算法的时间复杂度为O(eloge)。该算法适用于求边稀疏的连通网的最小生成树[5]。四、应用利用最小生成树来解决旅游路线问题，将旅游路线问题中的旅游景点看做图中的顶点，各个景点之间的路线看做图中顶点之间的边，景点之间路线的长度看做图中各边上的权值。这样，我们就把旅游路线问题转换成了求一个有向连通网的最小生成树问题。此时，假设景点个数为6，分别为v1,v2,v3,v4,v5,v6。并设其对应景点之间的路线距离权值及初始状态的连通加权无向图如下图所示。边(1,2）(1,3）(1,4）(2,3)(2,6)(3,4)(3,5)(3,6)(4,5)(5,6)权值6197356426v1v2v4v3v5v66957126436以下是用Kruskal算法求解最小生成树（1）实现步骤：根据前文介绍的Kruskal算法步骤依次添加边（1,3）,（4,5）,（2,6）,（3,6）,（3,4），并依次添加对应节点，各个步骤结果如下图：v1v31v1v4v3v512第一步第二步v1v2v4v3v5v6123v1v2v4v3v5v61243第三步第四步v1v2v4v3v5v651243第五步（2）仿真及结果分析在vc++6.0环境下，首先输入图的顶点数和边数，然后输入第一条边的起始点和终点，以及这条边的权值，直到输完为止自动将权从小到大排序，并且得出最小生成树，如下图运行结果所示。五、总结本文首先将实际的旅游路线选择问题转化成了图论的最小生成树问题，然后选用Kruskal算法编写相应的C语言程序最终实现。这样一方面可以得到一条最有效的路线，使得路途观赏性和时间效率都得到提高，另一方面还可以增加景点（顶点数），改变边的权值（景点之间的距离）等等，具有灵活、准确、简便等特点，由于它的一般性，不仅仅解决了旅游路线选择的问题，同时还适用于其他问题的解决。参考文献[1]鲍捷.基于最小生成树Kruskal算法的皖北地区旅游交通优化与线路组织[J].人文地理.2010,03.[2]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2003，11.[3]谭浩强.C程序设计（第三版）[M].北京：清华大学出版社，2005.[4]殷剑宏，吴开亚.图论及其算法[M].北京：中国科学技术大学出版社，2006[5]李晓莉，王发曾，罗军.中原城市群轨道交通干线选择研究[J].2008,10附录Kruskal算法程序：#includestdio.h#includestdlib.h#defineM20#defineMAX20typedefstruct//构造边{intbegin;intend;intweight;//权值}edge;typedefstruct{intadj;intweight;}AdjMatrix[MAX][MAX];typedefstruct{AdjMatrixarc;intvexnum,arcnum;//顶点数和边数}MGraph;voidCreatGraph(MGraph*);//函数申明构造图voidsort(edge*,MGraph*);//函数申明对边的排序voidMiniSpanTree(MGraph*);//最小生成树intFind(int*,int);voidSwapn(edge*,int,int);//交换两条边的权值和它们的起点和终点voidCreatGraph(MGraph*G)//构件图G{inti,j,n,m;printf(请输入图的顶点数和边数:);scanf(%d%d,&G-vexnum,&G-arcnum);for(i=1;i=G-vexnum;i++)//初始化图{for(j=1;j=G-vexnum;j++){G-arc[i][j].adj=G-arc[j][i].adj=0;}}for(i=1;i=G-arcnum;i++)//输入边和权值{printf(\n请输入边的起始点和终点:);scanf(%d%d,&n,&m);while(n0||nG-vexnum||m0||mG-vexnum){printf(\n);printf(\n);printf(输入的数字不符合要求请重新输入:);scanf(%d%d,&n,&m);}G-arc[n][m].adj=G-arc[m][n].adj=1;getchar();printf(\n请输入%d与%d之间的权值:,n,m);scanf(%d,&G-arc[n][m].weight);//输入权值}}voidsort(edgeedges[],MGraph*G)//对权值进行排序{inti,j;for(i=1;iG-arcnum;i++){for(j=i+1;j=G-arcnum;j++){if(edges[i].weightedges[j].weight){Swapn(edges,i,j);}}}printf(\n);printf(\n);printf(\n);printf(权从小到大排序之后为:\n);printf(◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n);printf(起点终点权\n);for(i=1;i=G-arcnum;i++){printf(%d%d%d\n,edges[i].begin,edges[i].end,edges[i].weight);}}voidSwapn(edge*edges,inti,intj)//交换权值以及头和尾{inttemp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].weight;edges[i].weight=edges[j].weight;edges[j].weight=temp;}voidMiniSpanTree(MGraph*G)//生成最小生成树{inti,j,n,m;intk=1;intparent[M];edgeedges[M];for(i=1;iG-vexnum;i++){for(j=i+1;j=G-vexnum;j++){if(G-arc[i][j].adj==1){edges[k].begin=i;edges[k].end=j;edges[k].weight=G-arc[i][j].weigh