公园的导游图

《用C++语言设计一个公园的导游图》第1页共26页用C++语言设计一个公园的导游图摘要现实生活中，常常会遇到求最短路径的问题。本课程设计旨在提供一种解决这类问题的实例，把某一公园的景点与路线抽象成顶点和边，从而构成图，进而解决一系列相关的最短路径，最佳路线等问题。在课程设计中，系统开发平台为WindowsXP，程序设计设计语言采用C++，程序运行平台为Windows98/2000/XP。对于求解最短路径，使用了著名的Dijkstra算法。对于求最佳路径，采用了常用于解决TSP问题的贪心法。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，这一导游图系统将同样适用于其他公园。关键词程序设计；数据结构；图；最短路径；Dijkstra算法；TSP问题《用C++语言设计一个公园的导游图》第2页共26页1引言现实生活中，常常会遇到求最短路径的问题，本课程设计将把这类问题实例化，把一个公园的景点顶点化、路径边化，建成一个图，再通过比较对图中各边及顶点的关系，实现对公园各个景点进行访问，并能根据要求，求出任意两个顶点的最短路径，还能给出一条依次不重复访问各点的最短路径。【这部分应写明前人相关的研究成果、理论与实践依据，内容可包括研究的目的、意义、主要方法、范围和背景等。】随着计算机科学的迅速发展，计算机已深入到揉社会的各个领域，它的应用已不再局限于科学计算，以解决一些数学问题，而且可以解决一些抽象化的具体问题，更多地用于控制，管理及数据处理等非数值计算的处理工作，这便为我们的日常生活提供了很多的方便，譬如说火车售票系统，学生成绩管理，车厢调度等实际问题。如今程序设计的语言很多，有发展比较完善高级语言，也有最基本的低级语言，然而再好的程序设计也要有一个比较清晰的思路——算法。为了编写好一个好程序，必须分析待处理对象的特性以及各处理对象之间的关系，于是数据结构便成为我们绝佳的选择。数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。《用C++语言设计一个公园的导游图》第3页共26页2程序的功能需求分析2.1程序的功能分析一个公园的导游图，至少应该有一个简单的景点分布图，让游客能对公园概况一目了然。其次，应该能提供相关的景点信息：包括景点名称，景点简介等。以上功能是基础，在此基础上，使公园的导游图系统更具人性化，更具有实用性：为导游图系统添加景点最短路径的计算，提供依次不重复访问所有景点的最佳旅游路线。2.2菜单项及其基本操作拥有了完整的功能的导游图系统，还需要有清爽，简易的操作界面，让游客一目了然，操作方便。本导游图用数字键的选择方式，加以提示，提供给用户如图2.1的简单方便的操作。图2.1抽象化的公园导游图至此，已经规划好导游图系统的功能和操作的基本构架，下一步就是着手为每一个操作的实现做程序实现的考虑了。《用C++语言设计一个公园的导游图》第4页共26页3程序的算法分析要完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。为此，可把系统分为以下几个核心：图的初始化、图的遍历、求两点间的最短路径、求最佳路线。3.1图的初始化图是一种复杂的数据结构，表现在不仅各个顶点的度可以相差很多，而且顶点之间的逻辑关系——邻接关系也错综复杂[1]。从图的定义可知，一个图包括两部分信息：顶点的信息以及描述顶点之间关系（边或弧）的信息。图的初始化是所有相关操作的基础，其存储结构将直接影响到程序的实现的难易度、空间性能和时间性能，因此选择适合本次程序的存储结构至关重要。图的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等多种，较常用的有邻接矩阵和邻接表，而这两者的存储方式的比较如表3-1。表3-1邻接矩阵与邻接表存储结构的比较存储方式空间性能比较时间性能比较唯一性比较邻接矩阵O(n2)O(n2)唯一邻接表O(n+e)O(n+e)非唯一图的邻接矩阵和邻接表存储各有利弊，应用时要根据图的稠密和稀疏程度以及问题的需求进行选择[2]。仔细比较这两种存储方式容易知道，由于邻接矩阵特殊的存储方式，如图2.2所示，它非常便于快速的查找两个顶点之间的边上的权值。所以，图采用带权的邻接矩阵存储。Vertex[5]=V0V1V2V3V4∞∞957∞∞34∞Arc[5][5]=93∞72547∞∞7∞2∞∞图3.1无向图及其邻接矩阵存储示意图V2V1V4V3V04375792《用C++语言设计一个公园的导游图》第5页共26页决定了图的存储方式后，需要有一个公园的实例，本程序选择本人所在地的姑婆山国家森林公园的游览地图作为蓝本，把公园地图抽象化成顶点与边构成的图形式，如图3.2，途中红色数字代表线的权值。图3.2抽象化的公园导游图3.2图的遍历图的遍历是图中最基本的操作。图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。导游图需要把每条路径的信息都向游客展示，就需要读取每两个顶点间的路径信息。由于采用了带权的邻接矩阵存储结构进行存储，所以需要针对这一存储结构对路线进行遍历操作。其遍历算法如图3.3所示，执行效果如图3.4所示。150346725132432413223《用C++语言设计一个公园的导游图》第6页共26页图3.3图的遍历算法流程图图3.4图的遍历算法执行效果示意图3.3最短路径（Dijkstra算法）基于本程序中图的存储是邻接矩阵结构存储的图结构，因而采用适合该存储结构的Dijkstra算法用于解决求最短路径的问题。V2V1V4V3V04375792选择图片控件For循环语句（i=0；i顶点数；i++）NFor循环语句(j=0;ji;j++)YYNY开始结束如果路径存在输出该路径信息N第一次循环第二次循环第三次循环第四次循环《用C++语言设计一个公园的导游图》第7页共26页迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的持续产生最短路径的算法，其基本思想是：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对于vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v，…，vk，就将vk加入集合S中，并将路径v，…，vk，vi，与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。如图3.5所示。图3.5图的遍历算法执行效果示意图辅助数组dist[n]：元素dist[i]表示当前找到的从源点到终点vi的最短路径的长度。初态为:若从v到vi有弧，则dist[i]为弧上的权值；否则置dist[i]为∞。若当前求得的终点为vk,则根据下式进行迭代：dist[i]=min{dist[i],dist[k]+arc[k][i]}1≦i≦n辅助数组path[n]:元素path[i]是一个串，表示当前所找到的从源点到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为“vvk”，否则置path[i]为空串。数组s[n]：存放源点和已经生成的终点（即集合S），初态为只有一个源点v。算法的伪代码描述是：1.初始化数组dist、path和s；2.while（s中的元素个数n）2.1在dist[n]中求最小值，其下标为k（则vk为正在生成的终点）；2.2输出dist[j]和path[j]；2.3修改数组dist和path;2.4将顶点vk添加到数组s中；3.4最佳访问路线（贪心法）在解决最佳访问路线问题时，不得不提到TSP问题。所谓的TSP问题就是指旅行集合S集合V-SVVkVi《用C++语言设计一个公园的导游图》第8页共26页家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短，最后返回到出发点。该这个又称货郎担问题、邮递员问题，是图问题中最广为人知的问题。对于TSP问题，一种最容易想到，也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅游路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为O（n！），当n大到一定程度后是不可解的[3]。在这里就引出解决此问题的一个经典算法：贪心法。贪心法（Greedyalgorithm，直译：贪心算法）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法[4]。因此贪心法非常适合程序的最佳旅游路径的求解。贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。对于大部分的问题，贪心法通常(但不一定)都不能找出最佳解,因为他们一般没有测试所有可能的解。贪心法容易过早做决定,因而没法达到最佳解。然而，贪心法的好处在于容易设计和很多时能达到好的近似解[5]。本程序的最佳路线问题的解决办法，就采用这种求近似最优解的算法。贪心法算法用伪代码描述如下：1.任意选择某个顶点v作为出发点；2.执行下述过程，直到所有点都被访问：v=最后一个被访问的顶点；在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j；访问顶点j；3.从最后一个访问的顶点回到出发点v；以图3.2为导游图系统实例代入后，最佳路线的算法按照如图3.6所示的方式进行图的顶点遍历。《用C++语言设计一个公园的导游图》第9页共26页图3.6实际最佳路径及路径长度150346725132432413223最佳路径长度：1+5+2+3+2+1+3+2=19最佳路径：(0)-(1)-(5)-(7)-(3)-(6)-(4)-(2)-(0)《用C++语言设计一个公园的导游图》第10页共26页4程序的运行与测试4.1程序运行初始界面程序运行，后台对图结构进行初始化，运行结果如图4.1。图4.1最短路径算法正确输出实现4.2查看公园地图公园地图的查看，输出用cout语句建立的公园地图。图4.2公园地图4.3查看路程信息遍历图的所有路径并依次输出路径信息。《用C++语言设计一个公园的导游图》第11页共26页图4.3所有边的信息4.4求最短路径根据用户要求，求始点到终点的最短路径信息和所有路径信息。如图4.4和4.5所示。图4.4两景点间的最短路径图4.5始发点到所有景点的最短路径4.4求最佳路径为游客提供一条可以依次不重复地游览所有景点并最终回到起点的最短路径。《用C++语言设计一个公园的导游图》第12页共26页4.5退出用break实现程序退出。《用C++语言设计一个公园的导游图》第13页共26页5存在的不足与对策由于设计者水平有限，本导游图系统的功能还比较简单，还有一些好的设想没有实现：比如添加管理模式，使得公园管理人员能够同样方便的更改导游图，因此更改这一导游图还必须在程序员的帮助下进行。另外，本导游图系统还有一定的局限性，如果存在只有一条通路的景点，导游图将无法求得最佳旅游路径。公园的导游图系统的这些不足请老师多多谅解。今后我会更多的学习数据结构的相关知识，更深刻地理解图的基本操作，不断提升认识，提高编程技巧，借以不断地提高程序设计水平。《用C++语言设计一个公园的导游图》第14页共26页参考文献[1]朱战立.数据结构——使用C++语言.西安：西安电子科技大学出版社，2001[2]王红梅，胡明，王涛.数据结构(C++版).北京：清华大学出版社，2005[3]马春江，李慧勇，孟繁军.新编数据结构教程.北京：中国电力出版社，2006[4]贪心法_维基百科.维基百科，：2008-9-04[5]田鲁怀.数据结构.北京：电子工业出版社，2006《用C++语言设计一个公园