《(精品)图论动画-最小全局切割算法.ppt》由会员分享,可在线阅读,更多相关《(精品)图论动画-最小全局切割算法.ppt(29页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、15.082 和和 6.855J 最小全局切割动画最小全局切割动画初始化初始化1325641115346饱和结点饱和结点1发出的弧发出的弧.更新剩余网络更新剩余网络2初始化初始化054321245361计算到结点计算到结点2的距离的距离判定可进入弧判定可进入弧11325641115346516413我们将再也不我们将再也不会从结点会从结点1推推进或者推进到进或者推进到结点结点1内内.3推进推进/重标号重标号054321245361选择一活动结点选择一活动结点1Carry out 推进推进/重标号重标号13256411346516413324推进推进/重标号重标号054321245361选择一活
2、动结点选择一活动结点1重标号重标号.不存在可进入弧不存在可进入弧.132564116465164132335推进推进/重标号重标号05432124561选择一活动结点选择一活动结点1从结点从结点3 推进推进.1325641164651641323116推进推进/重标号重标号05432124561选择一活动结点选择一活动结点1重标号结点重标号结点 3.规则规则:没有空层允许没有空层允许.132564164652641323117间隙间隙令令 t 表示当前漏结点表示当前漏结点.令令 dmax 是除了源结点外的结点的最大距离标号是除了源结点外的结点的最大距离标号.空层空层是有值是有值 k 且且 d(
3、t)k dmax 以至于没有结点以至于没有结点j 是是 d(j)=k.如果我们把如果我们把d(3)增加到增加到 7,我们创建了一个间隙我们创建了一个间隙.在这种情在这种情况下况下,我们把我们把d(j)增加到增加到 dmax+1.8推进推进/重标号重标号05432124561重标号结点重标号结点 3,因此没有,因此没有创建创建空层空层.113256416465264132311339切割层切割层05432124561切割层切割层 是仅有一个结点需要重标号的是仅有一个结点需要重标号的 层层.11325641646526412 113在剩余网络中,没有从切割层的结点到下方结点的路径在剩余网络中,没有
4、从切割层的结点到下方结点的路径.10切割切割-层层 rule总是选择在最低切割总是选择在最低切割-层下方的活动结点层下方的活动结点.如果每个活动结点是在或高于切割层如果每个活动结点是在或高于切割层,那么停止,得到最那么停止,得到最大预流大预流/最小切割最小切割.11推进推进/重标号重标号05432124561在最小切割层之下在最小切割层之下选择一活动结点选择一活动结点.11325641646526412 113从结点从结点 4 推进推进.412推进推进/重标号重标号05432124561在最小切割层之下选择一活动结点在最小切割层之下选择一活动结点.1325641636526512 13从结点从
5、结点 6 推进推进.2613推进推进/重标号重标号05432124561在最小切割层之下选择一活动结点在最小切割层之下选择一活动结点.1325641634528512 13从结点从结点 5 推进推进.2514推进推进/重标号重标号05432124561在最小切割层之下选择一活动结点在最小切割层之下选择一活动结点.132564263452852 13重标号结点重标号结点 5,如果它将不创建空层,如果它将不创建空层.1515寻找首个切割结束寻找首个切割结束05432124561在最低切割层下在最低切割层下不存在活动结点不存在活动结点.132564263452852 13最大预流和最小切割已经被发现
6、最大预流和最小切割已经被发现.1令令T 是是能到达漏结点能到达漏结点所有结点所有结点.16结束寻找第一个切割结束寻找第一个切割05432124561这是第一个最小切割这是第一个最小切割.3132564111534617开始第二个切割开始第二个切割05432124561在最低层选择新的漏结点在最低层选择新的漏结点132564263452852 13使使 结点结点 2 成为源结点成为源结点1饱和从饱和从 结点结点 2出来的弧出来的弧.25518Beginning of the second 切割切割05432124561我们将不再从结点我们将不再从结点 2推进或推进或 推进到结点推进到结点 2.1
7、325643452852 73没有必要物理上合并结点没有必要物理上合并结点 1和和 2.5219推进推进/重标号重标号05432124561选择一活动结点选择一活动结点1325643452852 73重标号结点重标号结点 3,如果它没有创建空层,如果它没有创建空层.52320推进推进/重标号重标号05432124561层层 4 变成了一切割层变成了一切割层1325643452852 73在切割层下,没有活动结点在切割层下,没有活动结点.52第二个切割已经发现第二个切割已经发现.令令T 是所有能到达漏结点的结点是所有能到达漏结点的结点21推进推进/重标号重标号05432124561这是第二次切割
8、这是第二次切割.3132564111534622开始第三次切割开始第三次切割05432124561让结点让结点 5 是源结点是源结点1325643452852 73结点结点 6 变成新的漏结点变成新的漏结点52饱和从结点饱和从结点 5发出的弧发出的弧.556623开始第开始第3次切割次切割05432124561层层3 仍然是切割层仍然是切割层13256435252 73在切割层下,仍然没有活动结点结点在切割层下,仍然没有活动结点结点.52我们已经发现了第我们已经发现了第3 个切割个切割令令 T 是所有能从漏结点到达的结点是所有能从漏结点到达的结点.24第第3 切割切割05432124561上面
9、的切割是最好的切割,上面的切割是最好的切割,1,2,5 在一边,结点在一边,结点 6 在另一边在另一边.3132564111534625开始第开始第4个切割个切割05432124561结点结点 6 变成一源结点变成一源结点13256435252 73结点结点4 变成下一个源结点变成下一个源结点52饱和从结点饱和从结点6 发出的弧发出的弧664426我们已经找到第我们已经找到第4和第和第5切割切割054321245611325645 2 9352在网络中仅有的弧是从源结点出来的弧在网络中仅有的弧是从源结点出来的弧.我们能停止算法以及识别剩余的切割我们能停止算法以及识别剩余的切割.27这是切割这是切割4和和513256411153461325641115346切割切割 4切割切割 528全局最小切割是切割数全局最小切割是切割数 20543212456131325641115346算法结束时,结点算法结束时,结点1在源边,得到最小切割在源边,得到最小切割.29