算法课程设计校园导航问题.wps资料文档下载

1、所谓贪婪选择性质，是指所求问题的全局最优解，可以通过一系列局部最优的选择来达到。每进行一次选择，就得到一个局部的解，并把所求解的问题简化为一个规模更小的类似子问题。所谓最优子结构，是指一个问题的最优解中包含其子问题的最优解。基于贪心算法的最短路径算法（狄斯奎诺算法）具体如下：最短路径算法关键先把已知最短路径顶点集（只有一个源点）和未知的顶点分开，然后依次把未知集合的顶点按照最短路径加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。算法把一个图（G）中的点划分成了若干部分：（1）：原点（v）（2）：所有周边点（C）另外有一个辅助集合 S，

2、从 v 到 S 中的点的最短路径已经求得。S 的最初状态是空集。这样就可以进一步划分图（G）：原点（v）；（2）：已求出 v 至其最短路径的周边点（S）；（3）：尚未求出 v 至其最短路径的周边点（Other=C-S）；算法的主体思想：A、找到 v-Other 所有路径中的的最短路径 vd=v-d（Other 的 一个元素）；B、找到 v-S-Other 所有路径中的的最短路径 vi=v-i（Other 的一个元素）；C、比较 vd 和 vi 如果 vd=vi 则将 d 加入 S 且从 Other 中删除，否 则将 i 加入 S 且从 Other 中删除。D、重复以上步骤直至 Other 为空

3、集。系统功能框图设计如下：图 2：系统功能框图 相关函数及函数名称的设计:相关函数及函数名称的设计:1、邻接矩阵创建函数：CreateMGraph（）2、校园平面图展示函数：Map（）3、资料介绍函数：Info（）4、求最短路径函数：Dijkstra（）5、主菜单函数：Menu（）6、输出结果函数：Display（）7、主函数：main（）各函数之间的调用关系设计如下：图 3:函数调用关系图三、流程图及主要源程序三、流程图及主要源程序主程序流程图如下所示：主程序流程图如下所示：图 4：主程序流程图1、节点数据类型的描述与定义（1）顶点信息的结构体定义：typedef struct Vertex

4、Typeint number;/顶点数字char*sight;/顶点向量VertexType;（2）邻接矩阵的结构体定义：typedef structVertexType vexNUM;/顶点序号int arcsNUMNUM;/邻接矩阵int vexnum;/图的当前顶点数MGraph;2、节点图函数的描述代码void CreateMGraph（int v）/建立节点图的函数int i,j;G.vexnum=v;for（i=1;iG.vexnum;+i）G.vexi.number=i;G.vex0.sight=江南大学主要场所的名字;G.vex1.sight=北大门;G.vex2.sight=

5、二食堂;G.vex3.sight=男生宿舍园区;G.vex4.sight=教职工公寓;G.vex5.sight=一食堂;G.vex6.sight=第一教学楼;G.vex7.sight=女生宿舍园区;G.vex8.sight=公益图书馆;G.vex9.sight=东大门;G.vex10.sight=食品学院;G.vex11.sight=第二教学楼;G.vex12.sight=三食堂;G.vex13.sight=四食堂;G.vex14.sight=南大门;+i）for（j=1;jG.vexnum;+j）G.arcsij=Max;G.arcs13=G.arcs31=580;G.arcs14=G.ar

6、cs41=620;G.arcs15=G.arcs51=750;G.arcs18=G.arcs81=1260;G.arcs23=G.arcs32=490;G.arcs25=G.arcs52=620;G.arcs27=G.arcs72=230;G.arcs34=G.arcs43=650;G.arcs35=G.arcs53=180;G.arcs38=G.arcs83=1330;G.arcs45=G.arcs54=750;G.arcs46=G.arcs64=430;G.arcs48=G.arcs84=1290;G.arcs49=G.arcs94=1340;G.arcs58=G.arcs85=690;G

7、.arcs68=G.arcs86=110;G.arcs69=G.arcs96=150;G.arcs710=G.arcs107=760;G.arcs714=G.arcs147=1820;G.arcs89=G.arcs98=680;G.arcs811=G.arcs118=190;G.arcs812=G.arcs128=810;G.arcs813=G.arcs138=1240;G.arcs814=G.arcs148=1100;G.arcs911=G.arcs119=440;G.arcs913=G.arcs139=980;G.arcs914=G.arcs149=1480;G.arcs1012=G.ar

8、cs1210=320;G.arcs1014=G.arcs1410=1560;G.arcs1112=G.arcs1211=880;G.arcs1113=G.arcs1311=410;G.arcs1114=G.arcs1411=820;G.arcs1213=G.arcs1312=610;G.arcs1214=G.arcs1412=390;G.arcs1314=G.arcs1413=510;3、求最短路径的算法函数代码void Dijkstra（int num）/狄斯奎诺算法最短路径int v,w,i,t;int finalNUM;int min;for（v=1;vNUM;v+）finalv=0;D

