算法课程设计-校园导航问题

算法设计与分析课程设计题目： 校园导航问题 文档： 物联网工程学院物联网工程专业学号 学生姓名 班级 二O—三年十二月校园导航问题一、问题描述与分析课程设计主要内容及要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）.首先，根据江南大学的主要场所设计江南大学的学校平面图如下所示：图1:江南大学主要场所平面图之后，需要进行算法的选择与分析，显然，这是一个主要涉及贪婪算法的问题，简单的描述就是计算求解一个节点到其他所有节点的最短路径的问题，通过查阅算法设计与分析的相关资料，最终选择了狄斯奎诺算法来设计解决这个问题。二、设计概要贪婪法的设计思想：在实际生活中，经常有这样一类问题：它有n个输入，它的解由这n个输入中的一个子集组成，但这个子集必须满足事先给定的某些条件。有时，把这些条件称为约朿条件，把满足约束条件的解称为问题的可行解。满足约束条件的解可能不止一个，因此可行解也不是唯一的。为了衡量可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，把这些函数称为目标函数。使目标函数取极值（极大或极小）的可行解，称为最优解。贪婪法通常用来解决具有最大值或最小值的优化问题。它犹如登山一样，一步一步地向前推进，从某一个初始状态出发，根据当前局部的而不是全局的最优决策，以满足约束方程为条件、以使得目标函数的值增加最快或最慢为准则，选择一个能够最快地达到要求的输入元素，以便尽快地构成问题的可行解。在一般情况下，贪婪法由一个迭代的循环组成，在每一轮循环中,通过少量的局部的计算，试图去寻求一个局部的最优解，而不考虑将来如何。因此，它是一步一步得建立问题的解的。每一步的工作都增加了部分解的规模，每一步的选择都极大地增长了它所希望实现的目标函数。因为每一步都是由少量的工作基于少量的信息组成的，因此所产生的算法特别有效。适合于用贪婪法求解的问题，一般具有下面两个重要性质，即贪婪选择性质和最优子结构性质。所谓贪婪选择性质，是指所求问题的全局最优解，可以通过一系列局部最优的选择来达到。每进行一次选择，就得到一个局部的解，并把所求解的问题简化为一个规模更小的类似子问题。所谓最优子结构，是指一个问题的最优解中包含其子问题的最优解。基于贪心算法的最短路径算法（狄斯奎诺算法）具体如下：最短路径算法关键先把已知最短路径顶点集（只有一个源点）和未知的顶点分开，然后依次把未知集合的顶点按照最短路径加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。算法把一个图（G）中的点划分成了若干部分：（1）：原点（v）（2）:所有周边点（C）另外有一个辅助集合S,从v到S中的点的最短路径已经求得。S的最初状态是空集。这样就可以进一步划分图（G）：（1）：原点（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为空集。系统功能框图设计如下：图2：系统功能框图相关函数及函数名称的设计:1、 邻接矩阵创建函数：CreateMGraphO2、 校园平面图展示函数：Map()3、 资料介绍函数：Info()4、 求最短路径函数:DijkstraO5、 主菜单函数：Menu()6、 输出结果函数：Display07、 主函数：main()各函数之间的调用关系设计如下:图3:函数调用关系图三、流程图及主要源程序主程序流程图如下所示:开始定义整型变量V0和VI定义字符型变量e和ckV J * 调用CreateMGraph()函数生成邻接矩阳图4：主程序流程图1、节点数据类型的描述与定义顶点信息的结构体定义:tvpedefstmctVertexTvpe{intnumber; 〃顶点数字char*sight; 〃顶点向量JVertexType;邻接矩阵的结构体定义:tvpedefstmct{VeitexTypevex[NUM];〃顶点序号intaics[NUM][NUM]; 〃邻接矩阵intvexiium; 〃图的当前顶点数}MGraph;2、节点图函数的描述代码voidCreateMGrapli(mt¥)//建立节点图的函数{intij;Gvexiium=v;for(i=1;i<Gvexnum;++i)G.vex[i].number=i;Gvex[O].sight="江南大学主要场所的名字";Gvex[1].sight=”北大门"；Gvex[2].sight=M二食堂”；Gvex[3].siglit=M男生宿舍园区”;Gvex[4].siglit="教职工公寓";Gvex[5].sight=M一食堂"；Gvex[6].siglit=H第一教学楼”;Gvex[7].siglit=M女生宿舍园区”;Gvex[8].siglit=,'公益图书馆”;Gvex[9].siglit="东大门";Gvex[10].sight=“食品学院”；Gvex[ll].sight=-第二教学楼“；Gvex[12].sight=n三食堂";Gvex[13].sight=H四食堂蔦Gvex[14].sight=”南大门”；foi(i=1;i<Gvexnum;++i){for(j=lj<Gvexiium;+4j)G.arcs[i][j]=Max:}Garcs[l][3]=Garcs[3][l]=580;Garcs[l][4]=Garcs[4][l]=620;G.arcs[l][5]=Garcs[5][l]=750:Garcs[l][8]=Garcs[8][l]=1260;Garcs[2][习=Garcs[3][2]=490;Garcs[2][习=Garcs[5][2]=620;G.arcs[2][7]=Garcs[7][2]=230:Garcs[3][4]=Garcs[4][3]=650;Garcs[3][5]=Garcs[5][3]=180;Garcs[3][8]=Garcs[8][3]=1330;Garcs[4][习=Garcs[5][4]=750;Garcs[4][6]=Garcs[6][4]=430;Garcs[4][8]=Garcs[8][4]=1290;Garcs[4][9]=Garcs[9][4]=1340;Garcs[5][8]=Garcs[8][5]=690;Garcs[6][8]=Garcs[8][6]=110;G.arcs[6][刃=Garcs[刃[6]=150;Garcs[7][10]=Garcs[10][7]=760;G.arcs[7][14]=Garcs[14][7]=1820;Garcs[8][9]=Garcs[9][8]=680;Garcs[8][11]=G.arcs[11][8]=190;Garcs[8][12]=Garcs[12][8]=810;Garcs[8][13]=Garcs[13][8]=1240;Garcs[8][14]=Garcs[14][8]=1100;Garcs[9][11]=G.arcs[11][刃=440;Garcs[9][13]=Garcs[13][9]=980;Garcs[9][14]=Garcs[14][9]=1480;Garcs[10][12]=Qarcs[12][10]=320;G.arcs[10][14]=G.arcs[14][10]=1560;Garcs[ll][12]=Garcs[12][ll]=880;G.arcs[ll][13]=Garcs[13][U]=410;Garcs[ll][14]=Garcs[14][ll]=820;Garcs[12][13]=Qarcs[13][12]=610;Garcs[12][14]=Qarcs[14][12]=390;Garcs[13][14]=G.arcs[14][13]=510;3、求最短路径的算法函数代码voidDijkstra(mtnum)//狄斯奎诺算法最短路径mtv,w,i,t;intfiiialfNUM]:intmill；fbr(v=l;v<NUM;v++)ifinal[v]=0;D[v]=G.arcs[num][v];foi(w=1;w<NUM;w++)P[v][w]=0;if(D[v]<Max)P[v][num]=l;P[v][v]=l;}D[num]=0;fiiial[num]=l;fbr(i=1;i<NUM;++i)niui=Max;foi(w=1;w<NUM汁+w)if(?fiiial[w])if(D[w]<nmi){v=w;inin=D[w];final[v]=l;fbi(w=1;\v<NUM;++w)if(!final[w]&&((nun+G.arcs[v][w])<D[w])){D[w]=niui+G.arcs[v][w];fbi(t=O;t<NUM;t++)P[w][t]=P[v][t];P[w][w]=l;}}}4、主菜单函数代码charMenu()〃主菜单函数{charc;intflag;do{systeni(MclsH);flag=l;Map();pnntf(M\ii\t\t\ti— 1E)；prmtffWt|1E);prmtffWt|欢迎使用江南人学导航图系统1S”)；prmtf<H\t\t\t|1S”)；prmtffWt|1、查询场所之间最短路径1S”)；prmtffWt|2、江南人学主要场所介绍1S”)；prmtffWt|e、退出系统1S”)；prmtffWt|1S”)；prmtfC-Wt1-」E);prmtf(M\t\t\t\t请输入您的选择：J;scaiif(,,%c,\&c);if(c==T||c=2||c==e)flag=O;}wlule(flag);returnc;}5、 输出最短路径函数代码voidDisplay(iiitsightljntsight2)//输出函数{inta,b,c,d,q=O;a=sight2;if(a!=sightl){从％$到％$的最短路径*\G.vexfsight1].sight.Gvex[sight2].sight);priiitf(n\t(最短距离为%dm.)\n\n\t'\D[a]);piiiitf(n\t%sM,Gvex[sight1].sight);d=sightl;fo【(c=0;c<NUM;++c){P[a][slghtl]=O;fbr(b=O;b<NUM;b++){iflG.aics[d][b]<Max&&P[a][b]){prmtf(H~>%sn,Gvex[b].sight);q=q+l；P[a][b]=O;d=b;if(q%8=0)pnntf(n\iiH);}}}}}6、 主函数代码voidmain()//主函数{intvO,vl；clwe;charck;CieateMGraph(NUM);dosystem("cls");ck=Menu();switch(ck)沁T:gate:system(MclsH);Map();do{请输入出发场地的序号(1〜14)：M);scanf(”％d”,&vO);if(v0<l||v0>14)输入错误!请重新查询!\iT);}whUe(vO<l||vO>14);do{prmtf(H\t\t请输入目的场地的序号(1〜14)：n);scanf(H%dH,&vl);if(vl<l||vl>14i|vl==v0)输入错误!请重新查询!\iT);}\vhile(vl<l||vlA]4||vl=vO);Dijkstia(vO);Displav(vO.vl);按回车键继续，按e退回首页\n”)；getcharQ;scanf(”％c役&e);if(亡==e)break;gotogate;沁2:system(MclsH);Info。；pnntf(”\n\n\t\t\t\t请按回车键返回首页...5”)；getcharQ;getcharQ;break;};}while(ck!=e);}四、程序调试及运行结果在多次调试程序并修改其中的语法错误之后，最终成功运行程序并得到如下几张图所示的运行结果(1)江南大学导航系统运行界面菜单•江I幸I吠:学士也图导尙亢杀纟充匚■3"C:\Window叭&y£tem32\DEbug\3£d.exe"欢迎使用江南大学导航图系统请输入您的选择匕(2)校园导航系统的主要场地的简介>3"C:\Windows\system32\Debug\asd.exe* |(=||@||S丄-北大门. 这里是江南大学的正门2.二負堂，又称梁溪苑，靠近澡堂男生宿舍园区：由桃园、李园等园区组成教职工公寓：握供教职工住宿与生活的场所—食堂： 又称江南苑，靠近男生宿舍园区第一教学楼； 由"BCD四大区域组成，可供自习及數学•人女生宿舍园区， 由桂园、榴园等园区组成1公益图书馆，由茉毅仁捐理，与荣氏家族有看不解之纟彖9.东大门： 东面的大门，有一块上面写着江南大学的大石丄0-食品学院：有着江南大学王牌专业的学院U.第二教学楼：与第一教学楼隔満相对.可供自习与教学12.三食堂； 由苏州大学承包，伙食不错13-四食堂，又称广溪苑，人气较高丄4.南大门， 门上书写看江南大学四字请按回车键返回首页.…（3）校园导航系统求解显示最短距离r^irsin从北大门到三食堂的最短路径是 〈最短距离为1970n.＞北大门一＞教职工公寓一〉第一教学楼一＞公益图书馆一＞三食堂按回车键继续，按e退回苜页14•南大门 12.三L堂一 13r^irsin从北大门到三食堂的最短路径是 〈最短距离为1970n.＞北大门一＞教职工公寓一〉第一教学楼一＞公益图书馆一＞三食堂按回车键继续，按e退回苜页14•南大门 12.三L堂一 13•四食堂9•东太门仮食品年院8•公益图书馆 ——".第二教学楼,•5—食堂・竿生宿舍园早——6•第一•教学楼十卄杠卄卄沖卄卄一^江南大学地图导航系统““詩“祁“石三「北牛门2••二食•堂 3•男生宿舍园区__丄| 4•教职工公寓・■3"C:\Windows\system32\Debug\asd.exe*号号B-.L地地场场岀目入入t请灶冃四、课程设计总结与心得（1）算法总结与心得首先，这次的课程设计的算法主要用到了贪婪算法的主要思想，贪婪算法是算法设计课程中的一个十分重要的规划思想，能够一步一步地来解决问题。狄斯奎诺算法用于求解一个有向图（也可以是无向图）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思十分巧妙，算法本身并不是按照我们的思维习惯一一求解从原