《图论论文-Floyd算法的应用》由会员分享，可在线阅读，更多相关《图论论文-Floyd算法的应用（12页珍藏版）》请在金锄头文库上搜索。
1、题 目 Floyd算法在旅游线路制定问题中的应用学 院 姓 名 学 号 2010 年 11 月摘 要随着日益增长的精神文化需求，旅游已经逐渐成为人们假期生活中不可缺少的一部分。但是旅游的高费用和经济条件还有时间的限制也制约着人们的旅行计划。尤其是对于我们这种初到某城市的学生游客，旅行路线的制定就成为了一个重要的问题。如何在有限时间内经济实惠地制定自己的旅行计划需要我们用有效的数学手段来解决。通过对图论这门课程的学习，发现各种最短路径的算法都能够很好的解决实际生活中的问题，例如Dijkstra算法、Floyd算法、Bellman-Ford算法等等。本文主要介绍了Floyd算法的原理，以重庆市周边
2、旅游景点为背景，选取了几个计划之内的旅游景点为假设模型，希望通过Floyd算法获得任意两景点之间的最短路径来制定旅游路线，中间路过的景点也是我们计划之内的。关键词：Floyd算法 最短路径 假设模型 距离估算 最小权重绪 论在18世纪30年代。一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题要求遍历普鲁士的哥尼斯堡七桥中的每一座桥恰好一次后回到出发点。欧拉证明了这是不可能完成的。此后，欧拉发表了著名的论文依据几何位置的解题方法，这是图论领域的第一篇论文，标志着图论的诞生。图论的真正发展始于20世纪五六十年代之间。是一门既古老又年轻的学科，图论极有趣味性，严格来讲它是组合数学的一个重要分支
3、。虽然图论只是研究点和线的学问。但其应用领域十分广阔。不仅局限于数学和计算机学科，还涵盖了社会学、交通管理，电信领域等等。总的来说，图论这门学科具有以下特点：图论蕴含了丰富的思想，漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化，非常灵活，常常是一种问题一种解法。由以上三个特点可以看出。图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的理论体系和解决问题的系统方法。而且图论所研究的内容非常广泛，例如图的连通性、遍历性。图的计数。图的着色、图的极值问题。图的可平面性等等。最短路问题是图论应用的基本问题，很多实际问题，如线路的
4、布设、运输安排、运输网络最小费用等问题，都可以通过建立最短路问题模型来求解。最短路问题一般是在加权图中讨论，最短路径不仅仅是指一般意义上的距离最短，诸如时间、费用都可以被引申为最短路径，相应的最短路径问题就成了最快路径问题、最低费用问题等。1 背景介绍重庆是中华人民共和国四个直辖市之一，地处中国西南。是中国重要的中心城市之一，历史悠久，国务院公布的第二批国家历史文化名城之一。因为重庆的地理环境，重庆多山多雾，故又有雾都、山城的别名。重庆也是旅游胜地，周边大大小小的旅游景点数不胜数。例如大足石刻、钓鱼城、丰都、小田溪巴王墓群、金佛山、歌乐山等等。对于我们这些初到重庆的学生游客来说，由于对当地理环
5、境并不熟悉，而且时间有限。我们希望在有限的十一或是五一假期内，找到最短的最经济的旅游线路，进行一次重庆周边旅行。所以，如何制定旅游线路就是一个很重要的问题。通过对图论这门课程的学习，我们知道最短路径也是图论中的一个重要的应用问题。其中涉及到的各种算法在日常生活中得到了广泛的应用。Floyd算法就是任意两点间最短路径的经典算法。2 Floyd算法描述2.1 最短路径问题在图G中的每一条边，可赋以一个实数，称为的权，G连同它边上的权称为赋权图，赋权图经常出现在图论的应用中。例如在友谊图中，权可以表示友谊深度；在通信图中，权可以表示各种通讯线路的建造或维修费用。若H是赋权图的一个子图，则H的权是指它
6、的各边的权和。许多最优化问题相当于要在一个赋权图中找出某类具有最小（或最大）权的子图，其中之一就是最短路问题：就是要在一个赋权图的两个指定顶点和之间找出一条具有最小权的路。最短路作为图与网络技术研究中的一个经典问题一直在工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用。顶点对之间的最短路径是指：对于给定的有向网，要对G中任意一对顶点有序对，找出V到W的最短距离和W到V的最短距离。目前，关于最短路问题的研究已有较多结果，传统的最短路算法主要有Floyd算法和Dijkstra算法等。其中，Dijkstra算法求解任意顶点对之间最短距离的方法是：轮流以每一个顶点为源点，重复执行算法n
7、次，即可求得每一对顶点之间的最短路径，总的时间复杂度为，Floyd提出了另外一个求图中任意两顶点之间最短路径的算法，虽然其时间复杂度也是，但其算法的形式更简单，易于理解和编程。2.2 Floyd算法描述对于图G，如果表示i和j之间的可实现的距离，那么表示端i和j之间的最短距离当且仅当对于任意的i, j, k，有。该算法用矩阵形式来表示，并进行系统化的计算，通过迭代来消除不满足上述定理的情况，对于n个端，一给定边长的图，顺序计算各个的W阵和R阵，前者代表径长，后者代表转接路由。其步骤如下：置 其中 和 其中 ：已得和阵，求和阵中的元素如下 ：，重复；，终止。由上述步骤可见，是计算经转接时是否能缩
8、短经常，如有缩短，更改并在R阵中记下转接的端。最后算得和，就得到了最短径长和转接路由。3 Floyd算法用于解决旅行线路问题3.1 旅行线路模型假设初到重庆邮电大学，同学们对重庆这个历史悠久且极具特色的中国中心城市充满了好奇，在节假日的时候都计划着去重庆市周边的旅游景点进行短期旅行。由于我们对重庆市的地理环境消费水平等并不是特别了解，制定旅行线路就成为了一个很重要的问题，由于假期时间有限，我们希望能够在备选目的地景点中，能够找到任何两个景点之间的最短路，且中途经过的节点也是备选景点中的景点。于是选择重庆周边的各个景点为对象如图3-1所示，我们可以选择图示的任何几个景点来生成一个考察对象图，图中
9、粗线条所连接生成的图为文章中考察的图，命名为G。图3-1 重庆市周边旅游景点图图中选择的备选景点分别为：大足石刻、钓鱼城、丰都、小田溪巴王墓群、金佛山、歌乐山、重庆市中心。这七个景点依次编号为1-7，且如图所示粗线表示连接端点的边分别命名为-。于是我们生成了考察对象图G，如图3-2所示。通过考察各个景点之间的实际距离（公里数），-的公里数分别为：78.6km，293.2km，175.6km，176.1km，129.2km，17.9km，79.8km，236.9km，124.7km，20.2km。我们以最短距离20.2为基准作归一化处理得到近似-的值分别为：4，14，9，9，6，1，4，12，6
10、，1。假设模型中，用这些归一化的值分别代表各个边的权值，构成加权图G如图3-2所示。图3-2 由七个景点生成的图G3.2 用Floyd算法计算任意两景点之间的最短路径现在我们以上述生成的图G为考察对象，根据算法流程，设W阵和R阵分别代表径长和转接路由。那么计算结果如下： 经过7轮迭代，我们得到了最终的W和R阵，分别包含了径长信息和路由信息。我们可以从和中找到任何两个端点间的最短径长和最短路由，对应着我们所建立的旅行线路模型中的任何两景点间的最短路径长度和路线。例如我们要找从丰都到大足石刻的最短路径以及路线长度，也就对应着节点到的最短路径和径长，可以从中找到对应的最小值为18，从中找到，就是要经
11、转接；再看，此时已经到达目的节点，所以路由是，对应模型中的景点为丰都经钓鱼城到大足石刻，总公里数为。综上所述，我们可以任选几个备选景点，然后在其中通过该算法来获取最短旅行路线。3.3 Floyd算法的编程实现下面给出了一个Floyd算法的通用程序：Void floyd(graph g,path *p)int i,j,k,n,x,y,z; p-n=n=n=g.n p-d=(int*)malloc(n*n*sizeof(int); p-v=(int*)malloc(n*n*sizeof(int); for(i=0;in;i+) for(j=0;jd+i*n+j)=*(g.a+i*n+j); *(p
12、-v+i*n+j)=j+1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jd+i*n+k);y=*(p-d+k*n+j); z=*(p-d+i*n+j); if(x!=0&y!=0&(z=0|x+yd+i*n+j)x+y; *(p-v+i*n+j)=*(p-v+i*n+k); 四 结论与心得最短路径算法是计算机理论的重难点，可以将最短路径的算法转化为求花费最少和最节省时间等方面的算法，从而对最短路径算法提出一些应用，以达到更多要求，使在交通旅游等方面的成本减到最低，不断拓展Floyd算法的功能。图论这门课是一门应用十分广泛其内容丰富的数学分支，在物理、化学、生物、计算机科学、工程技术和经济管理等各个领域都可以找到图论的足迹。它有极富趣味性，虽然图论只是研究点和线的学问，但其应用领域十分宽广，不仅局限于数学和计算机科学，还涵盖了社会学、交通管理、电信领域等等。总的来说，这门课有以下特点：图论蕴含了丰富的思想、漂亮的图形和巧妙的证明；设计的问题多且广泛，问题外表简单朴素，本质却十分复杂；解决问题的方法千变万化，非常灵活，常常是一种问题一种解法。图论这门课程的学习让我受益匪浅，感谢老师为我们认真的讲解和悉心地指导，对我们思考问题和解决问题的方式方法都起到了很大的帮助，它将渗透到以后工作学习中的每个角落。