9、v=G.arcsnumv;for（w=1;wNUM;w+）Pvw=0;if（DvMax）Pvnum=1;Pvv=1;Dnum=0;finalnum=1;iNUM;+i）min=Max;+w）if（!finalw）if（Dwmin）v=w;min=Dw;finalv=1;finalw&（min+G.arcsvw）Dw）Dw=min+G.arcsvw;for（t=0;tNUM;t+）Pwt=Pvt;Pww=1;4、主菜单函数代码char Menu（）/主菜单函数char c;int flag;dosystem（cls）;flag=1;Map（）;printf（ntttn）;printf（ttt n

10、）;printf（ttt 欢迎使用江南大学导航图系统 n）;printf（ttt 1、查询场所之间最短路径 n）;printf（ttt 2、江南大学主要场所介绍 n）;printf（ttt e、退出系统 n）;printf（tttn）;printf（tttt 请输入您的选择：）;scanf（%c,&c）;if（c=1|c=2|c=e）flag=0;while（flag）;return c;5、输出最短路径函数代码void Display（int sight1,int sight2）/输出函数int a,b,c,d,q=0;a=sight2;if（a!=sight1）printf（nt 从%s

11、到%s 的最短路径是,G.vexsight1.sight,G.vexsight2.sight）;printf（t（最短距离为%dm.）nnt,Da）;printf（t%s,G.vexsight1.sight）;d=sight1;for（c=0;cNUM;+c）Pasight1=0;for（b=0;bNUM;b+）if（G.arcsdb%s,G.vexb.sight）;q=q+1;Pab=0;d=b;if（q%8=0）printf（n）;6、主函数代码void main（）/主函数int v0,v1;char e;char ck;CreateMGraph（NUM）;ck=Menu（）;switc

12、h（ck）case 1:gate:system（cls）;doprintf（nntt 请输入出发场地的序号（114）：scanf（%d,&v0）;if（v014）printf（nntttt 输入错误!请重新查询!n）;while（v014）;doprintf（tt 请输入目的场地的序号（114）：v1）;if（v114|v1=v0）printf（nntttt 输入错误!while（v114|v1=v0）;Dijkstra（v0）;Display（v0,v1）;printf（nntttt 按回车键继续,按 e 退回首页n）;getchar（）;e）;if（e=e）break;goto gate;

13、case2:Info（）;printf（nntttt 请按回车键返回首页.n）;break;while（ck!=e）;四、程序调试及运行结果四、程序调试及运行结果在多次调试程序并修改其中的语法错误之后，最终成功运行程序并得到如下几张图所示的运行结果（1）江南大学导航系统运行界面菜单（2）校园导航系统的主要场地的简介（3）校园导航系统求解显示最短距离四、课程设计总结与心得四、课程设计总结与心得（1）算法总结与心得首先，这次的课程设计的算法主要用到了贪婪算法的主要思想，贪婪算法是算法设计课程中的一个十分重要的规划思想，能够一步一步地来解决问题。狄斯奎诺算法用于求解一个有向图（也可以是无向图）的一个

14、点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思十分巧妙，算法本身并不是按照我们的思维习惯求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第 n 个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列，然后求出原点到图中其余各点的最短路径。清楚了算法的这种巧妙的构思之后，理解算法本身就不是很困难了。虽然狄斯奎诺算法是一种典型的求最短路径的算法，可用于计算一个节点到其他所有节点的最短路径，其主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。然而迪杰斯特拉算法也有其缺点和局限性，由于它遍历计算的节点很多，所以效率较低，尤其是当需要处理大量

15、的节点时，其计算量会变得十分冗杂导致效率偏低。总之，在选择一个算法时，要具体问题具体分析，根据具体的问题选择合适的算法即可，还要兼顾算法的效率问题。（2）课程设计感想与总结通过这一次的课程设计，我对算法设计与分析这门课有了更加深入的了解与认识，不仅仅提高了自己理论方面的基础知识，还进一步的提高了自己的编程能力和实践操作水平。由于自己对 C 语言比较熟悉，而且专业课程教的也主要是 C 语言，所以我便选择了 C 语言作为此次课程设计的设计语言。经过此次的课程设计，我明白了任何一门计算机语言和课程的学习，都是应该将理论与实际相互结合，光有理论知识是远远不够的。在以前的学习中，我主要以备考为目的，总是注重对教材理论知识的学习，不太注重实践编程与实现，平时较少会去主动写一些代码，从以前的 C 语言学习包括现在的汇编语言的学习都是这样一个情况。虽然在期末考试中往往有不错的成绩，但是真正要我自己动手去编写一个程序时，却总是困难重重，无从下手。所以，要真正的学好一门课，需要理论联系实践，多多动手，多多实践，才能够真正的掌握。