文档介绍：精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
最优路径规划算法设计
问题概述
兵力机计算中的遗传算法计算哈密尔顿回路问题，即起点与终点重合问题。
图论基本知识
有向图的定义：一个有向图是由一个非空有限集合和中某些元素的有序对集合构成的二元组，记为。其中称为图的顶点集，中的每一个元素，称
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
为该图的一个顶点；称为图的弧集，记为，记有向图
和（c）是无向图，（b）是有向图
邻接矩阵表示法
图的邻接矩阵是如下定义的：是一个的0-1矩阵，即，，也就是说，如果两节点之间有一条弧，则邻接矩阵中对应元素为1，否则为0.
图（a）和图（b）的邻接表矩阵即为
在计算机中用二维数组表示，两节点之间有弧相应的元素为1.
必须指出的是：目前为止，一切最短路算法都只对不含负有向圈的网络有效。实际上，对于含负有向圈的网络，其最短路问题是NP-hard。因此，除非特别说明，一律假定网络不包含负有向圈。此外在实际问题中也会遇到无向网络上的最短路问题，这时原问题一般可以转化为有向网络中上的最短路问题。如果所有弧上的权全为非负数，只需将无向图的一条边代之以两条对称的有向弧即可。如果弧上的权有负有正，一般来说问题要复杂得多，要具体问题具体分析。本文中所要解决的问题都取权值为正，无向图皆采取两条对称的有向弧问题。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
，其中，与关联，称是图的一条道路，为路长，顶点和分别称为的起点和终点，而称为他的内部顶点。
若道路的边互不相同，则称为迹。若道路的顶点互不相同，则称为轨。
称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cycle)。
若图G 的两个顶点u, v间存在道路，则称u和v连通(connected)。u, v间的最短轨的长叫做u, v间的距离。记作d(u,v)。若图G 的任二顶点均连通，则称G 是连通图。
显然有：
(i)图P 是一条轨的充要条件是P 是连通的，且有两个一度的顶点，其余顶点的度为2；
(ii)图C 是一个圈的充要条件是C 是各顶点的度均为2 的连通图
应用
以行军途中各目标为图G 的顶点，两目标之间的连线为图G 相应两顶点间的边，得图G 。对G 的每一边e，赋以一个实数w(e)—两目标之间的距离长度，称为e的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路，它的权叫做间的距离，亦记作。
算法设计
Dijkstra算法
定义预览：
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
展到终点为止。Dijkstra算法是很有代表性的最短路径算法，注意该算法要求图中不存在负权边。
算法描述
算法思想：
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2）算法步骤：
，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。
，把k加入