发布时间 : 星期六 文章基于预流推进的最小标号最大流算法更新完毕开始阅读9bd60880fd4ffe4733687e21af45b307e971f90c
预流推进算法时间复杂度上界为O（mn2），由于最小标号预流推进算法会产生最频繁的活跃节点更新，因此，最小标号预流推进算法到达了时间复杂度上界。而新增加的终止条件执行次数不超过2n次，每次操作不超过n步，因此算法时间复杂度仍然为O（mn2）。在稀疏网络中，由于O（m）近似于O（n），因而会缩小最小标号预流推进算法与最高标号预流推进算法复杂度之间的差距，这是本文算法在稀疏网络中执行时间明显低于最高标号预流推进算法的原因之一。 预流推进算法需要构造剩余网络，算法以数组或矩阵形式存储剩余网络占用空间复杂度为O（n2），以稀疏矩阵或链表存储剩余网络占用空间复杂度为O（m）。 4.5预流推进算法的混合使用
最小标号选取规则的目的是在回溯发生前完成推进过程，使终止回溯现象成为可能，但其做法牺牲了算法复杂度并在非稀疏网络中有所体现，为了能够兼顾算法复杂度与算法终止回溯的能力，可以让该算法建立在最高标号预流推进算法基础上执行，即首先执行最高标号预流推进算法，当收点t在一段时间后无法获得更新，可怀疑算法已进入回溯阶段，从而使用最小标号算法将剩余低位势节点中的有效盈余推送至收点，然后终止算法。混合算法的时间复杂度介于O（n2m）与O（mn2）之间。 5仿真实验
本文仿真实验的平台是Matlab 2012b 64位版，运行于Windows8.1操作系统，处理器为Intel I74700HQ。仿真实验中用于对比的算法有：最小标号预流推进算法、最高标号预流推进算法、Dinic算法以及基于增广链修复的最大流求解算法[18]。仿真实验分为三组：第一组是非稀疏网络测试，第二组是稀疏网络测试，第三组是过渡网络测试。由于测试算法执行速度较快，为减小误差，每次测试均生成50个随机网络邻接矩阵，以算法平均执行时间进行衡量。此外，仿真实验还增加了算法稳健性测试，测试距离标号存在误差时的算法容错率以及将算法运行于图像分割应用实例。 5.1非稀疏网络仿真实验
非稀疏网络实验中采用节点规模为500～4000的ER随机网络，并以p=0.3随机连接节点对，网络的生成过程是： 1）创建一个规模为n的零矩阵作为邻接矩阵； 2）对矩阵中任意元素以p=0.3赋值为1； 3）将矩阵主对角线元素置0；
4）将矩阵中所有元素为1的位置赋予0～200随机整数值作为容量函数。
实验结果如图4所示，随着网络规模扩大，四种算法执行时间均持续提高，其中最高标号预流推进算法速度最快，Dinic算法速度最慢。 5.2稀疏网络仿真实验
稀疏网络实验中采用节点规模为500～4000的最邻近耦合网络，并以k=50连接邻居节点，网络的生成过程是： 1）创建一个规模为n的零矩阵作为邻接矩阵； 2）对矩阵主对角线附近的k=50个元素逐行全部赋值为1；
3）将矩阵主对角线元素置0；
4）将矩阵中所有元素为1的位置赋予0～200随机整数值作为容量函数。
实验结果如图5所示，随着网络规模扩大，四种算法执行时间均持续提高，其中本文算法和增广链修复算法速度最快，执行效率为最高标号预流推进算法5倍以上。 5.3过渡网络仿真实验
过渡网络实验中采用节点规模为2000的最邻近耦合网络，其关联边k值有所不同导致网络从稀疏向非稀疏过渡，创建过程与5.2节中相同，实验结果图6表明，本文算法、Dinic算法和增广链修复算法随着k值增加执行时间有着上升趋势，而最高标号预流推进算法呈现出下降趋势。 5.4实验结果分析
仿真实验验证了在稀疏网络中，最小标号预流推进算法能够充分发挥优势，甚至达到了最高标号预流推进算法执行速度的10倍，而在非稀疏网络中，该算法与最高标号预流推进算法的差距在1倍以内。之所以出现这种现象，源于3.2
节中的两组图解，在稀疏网络中，网路的分层数量较多导致发点s距离标号较大且可供推进的流量较少，若定义：k=回溯步骤/推进步骤，易见，当算法出现回溯现象时，随着网络稀疏程度增加，k值也会增加，在某些稀疏网络中，回溯步骤成为了算法执行过程的主导步骤，导致了最高标号预流推进执行时间远高于本文算法及一些增广链算法。相反，在非稀疏网络中，网络层数较低，k值对算法的影响将占据次要地位，此时时间复杂度的优势恰好得以体现，而由于网络层数较低，本文算法活跃节点更新次数较最高标号预流推进算法增加的十分有限，故执行效率差距不会过大。第三组实验中最高标号预流推进算法的反常表现验证了k值在算法执行过程随网络层数减少而降低。 5.5算法稳健性测试
稳健性测试实验中采用节点规模为500～4000的ER随机网络，以p=0.2随机连接节点对，实验对网络节点的距离标号分别进行两类破坏：第一类是在距离标号首次构建时产生错误，错误比例为2%；第二类是在距离标号在修改时产生错误，错误比例亦为2%。实验结果如表1所示。本文算法具备容错能力，由表1可知，算法仅在第二类错误中出现一次推进误差，其原因是某组节点标号的异常升高导致算法将这些节点上的盈余流划分到回溯过程中从而使结果偏小，网络规模越大，边数越多，则误差产生的可能性越小，因为