1。2 交通运输网路的最短路算法的优劣讨论的研究意义

    交通运输在日常生活中必不可少的一部分，随着时代的发展交通运输的网路越来越复杂，人们选择的路线也越来越多。然而复杂的网路也带来了许多不便，例如交通堵塞，因此有必要知道其中的最短路算法。通过对交通运输网路中最短路算法的优劣分析，选择最佳方案运输，可以极大的缓解交通压力，节约资源。不仅仅对社会带来便利，也给自己节约了时间和金钱。

1。3 交通运输网路的最短路算法的优劣讨论国内外研究现状与发展

第二章 最短路算法知识

 2。1最短路

  首先，我们给出路的定义。

定义2。1。1：路是图中从一个点到另一个点所经过的线，其中所有的顶点（除了第一个和最后一个）是不同的。一条路线中所有的边是不同的。图中一条长度为的路线是交替序列的顶点和边，，它以顶点开始,以结束，记为。

由路的定义我们可以知道，两个点之间的路不是唯一的，那么这些路中必然存在一条长度最短的路，我们给出最短路的定义。

定义2。1。2：在图中给出一个顶点（称为始点）及顶点（称为终点）。所谓最短路问题就是在道路集合中，寻找长度最小的路，这条路就称为从到的最短路。

最短路问题分为单源最短路问题和多源最短路问题。单源最短路问题指确定了起点或确定了终点求确定的顶点或终点到图中别的点的的最短路问题；多源最短路问题指图中任意两个点之间的最短路问题。

  2。2 最短路算法

    2。2。1 A*算法

A*（A-Star）算法是在静态路网中求解最短路的最有用的方法。公式表示为：

其中是点从起始点到目标点之间的估价函数，而是在状态空间中从起始点到点所需要的实际代价，以及是从到目标点最优路径所需的估计代价。为了保证找到最短路径，最重要的就在于估价函数的选取：

估价值到目标点的实际距离值，在这样的情况下，我们搜索的点数越多，搜索的范围就越大，而效率就越低。但这却能够得到最优解。

而如果估价值>实际值的话，搜索的点数就越少，搜索范围就越小，效率也就越高，但显然这样是不能保证得到最优解的。

因此，只有估价值与实际值越接近，估价函数才能够取得越好。论文网

A*算法的主要过程，是在每一次在选择下一个搜索点的时候，是从全部的已探知的却未搜索过的点中，选取值最小的点来进行展开。同时，所有的这些“已探知的却未搜索过”的点可以通过一个按值升序的队列来排列。如此，在整个搜索的过程中，我们只需要按照类似广度优先的算法框架，来从优先队列中弹出元素（值）作为队首，再对其可能存在的子结点计算、和值，直到优先队列为空或找到终点为止就可以了。

2。2。2 遗传算法

遗传算法（Genetic Algorithm）是一种通过了借鉴生物界的自然进化规律演化而来的随机化搜索方法。这种算法是美国的J。Holland教授在1975年最先提出的，直接的对结构对象来进行操作就是这种算法的特征，并不需要限定求导和函数连续性；这种算法具有内在的隐并行性同时还有更好的整体寻优能力；算法采用的寻优方法是概率化，这样能自动获得并指导优化所需的搜索空间，使其能自适应地去调整搜索的方向，而不需要确定的规则才能进行。遗传算法的这些性质，现在在组合优化、信号处理、机器学习、人工生命和自适应控制等领域早已广泛应用了。它是现代相关智能计算中的所需的关键技术之一。