地图中最短路径的搜索算法研究 毕业论文

《地图中最短路径的搜索算法研究 毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科生毕业论文题目地图中最短路径的搜索算法研究系别计算机与信息工程班级计算机科学与技术082姓名学号答辩时间2012年5月新疆农业大学计算机与信息工程学院目录摘要11问题分析21.1技术分析21.2需求分析22系统总体框架及算法设计32.1系统总体框架32.2算法设计32.2.1广度优先算法32.2.2深度优先算法52.2.3A*算法63程序运行结果与分析83.1图中各种算法的运行效果83.1.1广度优先算法运行结果83.1.2深度优先算法运行结果93.13A*算法运行结果103.2算法的总体比较与

2、分析104结论12参考文献13谢辞14地图中最短路径的搜索算法研究摘要：目前为止,国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析,结合实际应用，从各个方面较系统的比较了广度优先搜索算法(BFS)、深度优先搜索算法(DFS)、A*算法的优缺点，并描述了算法之间的一些关系，以及每种算法的适用情况。广度优先搜索算法占内存多但速度较快，深度优先搜索算法占内存少但速度较慢，A*算法是启发式搜索算法，适合于解决小规模、大规模以及超大规模的问题。程序通过调试运行，实现了设计的目标。关键词：

3、最短路径算法；广度优先算法；深度优先算法；A*算法；TheResearchofSearchAlgorithmofShortestPathinMapAbstract:Sofar,alargenumberofdomesticandforeignexpertsandscholarsonthe"shortestpathproblem"in-depthstudy.Inthispaper,throughtheoreticalanalysisandpracticalapplication,comprisewith

4、thebreadth-firstsearchalgorithm(BFS),depth-firstsearchalgorithm(DFS)andtheA*algorithmsfromanyaspectsofsystematic.Anddescribessomerelationshipsbetweenthealgorithms,andtheapplicationofeachalgorithm.Breadth-firstsearchalgorithmneedmorememorybutfast,depth-

5、firstsearchalgorithmneedlessmemorybutslow.A*algorithmisaheuristicsearchalgorithmwhicesuitableforsmall,bigandlarge-scaleproblems.Runninganddebuggingtheprogrammakethedesignedgoalcometrue.Keywords:Shortestpathalgorithm;Breadth-firstalgorithm;Algorithm;A*a

6、lgorithm;14地图中最短路径的搜索算法很早就广泛的应用于各个领域，最短路径问题也是图论研究中的一个经典问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”[1]。此次毕业设计，是大学生走进社会的最后一次学校学习，也是一次锻炼，本设计基于VC++的基础上，自主构建若干个固定结点，并描述各个结点之间的路径关系，然后用深度优先算法、广度优先算法和A*算法求出图中两个结点的最短路径，并进行全面的分析。1问题分析1.1

7、技术分析C++是一种静态类型，支持多重编程范式的通用程序设计语言[1]。它广泛的支援多种程序设计风格（程序化程序设计、资料抽象化、面向对象程序设计、泛型程序设计）。它是由C语言发展而来的，既可以用于面向过程的结构化程序设计，也可以用于面向对象的程序设计,是一门功能强大的程序设计语言[2]。VisualC++6.0是Microsoft公司在1998年推出的基于Windows9X和WindowsNT一个优秀集成开发环境[3]。该开发环境为用户提供了良好的可视化编程环境，程序员可以利用该开发环境轻松地访问

8、C++源代码编辑器、资源编辑器和使用内部调试器，并且可以创建项目文件。VisualC++6.0不仅包括编译器，而且它还包括许多有用组件，如程序向导AppWizard、类向导ClassWizard等，通过这些组件的协同工作，可以在VisualC++6.0集成开发环境中轻松的完成创建源文件、编辑资源，以及对程序的编译、连接和调试等各项工作[4]。1.2需求分析本系统是基于VC++，自主创建一张地图，可以随机建图，也可以手动创建顶点，并附加权值，之后将相关信息储存在数组中，