网路的最大流和最小截.pptx
会计学1网路的最大流和最小截网路的最大流和最小截2 6.4.3 6.4.3 确定网路最大流的标号法确定网路最大流的标号法确定网路最大流的标号法确定网路最大流的标号法n n从任一个初始可行流出发，如 0 流n n基本算法：找一条从 s 到 t 点的增广链(augmenting path)n n若在当前可行流下找不到增广链，则已得到最大流n n增广链中与 s 到 t 方向一致的弧称为前向弧，反之后向弧 增广过程：前向弧增广过程：前向弧 f ij=fij+q q,后向弧后向弧 f ij=fij q q 增广后仍是可行流增广后仍是可行流 第1页/共10页3 最大流最小截的标号法步骤最大流最小截的标号法步骤最大流最小截的标号法步骤最大流最小截的标号法步骤第一步：标号过程，找一条增广链1 1、给源点给源点 s s 标号标号 s s+,q q(s s)=)=，表示从，表示从 s s 点有无限流出潜力点有无限流出潜力2 2、找出与已标号节点找出与已标号节点 i i 相邻的所有未标号节点相邻的所有未标号节点 j j，若，若(1)(1)(i i,j j)是前向弧且饱和，则节点是前向弧且饱和，则节点 j j 不标号；不标号；(2)(2)(i i,j j)是前向弧且未饱和，则节点是前向弧且未饱和，则节点 j j 标号为标号为 i i+,q q(j j)，表示从节点，表示从节点 i i 正正向向流出，可增广流出，可增广 q q(j j)=min=minq q(i i),c cij ij f fij ij ；(3)(3)(j j,i i)是后向弧，若是后向弧，若 f fji ji=0=0，则节点，则节点 j j 不标号；不标号；(4)(4)(j j,i i)是后向弧，若是后向弧，若 f fji ji00，则节点，则节点 j j 标号为标号为 i i,q q(j j)，表示从节点，表示从节点 j j 流流向向 i i，可增广可增广 q q(j j)=min=minq q(i i),f fji ji ；3 3、重复步骤重复步骤 2 2，可能出现两种情况：，可能出现两种情况：(1)(1)节点节点 t t 尚未标号，但无法继续标记，说明网路中已不存在增广链，尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流当前流 v v(f f)就是最大流；所有获标号的节点在就是最大流；所有获标号的节点在 VV 中，未获标号中，未获标号节点在节点在 VV 中，中，V V 与与 VV 间的弧即为最小截集；算法结束间的弧即为最小截集；算法结束(2)(2)节点节点 t t 获得标号，找到一条增广链，由节点获得标号，找到一条增广链，由节点 t t 标号回溯可找出该标号回溯可找出该增广链；到第二步增广链；到第二步第2页/共10页4 最大流最小截的标号法步骤最大流最小截的标号法步骤最大流最小截的标号法步骤最大流最小截的标号法步骤第二步：增广过程1 1、对、对增广链中的前向弧，令增广链中的前向弧，令 f f=f f+q q(t t)，q q(t t)为节点为节点 t t 的标的标记值记值2 2、对对增广链中的后向弧，令增广链中的后向弧，令 f f=f f q q(t t)3 3、非增广链上的所有支路流量保持不变、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步n n以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷n n一次只找一条增广链，增广一次换一张图n n最后一次用广探法，以便找出最小截集第3页/共10页5最大流最小截集的标号法举例最大流最小截集的标号法举例最大流最小截集的标号法举例最大流最小截集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)第4页/共10页6最大流最小截集的标号法举例最大流最小截集的标号法举例最大流最小截集的标号法举例最大流最小截集的标号法举例(s+,)(s+,3)(2,3)最小截集最小截集第5页/共10页7 最大流标号法的复杂度讨论最大流标号法的复杂度讨论最大流标号法的复杂度讨论最大流标号法的复杂度讨论n n找一条增广链的计算量是容易估计的，不会超过找一条增广链的计算量是容易估计的，不会超过O O(n n2 2)n n但是最多迭代多少次但是最多迭代多少次(即增广的次数即增广的次数)就很难估计，在最坏就很难估计，在最坏情况下，与边的容量有关；如上图：先增广情况下，与边的容量有关；如上图：先增广 s s u u v v t t,然后增广然后增广 s s v v u u t t，每次只能增广，每次只能增广 1 1 个单位，故要个单位，故要增广增广40004000次才能结束次才能结束n n克服这种缺点的经验方法：克服这种缺点的经验方法：n n尽量先用段数少的增广链尽量先用段数少的增广链n n尽量不重复前面出现过的增广链尽量不重复前面出现过的增广链第6页/共10页8 6.4.4 多端网路问题多端网路问题多端网路问题多端网路问题第7页/共10页9 6.4.5 6.4.5 最小费用最大流最小费用最大流最小费用最大流最小费用最大流n n双权网路双权网路：每条弧不但有容量，还有单位流量的通过费用：每条弧不但有容量，还有单位流量的通过费用n n两种解法：一种基于最小费用路径算法；一种基于可行弧两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法集的最大流算法n n基于最小费用路径算法基于最小费用路径算法：总是在当前找到的最小费用的路：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧负权值费用的弧n n基于可行弧集的最大流算法基于可行弧集的最大流算法：从：从 0 0 费用弧集开始应用最大费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界流算法，然后根据计算信息提高费用的限界P P，使可行弧集，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主这种算法是一种主-对偶规划的解法。使用这种方法的还有对偶规划的解法。使用这种方法的还有运输问题、匹配问题运输问题、匹配问题第8页/共10页10 6.4.5 6.4.5 以最短路为基础汇总网路上的流以最短路为基础汇总网路上的流以最短路为基础汇总网路上的流以最短路为基础汇总网路上的流n n在电路网中每两点之间都有中继电路群需求，但并不是任在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路两点都有物理传输链路n n根据两点间最短传输路径将该两点间的电路需求量加载到根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设这条传输路径上去：设 a a2525=10=10 是节点是节点2 2 和和 5 5 之间的电路需之间的电路需求，节点求，节点2 2 和和 5 5 之间的最短传输路径为之间的最短传输路径为 2 2 1 1 3 3 5 5，则加，则加载过程为载过程为:T T2121=T T2121+10,+10,T T1313=T T1313+10,+10,T T3535=T T3535+10+10；T Tij ij 是传输是传输链路链路 i i j j 上加载的电路数；当所有点间电路都加载完则算上加载的电路数；当所有点间电路都加载完则算法结束法结束第9页/共10页
