- 1、本文档共65页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
6.5 最高标号预流推进算法 - 清华大学
STEP0. (预处理) 置初始可行流x为零流; 计算精确的距离函数d;令当前节点i=s. STEP1. 若d(s) n, 继续下一步; 否则结束, 得到最优解x. STEP2. 如果存在节点i的某条出弧(i,j)为允许弧, 则转STEP3; 否则转STEP4. STEP3. 令pred(j)=i, 再令i=j; 若i=t,则找到了一条增广路, 增广并修改残量网络, 再令i=s. 转STEP1. STEP4. 修改标号(重新标号): 当{(i,j)?A(x) | uij(x) 0} ??时令d(i)=min{d(j)+1|(i,j)?A(x)且uij(x) 0}, 否则令d(i)=n; 且当i ? s时再令i=pred(i) . 转STEP1. “前进步” “回退步” 6.3.2 最短增广路算法 6.3.2 最短增广路算法 – 性质 引理6.4 在最短增广路算法中,距离标号始终保持是有效的. 归纳法: 在预处理阶段,构造的距离标号是有效的.只需证明一次增广操作和一次重新标号操作不改变距离标号的有效性. 增广操作可能引起残量网络的弧的变化只有两种情况: 允许路上的弧(i,j)可能退出残量网络:这不会影响(i,j)弧的端点上的距离标号的有效性; (j,i)弧可能进入残量网络:由于(i,j)弧是允许弧, 因此d(i)=d(j)+1,所以d(j)=d(i)-1 d(i), 这也不会影响(j,i)弧的端点上的距离标号的有效性. 重新标号将d(i)改为d’(i)=min{d(j)+1|(i,j)?A(x)且uij(x) 0}: 不会破坏任意的(i,j)弧的端点上的距离标号的有效性 ; 重新标号时节点i在残量网络中没有允许弧, 即对于任意的(i,j)?N(x)满足d(i) d(j)+1. 因此 d’(i) d(i), 即标号严格增加. 对于任意的(j,i)弧, d(j) ? d(i)+1 d’(i)+1,仍有效 6.3.2 最短增广路算法 – 性质 推论: 由于距离函数是有效的,算法结束时残量网络N(x)中从节点s到节点t没有允许路,即残量网络中不存在增广路,所以算法确实求到了最大流 例6.5 用最短增广路算法计算如下网络图6.5(a)中的最大流(s=1,t=4,弧上数字表示容量). 1 2 3 4 1 2 3 4 5 1 2 3 4 1 2 3 4 5 1 1 2 0 1 2 3 4 1 2 3 4 1 1 2 3 4 1 2 4 1 4 0 1 1 2 1 1 2 3 4 1 1 3 4 1 4 1 0 1 2 1 2 3 4 1 2 1 4 5 1 2 3 4 1 2 1 4 5 2 0 1 2 3 1 2 3 4 1 2 1 4 5 1 2 3 4 1 2 1 4 5 2 0 1 2 4 最短增广路算法 – 首先思考:如何从一个节点出发找到从该节点出发的一条允许弧? 数据结构:即对每个节点i,算法用链表A(i)记录该节点出发的所有弧,这些弧的顺序可以任意,但一旦确定以后在算法执行过程中就不再改变. 当前弧(Current-Arc): 对每个节点i,用一个指针指向下一条将要被检索的弧,这条弧称为当前弧. 算法开始时,当前弧为A(i)中的第一条弧。 在查找从该节点出发的允许弧时,总是从当前弧开始判别:如果当前弧是允许弧,则返回这条弧;否则令A(i)中的下一条弧为当前弧。 如此下去,直到找到一条允许弧或判别完 A(i)的最后一条弧为止。 6.3.3 复杂度分析 1 2 4 2 2 3 1 2 3 4 5 6 0 5 4 10 0 初始当前弧:(1,2) 当前弧:(3,4) 分析:即确定“前进步”、“回退步”、增广、重标号的次数及每次的复杂度 最短增广路算法 – 采用当前弧(Current-Arc)结构时: 如果 A(i)中的一条弧在以前的迭代中不是允许弧,则在节点i的标号改变之前它仍然不是允许弧. Why? 非允许弧(i,j)的两种情况:(1) uij(x)=0; (2) d(i)d(j)+1. 这样我们得到如下结论: 复杂度分析 引理6.5 在最短增广路算法的执行过程中, 如果每个节点的重新标号操作不超过k次,则算法查找允许弧和重新标号操作的总复杂度为O( |A(i)|)=O(km). 如果判别完 A(i)的最后一条弧仍然没有找到允许弧,则说明 A(i)中不存在允许弧;这时,算法必须执行对该节点的重新标号操作,并重置该节点的当前弧为A(i)中的第一条弧. 由于对节点i的一次检查和一次重新标号操作分别需要对A(i)检索一遍,因此复杂度为O(| A(i)|). 6.3.3 最短增广路算法 –复杂度分析
您可能关注的文档
- 5 - 汉能控股集团.pdf
- 5 月份目录 - 格兰名筑,东莞格兰名筑房地产开发有限公司,东莞格兰名筑.pdf
- 5 消除瓦斯气体造成的问题 - 松井制作所.pdf
- 5-2.深圳市建筑节能改造项目方案审查要点 - 深圳市环境工程科学技术 ....doc
- 5-4自然资源的保育与永续发展.ppt.ppt
- 5. oracle erp销货管理系统的模组:客户订单模组、出货作业模组。.ppt
- 5-隔墙与隔断2.pdf
- 5. 外汇市场技术面分析 - ads prime.pdf
- 5. 募投项目—资金运用3.1 电子信息业务.ppt
- 5. 常规岛主厂房抗震设计 - 国家核电学习系统.ppt
- 第一单元隋唐时期繁荣与开放的时代(原卷板).docx
- 第04讲测量平均速度(原卷版)-2022年新八年级物理暑假课(人教版).docx
- 第01课邓稼先(基础训练)(原卷版).docx
- Unit1单元小结-2022-2023学年七年级英语下册(牛津深圳版).docx
- 专题21书面表达考点4叙事描写类-2022年中考英语真题分项汇编(原卷版).docx
- 秘籍13 化学解答题(原卷版).docx
- 8.1牛顿第一定律2.docx
- 第13练感叹句-2022年七年级英语(牛津上海版).docx
- 儿童瑜伽培养小学生的身体协调性和集中力.pptx
- 第1章数学与我们同行全章复习与检测卷(4个知识点2种题型)(原卷版).docx
文档评论(0)