M算法的研究.doc

重庆邮电大学研究生堂下考试答卷2011-2012学年第二学期 考试科目：图论及其算法 专 业：信息与通信工程 2012/12/7摘要：本次论文首先介绍了图论中的最大流算法，然后主要研究了其应用到解决通信网中从源端到宿端可能达到的最大流量的计算过程。网中的各条通信线路归为一个图的模型之后，写出该图的邻接矩阵后，确定该图的割量从而求出最大流量的值。进而用代码实现算法，最后在VC+6.0的编译环境下调试并对该算法作了进一步的优化展望。关键词：最大流算法 邻接矩阵 割量 VC+6.0第一章 引言1.1图论的相关展述图论是一门发展迅速而又广泛应用的学科。它广泛地应用于物理、化学、运筹学、计算机科学、信息论、网络理论等几乎所有的学科领域。另一方面，随着这些学科的发展，特别是计算机科学的快速发展，有大大促进了图论的发展。运用图论知识解决实际问题，有着非常独特与聪明之处。基于此，本次论文便是应用图论中的最大流算法，来解决实际通信网络中从源端到宿端可能达到的最大流量的计算1。1.2通信网中的最大流问题网的作用主要是将业务流从源端送到宿端。常见的有商品在运输网中的传递，邮件在邮政网中的分发，信息在通信网中的输送。为了充分利用网资源，包括线路、转接设备等，总希望合理的分配流量，以使从源到宿的流量尽可能大，传输代价尽可能小等。流量分配的好坏将直接关系到网的使用效率和相应的经济效益，是网运行的重要指标之一。网内流量的分配并不是任意的，它受限于网的拓扑结构、边和端的容量，所以流量分配实际上是在某些限制条件下的优化问题。比如说，要研究信息网络中对信息的传输能力，很显然这些网络都具有源端(发点)和宿端(收点),且每一弧都有明确的最大通过能力(容量) 。但是由于网络配置的原因, 各弧的实际能力往往达不到各弧的最大通过能力。利用标号算法求解网络最大流是目前最优秀的算法之一。通过该算法能够计算出实际通过最大能力即网络的最大流量问题，可以充分发挥网络的设备能力, 且能够明确得知如何改造网络可以使得最大流量增大。第二章 网络流相关概念2.1对相关概念的简单阐述2.1.1流网络(Flow Netwok)(1)流网络图：流网络图G=(V,E)是一个有向图，其中每条边(u,v)E均有一非负容量c(u,v)0。如果(u,v)E,则假定c(u,v)0。流网络中有两个特别的顶点：源端s和宿端t2。图1.1 一个网络流的例子，边上的数字表示该弧的容量(2)流(Flow)：用fij表示该弧(由顶点i到顶点j的弧)上的当前通信流量，用cij 表示该弧上的最大通信容量。那么fijcij的前向边称为饱和边；fijcij的前向边称为非饱和边；反向边则分为零流量和非零流量。(3)割：流网络G=(V,E)的割(S,T)将顶点集V划分成S和T=V-S两部分，使得sS，tT。定义割(S,T)的容量为c(S,T)下面是一个割的例子：图1.2 一个割的例子，割的容量为2+2+1+6=11(4)可增流路：从VsVt的一条路径P中，如果所有的前向边都未饱和，所有的反向边都是非零流量，则此条路径称为可增流路。 可增流路的性质：在可增流路上，所有正向边的流量均可增加不致破坏流量的有限性；所有反向边上均可减流不致破坏非负性；可减流路上的减流相当于正向边上增流；含有多条边的可增流链路上的增流（包含反向边上减流）的最小值，应当是：此处eij代表链路中的正向边，eji代表反向边。可增流路在增流以后（反向边上减流），可得一新的可行流并使源宿端间的流量增加。 如果可行流fij已经使得源宿端间的流量得到最大值，则从VsVt的每一条路上，至少有一个饱和的前向边，或一个零流的反向边，也就是不存在一条可增流（可减流）的路。(5)增广路径：对于残留网络中中的一条s-t路径p，我们称其为增广路经，定义增广路径p的残留容量为p上弧容量的最小值。增广路径时求最大流中一个很重要的概念。(6)增广：对于一条增广路径P，增广的意思就是对于每一条属于P的弧(i,j)，将fij 增加p的残留容量，将fji减少p的残留容量。这样新的流fij就得到了增广。2.1.2 相关定理(1).最大流量最小割量定理：当源宿间的流量达到最大，每个割集 中的前向流量都等于最大流量Fmax，并且总存在这样一个割集，其每条正向边都是饱和的，其割量在各个割集中达到最小值，并且也等于Fmax。第三章 最大流的算法3.1算法的基本思想寻找源端到宿端fij可增广的路径，使网络流的流量得到增加，直到达到最大容量为止。算法分2个过程：1是标记过程，通过标记过程找到一条可增广路径；2是增广过程，即沿增广路径增加网络流量的过程。3.2算法及其代码实现3.2.1 标记过程(1)本次所设计的程序采用以输入邻接矩阵形式代替输入网络图，在邻接矩阵上上直接给出流量矩阵。两者结合就构成了一个网络图的数字实现。代码如下：(2)算法步骤M0：初始，令fij0，标出其相邻端的流量、方向；选择任一链路；M1: 标源端为（，s，）；M2：查已标、未查端Vi，标出其所有的邻端。若宿端已经被标记，那么转至算法的增广过程，否则返回M1重标源端。标邻端时分三种情况3：由端i到端j有边，且cij fij,即可增流，则标（，i，ej），表示可增流ej，其中ejmin（cijfij,，ei）；若由端j到端i有边，且fji0, 则给j点标号(i, ，ej), 其中ej=min(ei, fji),即可减流ej。不符合前两条，决定不标。因此M算法中图G的节点标记有三种情况：未标记节点：所有未赋标记的节点；未检查的标记节点：如果节点 x 已有标记，但其邻接节点y没有完全标记，则x称为未检验的标记节点；已检查的标记节点：若节点 x 已标记， x 所有邻接的节点都已标记，则x 称为已检验的标记节点。3.2.2 增广过程第1步：设节点Z=t，转至下面的第2步； (逆向增广)第2步：若Z的标记(+, q, ez)，将流fqz变成fqz+ ez；若Z标记(, q, ez)，将流fzq变成fzqez；第3步：若 q = s，取消网G中所有节点的标记，并转至算法标记过程第1步，进行下一次迭代过程；若 q s，设q = Z，返回增广过程第2步。3.2.3 求增广之后的最大流量前面已经定义过割量的定义，那么我们求最大流量时就是先找出这个图的割集，计算算法结束时割集上的fqz或fij之和4。3.2.4 编译环境 本次设计的程序用C+语言实现，编译环境为VC+6.0。核心代码的实现参考附件。第四章 测试与分析4.1 完成相关测试我们根据下图各端的连接情况，以及各边上标的容量值来做一个简单的测试。现给定一有向图，如图4.1所示。图4.1 给定的有向图示例我们首先写出邻接矩阵如下：0 1 1 1 1 00 0 0 0 0 10 1 0 0 0 00 0 1 0 0 10 1 0 1 0 10 0 0 0 0 0再写出各边上的通量如下：0 4 3 5 9 00 0 0 0 0 80 5 0 0 0 00 0 0 6 0 40 5 0 7 0 30 0 0 0 0 0运行程序编译的结果如图4.2所示。图4.2 图4.1示例计算结果由上图可知，计算结果和用算法写出来的结果一样，这样就基本上验证了程序的正确性。4.2 分析比较首先对比一下用C+实现和用Matlab实现的不同之处。Matlab的实现更具有可观性，而且编写代码时简单，工作量小，相对的，用VC+编写就显得稍微麻烦了，因为这是一个一直循环搜索的程序，编写时要完成的代码很多，而且调试的时候稍微麻烦。但是VC+编写的可植入性很好。现在只是解决了一个最大流问题，如果在每一条弧上在加上一个费用，然后去计算具有最小费用的最大流路径，此时我们只需编写另外一个矩阵，写入相应代码即可，因此从这一方面也体现了用VC+编写的好处。 第五章 结束语网络最大流问题的应用是一项十分有意义的研究工作，对于实际问题中寻求网络最大流解法，可以帮助我们很快地解决问题。本文采用标号方法完成了网络最大流算法的计算过程，通过最大流量最小割量定理可以求得所寻求的增广路径的流量和，也就是最大流量。最后用代码实现算法过程，在运行中只需要输入网络图的邻接矩阵，以及对应的各边容量，能很快得出最大流量值。如果在每一条弧上在加上一个费用，然后去计算具有最小费用的最大流路径，这时我们可以去研究负价环算法，或者此时我们可以在上面最大流问题的研究基础上编写另外一个费用矩阵，写入相应代码，调试即可。另外，编程虽是辛苦劳累的，但是收获同样是巨大的，在设计中每解决一个问题，那种成就感是无法言语的，设计中第一次调试程序时出现了逻辑错误，编译能通过，运行始终无法通过，后来经过自己思考，找同学咨询，借助参考书资料以及网络资源，找到了问题所在，进行了多次修改调试之后终于得到了运行结果，这让我感觉到了学会收集资料也是很重要的，可以在这个过程中学到不少知识。最后，由于能力有限，也仅仅限于将算法用代码实现，并没有对算法作深入研究，比如说，对于标记各端时，可以加一些调整过程，从而使算法更简洁。这样的问题很多，需要学习的地方亦有很多。参考书目：1 图论及其算法 殷剑宏 吴开亚 编著2 通信网理论基础 张琳 望育梅 禹可 刘雨 编著3 算法导论 Thomas H.corman Charles E.leiserson Ronald L.Rivest Cliffor stein 编著4 算法艺术与信息竞赛 刘汝佳 黄亮 著5 C+ Primer中文版 Stanley B Lippman Josee Lajoie 编著 潘爱民 张丽 译附件（核心代码）：int fordForkerson(int num) /首先检查与源点s相连的点，对每个与它相连的点都进行标号 int cishu = 0;/该变量用于假如源端没有一条路径可到达宿端的情况，此时可以强制将程序跳转到最后计算最大流量处。int maxFlow = 0; while (1)/每次重新求增广路径，先清空当前监测点，保证从0开始 int curNum = 0; while (1)if (vertexMatrixcurNumcurNum.isLabeled = true & vertexMatrixcurNumcurNum.isChecked = false)for ( int i = 0;i num;i+)/如果某个点与已经标号点所连并且未标号并且可以标号（指所连边上尚有可通过容量）那么首先将它标号 /若弧(i,j)上, fij 0 ) /进行标号 vertexMatrixii.isLabeled = true; /可通过i,i点的流选择前一个点可通过的流和将这两个点所连接的边可通过的流的最小值 vertexMatrixii.maxFlowNum = (vertexMatrixcurNumcurNum.maxFlowNum 0) /进行标号 vertexMatrixii.isLabeled = true; /此时是反向弧 /若弧(j,i)上，fji0, 则给j点标号(i, -，d(j), 其中d(j)=min(d(i), fji), vertexMatrixii.maxFlowNum = (vertexMatrixcurNumcurNum.maxFlowNum = flowMatrixicurNum.currentFlow ?vertexMatrixcurNumcurNum.maxFlowNum:flowMatrixicurNum.currentFlow); flowMatrixicurNum.isThisFlow = true; /表示curNum,curNum点进行了检查 vertexMatrixcurNumcurNum.isChecked = true; /退出条件为终点被标记或者其他几个点都被checked但终点未被标记 bool status = true; for ( i = 0;i num;i+)status = status & vertexMatrixii.isChecked;if (vertexMatrixnum-1num-1.isLabeled = true) | (status = true & vertexMatrixnum-1num-1.isLabeled = false)break; curNum+; if (curNum = num)curNum = 0;elsecurNum+; if (curNum = num)curNum = 0; cishu+;if (cishu = num-1)break;/最后检查终点num-1是否被标号，标号的话，说明存在一条增广路径，按照求得的可以增加的最大流值对其进行增广 if (vertexMatrixnum-1num-1.isLabeled = true)/说明终点已经进行标号，必然存在一条增广路径，反向查找 /可以增广的流量就是最终终点标记的流 int canAddFlow = vertexMatrixnum-1num-1.maxFlowNum; /tempEnd保存临时终点，用于反向递推 int tempEnd = num-1; while (1)for (int i = 0;i num;i+)if (flowMatrixitempEnd.isThisFlow = true)flowMatrixitempEnd.currentFlow += canAddFlow; flowMatrixitempEnd.restFlow = flowMatrixitempEnd.construct - flowMatrixitempEnd.currentFlow; /反向递推，向前推一个点 tempEnd = i; /标记到每个点的来源点和来源通路必定只有一个 break;if (flowMatrixtempEndi.isThisFlow = true)flowMatrixtempEndi.currentFlow -= canAddFlow; flowMatrixtempEndi.restFlow = flowM