《网络单纯形算法》PPT课件.ppt

15.082 和 6.855J,网络单纯形动画,2,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,有供应和需求的树.(假设所有的其他弧的流是0),在弧(4,3)中的流是什么？,3,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,为了计算流，向上迭代树，寻找流能唯一确定的弧.,在弧(5,3)中的流是什么？,2,4,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,在弧(3,2)中的流是什么？,2,3,5,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,在弧(2,6) 中的流是什么?,2,3,6,6,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,在弧(7,1)中的流是什么?,2,3,6,4,7,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,在弧(1,6)中的流是什么?,2,3,6,4,3,8,计算生成树流,1,3,6,4,5,2,7,1,3,-6,-4,1,2,3,注释: 有两中不同的方法计算在(1,2)的流，两种方法都给出流为 4.这是巧合吗？,2,3,6,4,4,3,9,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,这里是有弧代价的生成树.如何选择结点势以便即约代价是0呢？,回忆: (i,j)的即约代价是 cij - i + j,10,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,1 可以被任意设置.我们令 i = 0.,结点 2 的单纯形乘子是什么？,在最小代价流问题中，有一个多余的限制.,0,计算生成树的单纯形乘子,11,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点 7 的单纯形乘子是什么？,0,(1,2)的即约代价是c12 - 1 + 2 = 0. 因此5 - 0 + 2 = 0.,-5,12,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点 3 的单纯形乘子是什么？,0,(7,1)的即约代价是c12 - 1 + 2 = 0. c71 - 7 + 1 = 0. 因此 -6 - 7 +0 = 0.,-5,-6,13,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点 6 的单纯形乘子是什么？,0,-5,-6,-2,14,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点 4 的单纯形乘子是什么？,0,-5,-6,-2,-1,15,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,结点 5 的单纯形乘子是什么？,0,-5,-6,-2,-1,-4,16,计算生成树的单纯形乘子,1,3,6,4,5,2,7,5,-6,-2,-4,1,3,有单纯形乘子和这棵树相关.它们不依弧流，也不依赖非树弧上的代价.,0,-5,-6,-2,-1,-4,-1,17,网络单纯形算法,1,2,4,5,3,2,-4,2, $4,4, $2,1, $4,5, $5,3, $5,4, $1,4, $2,3, $4,5,-3,最小代价流问题,18,生成树流,1,2,4,5,3,2,-4,1,0,0,3,2,0,1,3,5,-3,初始生成树解,T L U,19,单纯形乘子和即约代价,1,2,4,5,3,0,-4,0,?,4,0,0,-2,0,2,3,-2,初始单纯形乘子和即约代价,T L U,c45 = 2,什么弧是违规的？,3,20,添加违规弧到生成树，创建圈,1,2,4,5,3,3,2,4,0,4,1,3,3,弧(2,1) 添加到了树中,T L U,圈是什么，能发送多少流？,2, 1,4, 0,1, 0,5, 3,u14, x14,21,环绕圈发送流,1,2,4,5,3,3,0,4,2,4,3,3,3,沿着圈发送2 单位的流,T L U,下一个生成树是什么？,2, 1,4, 0,1, 0,5, 3,u14, x14,22,旋转(pivot)之后,1,2,4,5,3,3,0,4,2,4,3,3,3,更新的生成树,T L U,在旋转中，一条弧加入到 T， 而另一条弧从 T 删除.,2, 1,4, 0,1, 0,5, 3,u14, x14,23,更新乘子,1,2,4,5,3,当前乘子和即约代价,T L U,0,-4,0,4,4,0,0,-2,0,2,3,-2,3,我们如何使cp21 = 0 ，且让其他树弧有 0 即约代价？,24,从 T 删除 (2,1) 把 T 分裂成两部分,1,2,4,5,3,添加 到树的一侧不影响任何树弧的即约代价，除了 (2,1). 为什么?,T L U,0,-4,0,4,4,0,0,-2,0,2,3+,-2+,3,应该选择什么样的 值，产生即约代价 (2,1) = 0?,25,更新的乘子和即约代价,1,2,4,5,3,更新的乘子和即约代价.,T L U,0,-4,0,2,2,0,2,0,0,2,1,-4,3,这棵树的解是最优的吗？,26,添加一条违反弧到生成树，创建圈,1,2,4,5,3,添加弧 (3,4) 到生成树,T L U,3,0,4,2,4,3,3,3,2, 1,4, 0,1, 0,5, 3,圈是什么，能发送多少流？,27,沿圈发送流,1,2,4,5,3,沿圈发送1 个单位的流.,T L U,3,0,4,2,4,2,3,2,2, 2,4, 0,1, 0,5, 3,下一个生成树解是什么？,28,下一个生成树解,1,2,4,5,3,这是更新的生成树解,T L U,3,0,4,2,4,2,3,2,2, 2,4, 0,1, 0,5, 3,29,更新的乘子,1,2,4,5,3,这是当前乘子.,T L U,0,-4,0,2,2,0,2,0,0,2,1,-4,3,我们如何修改乘子？,30,更新的乘子,1,2,4,5,3,这是更新的乘子.,T L U,0,-4 +,0,2,2,0,2,0,0,2,1,-4,3, 应该是什么值?,31,更新的乘子,1,2,4,5,3,这是更新的乘子.,T L U,0,-6,-2,4,2,0,2,0,0,0,1,-4,3,当前生成树解是最优的吗？,32,最优解,1,2,4,5,3,这是最优解.,T L U,0,-6,-2,4,2,0,2,0,0,0,1,-4,3,没有弧违反最优条件.,33,寻找圈,1,3,6,10,11,8,7,9,12,5,2,34,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,2,4,depth(5) = 4; depth(3) = 2; 用 pred(5)替换结点5,35,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,2,3,depth(9) = 3; depth(3) = 2; 用 pred(9)替换结点9,36,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,2,2,depth(2) = 2; depth(3) = 2; 用 pred(2)替换结点2; 用 pred(3)替换结点3,37,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,1,1,depth(8) = 1; depth(7) = 1; 用 pred(8)替换结点8; 用 pred(1)替换结点7,38,使用深度和前驱,1,3,6,10,11,8,7,9,12,5,2,0,结点3和5的最小共同祖先被找到.,39,更新乘子：使用线和深度,1,3,6,10,11,8,7,9,12,5,2,假设弧 (1,8)将从树中删除.以结点8为根的子树是什么？,40,跟随从结点8开始的线,1,3,6,10,11,8,7,9,12,5,2,什么是thread(8)?,41,跟随从结点8开始的线,1,3,6,10,11,8,7,9,12,5,2,什么是thread(3)?,42,跟随从结点8开始的线,1,3,6,10,11,8,7,9,12,5,2,什么是thread(10)?,43,跟随从结点8开始的线,1