Matlab最优化理论中的最短路问题 (4)
时间:2017-06-16 16:50 来源:毕业论文 作者:毕业论文 点击:次
已知图 ,其中 ，且 为 的邻接矩阵，则 中的 行 列元素 是图 中从 到 且长度为的 链的数目。 1.2.3 权矩阵 定义：赋权图 ，其边 有权 。构造矩阵 ，其中： 称矩阵A为图G的权矩阵。 例4 写出下面所示图的权矩阵。 解：上图的权矩阵为 2 最短路问题算法 2.1 最短路问题 最优化技术研究对象是从众多方案中选择一个最优的方案。对这些方案，首先确定一个衡量方案优劣的标准，然后采取某种手段寻找该标准下的最好方案。解决最优化问题的方法称为最优化方法。网络分析是最优化技术中的一种重要的理论方法，而最短路问题是网络理论中最典型的问题之一。许多优化问题可以使用网络理论中的最短路问题模型，如设备更新、管道铺设、线路安排、厂区布局等等。我们知道最短路问题可以用动态规划来解决，但某些最短路问题（如道路不能整齐分段者）构造动态规划方程比较困难，而图论方法则比较有效。 2.1.1 最短路问题的描述 最短路问题的一般提法如下：设 为连通图，图中各边 有权 （ = 表示 间无边）， ， 为途中任意两点，求一条道路 ， 使它是从 到 的所有路中总权最小的路。即： 最小。有些最短路问题也可以是求网络中某指定点到其余所有结点的最短路，或求网络中任意两点间的最短路。 最短路问题中常见的几类问题： （1） 两指定点间的最短路问题； （2） 从某指定点到其他所有点之间的最短路问题； （3） 任意两点对之间的最短路径问题； 2.1.2 算法的概述与比较 在给定的某一赋权网络中，求始点到其它各点的最短路径算法通常分为两类：第一类是用于求解赋权网络中不存在负数边权，目前比较通用的是Dijkstra算法；第二类是用于求解赋权网络中存在负数边权，这类算法目前比较通用的是Floyd算法。 Dijkstra算法可用于计算两结点之间或一个结点到所有结点之间的最短路径。Dijkstra算法可以应用于简单有向图和混合图。在标号过程中，若给定的网络是有向图和混合图，则所谓相邻必须是箭头指向的结点。对于无向图，Dijkstra算法可以求得所有结点间的最短路径， 另外，无向图的始点到所有点的最短路是一个生成树。 Floyd算法可以解决有负权值边的最短路问题，Floyd算法也可以求出某一指定点到其他各结点的最短路径，但它一般被用来求解任意两点间的最短路径。 下面两节将详细的介绍最短路问题的算法及其步骤。 2.2 Dijkstra算法 Dijkstra算法是由Dijkstra于1959年提出，可用于求解指定两点 间的最短路，或从指定点 到其余各点的最短路，目前被认为是求无负权网络最短路问题的最好方法。 2.2.1 Dijkstra算法的步骤 Dijkstra算法的基本思路的原理为： 若序列 是从 到 的最短路，则序列{ }必为从 到 的最短路。 Dijkstra算法的步骤： Dijkstra算法采用标号法。可用两种标号，T标号与P标号，T标号为探测性标号，P标号为永久性标号，给 点一个P标号时，表示从 到 点的最短路权， 点的标号不再改变。给 点一个T标号时，表示从 到 点的估计最短路权的上界，是一种临时标号，凡没有得到P标号的点都有T标号。算法每一步都把某一点的T标号改为P标号，当终点 得到P标号时，全部计算结束。对于有n个顶点的图，最多经n-1步就可以得到从始点到终点的最短路。 (责任编辑：qin) |