毕业论文移动版

最短路径问题是图论研究中的一个长盛不衰的经典问题，它旨在寻找图中指定两结点间的最短路径。国内外大量专家学者都对此问题进行了比较深入的研究。

寻找最短路径就是：给出了一个连接若干个点的网络，在这个网络的两个指定点之间，找一条最短路径。最短路径不仅可以指一般物理意义上的距离最短,还可以引申到其它的度量,比如：费用、时间、线路容量等。最短路径算法的选择问题与实现问题是路线设计的基础问题,最短路径算法则是计算机科学与地理信息科学等领域的研究热点,很多与网络相关的问题都可以纳入最短路径问题的范畴中。

随着经典的图论与不断发展完善的计算机数据结构和算法的有效结合，新的最短路径算法也不断涌现。比较常用的路径规划方法有:Dijkstra算法，蚁群算法，平行最短路径搜索算法，EBSP*算法和基于矩阵负载平衡的启发算法等。它们在时间复杂度、空间复杂度、易实现性以及应用范围等方面各具特色。其中，因为Dijkstra算法可以给出最可靠的最短路径，而且比较容易实现，所以被广泛应用。 86911

因为经典的Dijkstra算法的时间复杂度为，当直接应用到大规模城市路网的时候，它的最短路径查询时间较长，所以专家学者们纷纷开展对Dijkstra算法的优化研究。概括来说，研究者们主要是从5个方面对最短路径算法进行优化：(1)基于数据存储结构的优化，以空间换取时间；(2)基于路网规模控制的优化；(3)基于搜索策略的优化；(4)优先级队列结构的优化；论文网(5)基于双向搜索的并行计算优化。

本文主要介绍了遗传算法，它是基于生物进化原理的一种全局性优化算法。遗传算法采用的是启发性的智能搜索算法，在处理高空间复杂问题上时往往比其他算法有更好的结果。它提供给了我们一种通用的算法框架，这种框架具有很强的适应性，并且在处理特殊问题提供了极大的灵活性。很多算法，比如：资源分配、连通分析、决策支持系统中的决策理论、流分析以及最佳路径分析等有关最优化问题的算法都应用了遗传算法的结构特征。本文选择了图论中最富有代表性的最短路径问题，浅要介绍了遗传算法并着重探讨遗传算法在求解最短路径问题的可行性。