wangyou网络规划.pptxVIP

网络规划;最短路问题 最大流问题 最小费用流问题 ; 最短路问题 最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以便用这个模型．如设备更新、管道铺设、线路安排、厂区布局等。 最短路问题的一般提法： 设G={V，E}为连通图，图中各边(vi,vj)有权lij(lij=∞表示vi,vj间无边)。vs,vt为图中任意两点，求一条路μ，使它是从vs到vt的所有路中总权最小的路。即 ;有些最短路问题是求网络中某指定点到其余所有点的最短路，或求网络中任意两点间的最短路。下面介绍两种算法，可分别用于求解这几种最短路问题。 1、Dijkstra算法 2、Floyd算法（自己上网百度一下）;1、Dijkstra算法 本算法由Dijkstra于1959年提出，可用于求解指定两点vs、vt间的最短路，或从指定点vs到其余各点的最短路。 (1) 基本思路基于以下原理：若序列{vs,v1,…,vn-1,vn}是从vs到 vn的最短路，则序列{vs,v1,…,vn-1}必为从vs到vn-1的最短路 (2)使用条件——网络中所有的弧(边)权均非负，即;Dijkstra算法基本步骤，采用标号法。 可用两种标号：T标号与P标号，T标号为试探性标号，P为永久性标号，给vi点一个P标号时，表示从vs到点vi的最短路权,vi点的标号不再改变。给vi点一个T标号时．表示从vs到点vi的估计最短路权的上界，是一种临时标号．凡没有得到P标号的点都有T标号。算法每一步都把某一点的T标号改为P标号，当终点vt得到P标号时，全部计算结束。对于有n个顶点的图，最多经n一1步就可以得到从始点到终点的最短路。 标号的意义： ①标号P(永久性标号)—从始点到该标号点的最短路权。 ②标号T(临时性标号）—从始点到该标号点的最短路权上界。 ;例、用Dijkstar算法求下图中v1到v7点的最短路。 ;(1) 首先给v1以P标号,P(v1)=0,其余所有点给T标号,T(vi)=+∞;?;(4) v3为刚得到P标号的点，考察边(v3,v4),(v3,v6)的端点v4,v6。 T(v4)=min{T(v4),P(v3)+l34}=min{5,2+2}=4 T(v6)=min{T(v6),P(v3)+l36}=min{∞,2+7}=9;(6) v2,v4为刚得到P标号的点,考察边(v2,v5), ),(v4,v5),(v4,v6)的端点v5,v6。 T(v5)=min{T(v5),P(v4)+l45,P(v2)+l25}=min{∞,4+3,4+4}=7 T(v6)=min{T(v6),P(v4)+l46}=min{9,4+4}=8;(8) v5为刚得到P标号的点，考察边(v5,v6),(v5,v7)的端点v6,v7。 T(v6)=min{T(v6),P(v5)+l56}=min{8,7+1}=8 T(v7)=min{T(v7),P(v5)+l57}=min{∞,7+7}=14;2、最大流问题;截集:把网络D=(V,E,C)的点集V剖分为两个非空集合Vs和Vt(即Vs∩Vt=?，Vs∪Vt=V)，使vs∈Vs, vt∈Vt，把从Vs指向Vt的弧的全体 截量:截集中所有弧的容量之和 最小截集：截量最小 由截集的定义可知：截集是从vs到vt的必经之路，无论去掉哪个截集，从vs到vt就不存在路了，因此任何一个可行流的流量不会超过任何一个截集的容量。因而若能找到一个可行流和一个截集，使得可行流的流量等于这个截集的容量，则该可行流一定是最大流，该截集一定是最小截集。;链：图中有一个点与边的交替序列 μ={vi0,ei1,vi1,ei2,?,vik-1,eik,vik}，则称该交替序列 μ为连结vi0和vik的一条链。 增广链：对于可行流f，?是一条从vs到vt的一条链，如果?+ （全体正向弧）中的弧均为非饱和弧，?-中的弧均为非零流弧，则称?为从vs到vt的关于f 的增广链。;计算网络最大流的方法 增广链的实际意义在于沿着这条链存在增大输送能力的潜力。如沿着增广链?1={vs,v2,v5,v4,v6,vt}，凡是正向弧的流量都增加1，反向弧的流量都减少1（见下图），结果整个网络的流增加了1，即由6增加到7。用这种方法调整后的流仍为可行流。这样就得到了一个寻找最大流的方法：从一个可行流开始，寻找关于这个可行流的增广链，若增广链存在，则可以经过调整，得到一个新的可行流，其流量比调整前的可行流大，重复这个过程，直到不存在增广链时就得到了最大流。;下面介绍计算网络最大流的标号算法 设已有一个可行流f(若网络中没有给出可行流,则可设f为零流)，标号法可分为两步： （一）标号过程 在这个过程中,网络中的点或者是标号点，或者是未标号点。每个标号点的标号包含两个部分：