公园的导游图.doc

用C+语言设计一个公园的导游图 第26页 共26页 用C+语言设计一个公园的导游图摘 要 现实生活中，常常会遇到求最短路径的问题。本课程设计旨在提供一种解决这类问题的实例，把某一公园的景点与路线抽象成顶点和边，从而构成图，进而解决一系列相关的最短路径，最佳路线等问题。在课程设计中，系统开发平台为Windows XP，程序设计设计语言采用C+，程序运行平台为Windows 98/2000/XP。对于求解最短路径，使用了著名的Dijkstra算法。对于求最佳路径，采用了常用于解决TSP问题的贪心法。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，这一导游图系统将同样适用于其他公园。关键词 程序设计；数据结构；图；最短路径；Dijkstra算法；TSP问题1 引 言现实生活中，常常会遇到求最短路径的问题，本课程设计将把这类问题实例化，把一个公园的景点顶点化、路径边化，建成一个图，再通过比较对图中各边及顶点的关系，实现对公园各个景点进行访问，并能根据要求，求出任意两个顶点的最短路径，还能给出一条依次不重复访问各点的最短路径。【这部分应写明前人相关的研究成果、理论与实践依据，内容可包括研究的目的、意义、主要方法、范围和背景等。】随着计算机科学的迅速发展，计算机已深入到揉社会的各个领域，它的应用已不再局限于科学计算，以解决一些数学问题，而且可以解决一些抽象化的具体问题，更多地用于控制，管理及数据处理等非数值计算的处理工作，这便为我们的日常生活提供了很多的方便，譬如说火车售票系统，学生成绩管理，车厢调度等实际问题。如今程序设计的语言很多，有发展比较完善高级语言，也有最基本的低级语言，然而再好的程序设计也要有一个比较清晰的思路算法。为了编写好一个好程序，必须分析待处理对象的特性以及各处理对象之间的关系，于是数据结构便成为我们绝佳的选择。数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。2程序的功能需求分析2. 1 程序的功能分析一个公园的导游图，至少应该有一个简单的景点分布图，让游客能对公园概况一目了然。其次，应该能提供相关的景点信息：包括景点名称，景点简介等。以上功能是基础，在此基础上，使公园的导游图系统更具人性化，更具有实用性：为导游图系统添加景点最短路径的计算，提供依次不重复访问所有景点的最佳旅游路线。2.2 菜单项及其基本操作拥有了完整的功能的导游图系统，还需要有清爽，简易的操作界面，让游客一目了然，操作方便。本导游图用数字键的选择方式，加以提示，提供给用户如图2.1的简单方便的操作。图2.1 抽象化的公园导游图至此，已经规划好导游图系统的功能和操作的基本构架，下一步就是着手为每一个操作的实现做程序实现的考虑了。3 程序的算法分析要完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。为此，可把系统分为以下几个核心：图的初始化、图的遍历、求两点间的最短路径、求最佳路线。3.1 图的初始化图是一种复杂的数据结构，表现在不仅各个顶点的度可以相差很多，而且顶点之间的逻辑关系邻接关系也错综复杂1。从图的定义可知，一个图包括两部分信息：顶点的信息以及描述顶点之间关系（边或弧）的信息。图的初始化是所有相关操作的基础，其存储结构将直接影响到程序的实现的难易度、空间性能和时间性能，因此选择适合本次程序的存储结构至关重要。图的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等多种，较常用的有邻接矩阵和邻接表，而这两者的存储方式的比较如表3-1。表3-1 邻接矩阵与邻接表存储结构的比较存储方式空间性能比较时间性能比较唯一性比较邻接矩阵O(n2)O(n2)唯一邻接表O(n+e)O(n+e)非唯一图的邻接矩阵和邻接表存储各有利弊，应用时要根据图的稠密和稀疏程度以及问题的需求进行选择2。仔细比较这两种存储方式容易知道，由于邻接矩阵特殊的存储方式，如图2.2所示，它非常便于快速的查找两个顶点之间的边上的权值。所以，图采用带权的邻接矩阵存储。V2V1V4V3V04375792Vertex5 =V0V1V2V3V495734Arc55=937254772图3.1 无向图及其邻接矩阵存储示意图决定了图的存储方式后，需要有一个公园的实例，本程序选择本人所在地的姑婆山国家森林公园的游览地图作为蓝本，把公园地图抽象化成顶点与边构成的图形式，如图3.2，途中红色数字代表线的权值。150346725132432413223图3.2 抽象化的公园导游图3.2 图的遍历图的遍历是图中最基本的操作。图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。导游图需要把每条路径的信息都向游客展示，就需要读取每两个顶点间的路径信息。由于采用了带权的邻接矩阵存储结构进行存储，所以需要针对这一存储结构对路线进行遍历操作。其遍历算法如图3.3所示，执行效果如图3.4所示。选择图片控件For循环语句（i=0；i顶点数；i+）NFor循环语句(j=0;ji;j+)YYNY开始结束如果路径存在输出该路径信息N图3.3 图的遍历算法流程图第一次循环第二次循环第三次循环第四次循环V2V1V4V3V04375792 图3.4 图的遍历算法执行效果示意图3.3 最短路径（Dijkstra算法）基于本程序中图的存储是邻接矩阵结构存储的图结构，因而采用适合该存储结构的Dijkstra算法用于解决求最短路径的问题。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的持续产生最短路径的算法，其基本思想是：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对于viV-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v，vk，就将vk加入集合S中，并将路径v，vk，vi，与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。如图3.5所示。集合S集合V-SVVkVi图3.5 图的遍历算法执行效果示意图辅助数组distn：元素disti表示当前找到的从源点到终点vi的最短路径的长度。初态为:若从v到vi有弧，则disti为弧上的权值；否则置disti为。若当前求得的终点为vk,则根据下式进行迭代：disti=mindisti,distk+arcki 1in辅助数组pathn:元素pathi是一个串，表示当前所找到的从源点到终点vi的最短路径。初态为：若从v到vi有弧，则pathi为“vvk”，否则置pathi为空串。数组sn：存放源点和已经生成的终点（即集合S），初态为只有一个源点v。算法的伪代码描述是：1.初始化数组dist、path和s；2.while（s中的元素个数n）2.1 在distn中求最小值，其下标为k（则vk为正在生成的终点）；2.2 输出distj和pathj；2.3 修改数组dist和path;2.4 将顶点vk添加到数组s中；3.4 最佳访问路线（贪心法）在解决最佳访问路线问题时，不得不提到TSP问题。所谓的TSP问题就是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短，最后返回到出发点。该这个又称货郎担问题、邮递员问题，是图问题中最广为人知的问题。对于TSP问题，一种最容易想到，也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅游路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为O（n！），当n大到一定程度后是不可解的3。在这里就引出解决此问题的一个经典算法：贪心法。贪心法（ Greedy algorithm ，直译：贪心算法） 是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法4。因此贪心法非常适合程序的最佳旅游路径的求解。贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。对于大部分的问题，贪心法通常(但不一定)都不能找出最佳解, 因为他们一般没有测试所有可能的解。贪心法容易过早做决定, 因而没法达到最佳解。然而，贪心法的好处在于容易设计和很多时能达到好的近似解5。本程序的最佳路线问题的解决办法，就采用这种求近似最优解的算法。贪心法算法用伪代码描述如下：1.任意选择某个顶点v作为出发点；2.执行下述过程，直到所有点都被访问：v= 最后一个被访问的顶点； 在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j； 访问顶点j；3.从最后一个访问的顶点回到出发点v；以图3.2为导游图系统实例代入后，最佳路线的算法按照如图3.6所示的方式进行图的顶点遍历。150346725132432413223最佳路径长度：1+5+2+3+2+1+3+2=19最佳路径：(0)-(1)-(5)-(7)-(3)-(6)-(4)-(2)-(0)图3.6 实际最佳路径及路径长度4程序的运行与测试4.1程序运行初始界面程序运行，后台对图结构进行初始化，运行结果如图4.1。图4.1 最短路径算法正确输出实现4.2查看公园地图公园地图的查看，输出用cout语句建立的公园地图。图4.2 公园地图4.3查看路程信息遍历图的所有路径并依次输出路径信息。图4.3 所有边的信息4.4 求最短路径根据用户要求，求始点到终点的最短路径信息和所有路径信息。如图4.4和4.5所示。图4.4 两景点间的最短路径图4.5 始发点到所有景点的最短路径4.4 求最佳路径为游客提供一条可以依次不重复地游览所有景点并最终回到起点的最短路径。4.5 退出用break实现程序退出。5 存在的不足与对策由于设计者水平有限，本导游图系统的功能还比较简单，还有一些好的设想没有实现：比如添加管理模式，使得公园管理人员能够同样方便的更改导游图，因此更改这一导游图还必须在程序员的帮助下进行。另外，本导游图系统还有一定的局限性，如果存在只有一条通路的景点，导游图将无法求得最佳旅游路径。公园的导游图系统的这些不足请老师多多谅解。今后我会更多的学习数据结构的相关知识，更深刻地理解图的基本操作，不断提升认识，提高编程技巧，借以不断地提高程序设计水平。参考文献1 朱战立. 数据结构使用C+语言. 西安：西安电子科技大学出版社，20012王红梅，胡明，王涛. 数据结构(C+版). 北京：清华大学出版社，20053马春江，李慧勇，孟繁军. 新编数据结构教程. 北京：中国电力出版社，20064贪心法_维基百科. 维基百科，/wiki/%E8%B4%AA%E5%BF%83%E6%B3%95：2008-9-045田鲁怀. 数据结构. 北京：电子工业出版社，2006附录 A 用C+语言设计一个公园的导游图/ 程序名称：ParkGuide.h/ 程序功能：程序的变量及函数声明#ifndef PARKGUIDE_H /定义头文件#define PARKGUIDE_H #include /引入标准库中的头文件using namespace std; const int MaxSize=12; /图中最多顶点个数template class ParkGuidepublic: ParkGuide(int* a, T* v,int n); /构造函数，初始化具有n个顶点的图 ParkGuide( ) /析构函数 void Dijkstra( int v,int endv);/最小距离 void PutOutArcInfo(); /输出路径void TSP(int v); /求最优路径private: T vertexMaxSize; /存放图中顶点的数组 int arcMaxSizeMaxSize; /存放图中边的数组 int vertexNum; /图的顶点数和边数 ;#endif/ 程序名称：ParkGuideMain.cpp/ 程序功能：程序的#include #include /引入标准库中的头文件#include ParkGuide.cpp /引用 ParkGuide.cpp 文件#include TSP.cpp /引用解决最佳旅游路线的TSP文件using namespace std;int main(int argc, char* argv) const int numv = 8; /顶点数int control=1; /控制 int which; /功能选择变量string name; /插入顶点的值int bordernumvnumv= /按邻接矩阵确定顶点的权值10000,1,2,2,10000,10000,10000,10000, /0号景点1,10000,10000,10000,10000,5,10000,10000,/1号景点2,10000,10000,3,3,10000,4,10000, /2号景点2,10000,3,10000,10000,3,2,3, /3号景点10000,10000,3,10000,10000,10000,1,10000,/4号景点10000,5,10000,3,10000,10000,5,2, /5号景点10000,10000,4,2,1,5,10000,4, /6号景点10000,10000,10000,3,10000,2,4,10000 /7号景点; string vnamenumv=公园正门,牛头寨,梅园山庄,方家茶园,情人林,猕猴园,仙姑瀑布,仙姑庙; /初始化各顶点 int* p; /定义指针pstring* q; /定义指针qp = &border00; /p指针指向cost数组的起始位置q = vname; /q指针指向vname数组ParkGuide g(p, q, numv ); /调用Graph程序 while ( control=1 ) /控制cout * endl;cout *欢迎您到姑婆山国家森林公园* endl;cout*endl;cout*请选择你想要进行的操作： *endl;cout*1、查看公园地图*endl;cout*2、查看路程信息*endl;cout*3、提供游览景点的最短路径*endl;cout*4、提供游览公园的一种最佳路径*endl;cout*5、退出*endl;cout* which; switch( which ) /功能选择 case 1: /输出图的各顶点的值cout 公园地图 endl;cout 仙姑庙 endl;cout . . . endl;cout . . . endl;cout 仙姑瀑布 . 猕猴园 endl;cout . . . . . . endl;cout . . . . . . endl;cout 情人林 . . . . . endl;cout . . 方家茶园 . endl;cout . . . . . endl;cout . . . . endl;cout 梅园山庄 . 牛头寨 endl;cout . . . endl;cout . . . endl;cout 正 门 endl; break; case 2: /输出图中的路径 int i; int j; cout所有的边的信息为:n; try g.PutOutArcInfo(); catch(char*) cout输出不正确！endl; break; case 3: /求最短路径 cout请输入您所在景点序号:vv; cout请输入您想到的景点序号，若要全部显示请输入9:vvt; try g.Dijkstra(vv,vvt); catch(char*) cout输出顶点不正确！endl; break; case 4: cout本公园为您提供的最佳旅游路线是：n; g.TSP(0); /求最优旅游路线 break; case 5: /退出 control=0; coutendl; cout谢谢使用,祝您旅途愉快!endl; coutendl; break; default:cout对不起，输入错误，请重新输入!endlendlendl; return 0;/ 程序名称：ParkGuide.cpp/ 程序功能：完成游戏的初始化、对鼠标响应及判断游戏是否完成功能#include#include /引入标准库中的头文件#include ParkGuide.h /引入头文件using namespace std;/* 前置条件：图不存在 输入：无 功能：图的初始化 输出：无 后置条件：构造一个有值的图*/template ParkGuide:ParkGuide(int* a,T* v, int n ) /构造图 int i,j; vertexNum=n; /顶点数 for (i=0; iMaxSize; i+) /初始化邻接矩阵 for (j=0; jMaxSize; j+) /定义边 arcij = 10000; for ( i=0; ivertexNum; i+) vertexi=vi; /存储顶点信息 for (i=0; ivertexNum; i+) /给边赋置 for (j=0; jvertexNum; j+) arcij=*(a+i*n+j); int tt=0; /* 前置条件：图已存在 输入：无 功能：输出图中所有的路径 输出：图中所有顶点的数据信息 后置条件：图保持不变*/template void ParkGuide:PutOutArcInfo() /输出图中所有的路径 int i=0; /假设源点是第0个顶点，即顶点序号是0 int j=0;if ( ivertexNum| jvertexNum) throw 位置; /错误抛出异常 else for(i=0;ivertexNum;i+) /输出任意两点之间的路径 for(j=0;ji;j+) if(arcij10000) /两点之间存在路径 cout从 vertexi 到 vertexj 的路程为：arcij公里n; /若两点间有路，则输出该两点间的路径 /* 前置条件：图已存在 输入：顶点v ，endv 功能：假如endv存在，求v到endv的最短路径；假如不输入endv，则求v到任意顶点的最短路径 输出：所求得的最短路径及所经历的位置 后置条件：图保持不变*/template void ParkGuide:Dijkstra(int v,int endv) /求从v顶点到endv点的最短路径 if ( vvertexNum) throw 位置; /v顶点或endv顶点输出不正确则抛出异常 int numv=vertexNum; /顶点数 int distMaxSize; /最短长度 int pathMaxSize; /当前找到的最短路径 int sMaxSize; /存放源点和已生成的终点的集合 int max= 10000; /代表无穷大 int i,j,k,wm; for(i=0;inumv;i+) /按网的邻接矩阵确定各顶点最短路径的初值 disti=arcvi; if(i!=v& disti max) /如果v、i之间有路 pathi=v; /当前找到的最短路径为v else pathi=-1; /否则v与i顶点不存在路径 si = 0; /给s集合确定初值0 sv=1;distv=0; /将顶点v本身排除在外 for(k =0;knumv-1;k+) /求其他numv-1各顶点的最短路径 wm = max;j=v; /确定当前最短路径wm及顶点的序号j for( i=0;inumv;i+) if(!si&distiwm) /如果v、i之间有路 j=i;wm = disti; /把当前找到的路径确定为最大值 sj=1; for(i =0;inumv;i+) /更新未确定最短路径各顶点的当前最短路径 if(!si&distj+arcjidisti) /如果v、i两点的距离加上i、j小于从v点到j点的距离 disti=distj+arcji;pathi=j; /disti取最小值 if (endv =0 ) /endv点存在 string mmm=; /初始化字符串 int j =endv; while(j -1 ) string nnn = vertexj; /依次把顶点存放在nnn字符串中 nnn+=mmm; mmm = +nnn; j = pathj; cout从 vertexv.c_str() 到 vertexendv.c_str() 的最短路程为：distendv公里 途经：mmm.c_str()n;/输出从v点到endv点的最短路径 else /endv点不存在for(i=0;i -1 ) string nnn = vertexj; /依次把顶点存放在nnn字符串中 nnn+=mmm; mmm = +nnn; j = pathj; cout从 vertexv.c_str() 到 vertexi.c_str() 的最短路程为：disti公里 途经：mmm.c_str()n;/输出从v点到任意点的最短路径 / 程序名称：TSP.cpp/ 程序功能：解决导游图的TSP问题：求不重复地访问每一个并回到起点的最短路径#include#include /引入标准库中的头文件#include ParkGuid