1、 本科生毕业论文本科生毕业论文 题题 目目 地图中最短路径的搜索算法研究 系系 别别 计算机与信息工程 班班 级级 计算机科学与技术 082 姓姓 名名 学学 号号 答辩时间答辩时间 2012 年 5 月 目 录 摘要 1 1 问题分析 2 1.1 技术分析 2 1.2 需求分析 2 2 系统总体框架及算法设计 3 2.1 系统总体框架 3 2.2 算法设计 3 2.2.1 广度优先算法 3 2.2.2 深度优先算法 5 2.2.3 A*算法 6 3 程序运行结果与分析 8 3.1 图中各种算法的运行效果 8 3.1.1 广度优先算法运行结果 8 3.1.2 深度优先算法运行结果 9 3.13
2、 A*算法运行结果 10 3.2 算法的总体比较与分析. 10 4 结论. 12 参考文献. 13 谢辞. 14 1 地图中最短路径的搜索算法研究 摘要：目前为止, 国内外大量专家学者对“最短路径问题”进行了深入的研究。 本文通过理论分析, 结合实际应用， 从各个方面较系统的比较了广度优先搜索算 法(BFS)、深度优先搜索算法(DFS)、A* 算法的优缺点，并描述了算法之间的一 些关系，以及每种算法的适用情况。广度优先搜索算法占内存多但速度较快，深 度优先搜索算法占内存少但速度较慢，A*算法是启发式搜索算法，适合于解决小 规模、大规模以及超大规模的问题。程序通过调试运行，实现了设计的目标。 关
3、键词：关键词：最短路径算法；广度优先算法；深度优先算法；A*算法； The Research of Search Algorithm of Shortest Path in Map Name:Li Xiaokun Tutor:Dong Luan Abstract: So far, a large number of domestic and foreign experts and scholars on the“ shortest path problem“ in-depth study. In this paper, through theoretical analysis and prac
4、tical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic. And describes some relationships between the algorithms,and the application of each algorithm. Breadth-first search algorithm need more memory but fast, depth-first search algorithm need less memory but slow. A * algorithm is a heuristic search algorithm whice suitable f
