毕业论文移动版

此算法的基本运算过程如下：

（1）初始化:首先设置进化代数计数器，使，再设置其最大进化代数，并且随机生成了个个体来作为起始的群体。

（2）个体评价：计算这个群体中每个个体的适应度。 　　

（3）选择运算：将选择的运算来作用于群体。这么做的目的就是让优化的个体能够直接遗传到下一代，或者通过配对交叉所产生出的新个体，再来遗传到下一代。这样的操作是在群体中的每个个体的适应度评估基础上的进行的。 　　

（4）交叉运算：将交叉运算作用于群体。这里的交叉是指把两个个体作为父代，并把它们的部分结构进行替换重组产生新个体的操作。交叉运算是遗传算法中的核心运算。 　　

（5）变异运算：将变异运算作用于群体。也就是对群体中的个体串接的某些基因座上的基因值进行改动。 　　

群体经过以上3种运算之后就能过得到下一代群体。 　　

（6）终止条件判断:如果,那么进化过程中所能得到的且具有最大适应度个体就是最优解输出，终止计算。

2。2。3 Dijkstra算法

Dijkstra算法的基本思想：首先设置一个顶点的集合，那么从这个点到集合中的每一个顶点的边权值就已经确定。这样算法进行反复的选择就具有最短路估计的顶点，并将加入中，再对的所有出边来进行松弛操作。

2。2。4 Floyd算法

Floyd算法的基本思想如下：首先任意两个点A和B之间的最短路只有2种可能，一种是直接由A到B，另一种是由A经过若干个点之后再到B，因此，我们只要假设dist(AB)是点A，B之间的最短路的距离，那么对于每一个点K，我们只需要检查dist(AK) + dist(KB) 是否小于 dist(AB)，如果小于，那么就证明了从A到K再到B这样的的路径要比A直接到B的路径短，所以我们可以设 dist(AB) = dist(AK) + dist(KB)，这样一来，当我们讨论完所有的点K，dist(AB)中所记录的就是A到B的最短路的距离。

以上四种算法是最常见的几种算法，当然还有更多的的算法，这里不在一一介绍。如前文所属，在这些算法中，其中公认的最经典的算法就是Dijkstra算法和Floyd算法，我们也将对这两种算法进行具体的介绍。在介绍之前，我们先介绍下时间复杂度 ，时间复杂度是比较算法优劣的一个重要因素。

定义2。2。4。1：算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

我们在计算算法的时间复杂度时，首先要知道算法的基本操作，然后根据操作的步骤来确定它的执行次数，再找出同数的量级（它同数的量级有以下：1，，， ，，，，），找出后，的值也就是该数量级，若对进行求极限能够得到一个常数，那么该时间复杂度。文献综述

  2。3 两种经典算法

在上个世纪六十年代之前对最短路算法的研究已经有所成效，在1959年荷兰著名图论专家E。W。Dijkstra首次提出了对赋权图的有效算法，这种算法不仅解决了两点间的最短路,同时还可以求图中的一个特定点到其它各点的最短路。当然在我们现实生活中，所遇到的大部分问题并都不含负权，因此我们在的情况下选择Dijkstra算法。

Dijkstra算法是非常经典的，其主要特点就是利用起始点为中心向外进行扩展运算，直到扩展到了终点。Dijkstra算法将网路结点分成3部分：未标记、临时标和永久标记三种结点。网路中所有的点首先起始点为未标记结点，连通搜索过程中的以及最短路径中的结点记作临时标记结点。每次循环下来都是从临时标记结点中选取所距初始点路径长度最短的结点来作为永久标记结点，一直至找到目标结点时结束算法。 (责任编辑：qin)