资源描述：
《15(最大流问题).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、最大流量问题本节内容相关概念与基本定理求解网络最大流方法7/24/20211山东交通学院信息工程系流量网络定义给定一个n个顶点加权连通图，该图具有如下特性：包含1个没有输入边的顶点；该点称为源点。包含1个没有输出边的顶点；该点称为汇点。每条有向边的权重uij是一个正整数，称为该边的容量(这个数字表示该边所代表的链路把物质从i送到j的数量上限)。满足以上特性的有向图称为流量网络。7/24/20212山东交通学院信息工程系设源点与汇点分别是物质流中惟一的出发地和目的地。进入中间点物质总量必须等于离开物质总量，这个条件称为能量守恒要求。如
2、果用xij来标记通过边(i,j)传输量，则：7/24/20213山东交通学院信息工程系容量约束：对于每条边(i,j)E来说，0xijuij可行解：一个给定一个网络的流，使得它满足流量守恒约束和容量约束。最大流量问题：7/24/20214山东交通学院信息工程系最大流量求解方法最大流量问题求解有两种方法单纯形法增益路径法7/24/20215山东交通学院信息工程系增益路径法从流量0开始，试着找一条可以传输更多流量的、从源点到汇点的路径。这样路径称为流量增益。如果找到了一条流量增益路径，沿路径调整边上的流量，以得到更大的流量值。迭代,
3、直到找不到为止。7/24/20216山东交通学院信息工程系增益路径的实现举例沿路径1→2→3→6，最多把流量增加2个单位。由于不能再进一步增加，算法结束，得到结果（b）。但此时不为最优结果，沿路径1→4→3←2→5→6流量还能增加。7/24/20217山东交通学院信息工程系扩展增益路径法为求流量x的增益路径，需考虑两类边：前向边：从i连向j，该边具有正的未使用的容量rij=uij-xij。后向边：从j连向i，该边具有正的流量xjiij未使用的容量rij=uij-xijij流量xji前向边后向边7/24/20218山东交通学院信息工程
4、系扩展增益路径法对于给定容量的增益路径，设r是所有前向边中未使用的容量和后向边中具有正的容量xji中的最小值。如果在每条前向边上增加容量r，在向后边上减去r，得到一个更大的可行流量。7/24/20219山东交通学院信息工程系扩展增益路径的实现举例上图b中，增益路径1→4→3←2→5→6。(1,4),(4,3),(2,5),(5,6)是前向边，(3,2)是后向边，最小值r=1，根据r值进行调整，得到c。7/24/202110山东交通学院信息工程系增益路径法性能退化路径生成次序如果不恰当，会对该方法效率产生巨大的影响，如下图：沿路径1→
5、2→3→4对流量0进行增益，会得到(b)中值为1的流量。沿路径1→32→4对流量0进行扩展增益，会得到(c)中值为2的流量。共迭代2U次才能得到最大流量值2U。7/24/202111山东交通学院信息工程系增益路径法性能退化2次得到最大流量值方法：沿路径1→2→4对流量0进行增益。沿路径1→3→4对流量0进行增益。增益路径法依赖于路径生成次序，生成次序不恰当，会对该方法效率产生巨大的影响。7/24/202112山东交通学院信息工程系最短增益路径法基本思想：用广度优先查找，用数量最少的边来生成增益路径。具体策略：两个记号来标记一个新的
6、(未标记)顶点第一个标记指出从源点到被标记顶点还能增加多少流量。第二个标记指出另一个顶点的名字。7/24/202113山东交通学院信息工程系两个记号来标记一个新的(未标记)顶点第一个标记指出从源点到被标记顶点还能增加多少流量。第二个标记指出另一个顶点的名字。第二个标记加上+或-号，用来指出该顶点是通过前向边还是后向边得到的。7/24/202114山东交通学院信息工程系如果未标记顶点j是由从i到j的有向边和遍历队列中的前面顶点i相连接，而且j具有大于0的未使用容量rij=uij-xij,那么顶点j就标记为lj,i+，其中lj=min{
7、li,rij}。7/24/202115山东交通学院信息工程系如果未标记顶点j是由从j到i的有向边和遍历队列中的前面顶点i相连接，而且j具有大于0的流量xij,那么顶点j就标记为lj,i-，其中lj=min{li,xij}。7/24/202116山东交通学院信息工程系处理2结点时，由于从1到2未使用容量为2，因此2顶点标记为min{,2},1+.处理3结点时，由于从2到3未使用容为5，因此3顶点标记为min{2,5},2+.这种标记的遍历结束于汇点6，沿着路径1→2→3→6用2对流量进行增益。7/24/202117山东交通学院信息工
8、程系下一次迭代时过程。这种标记的遍历结束于汇点6，沿着路径1→4→3→2→5→6用1对流量进行增益。7/24/202118山东交通学院信息工程系再一次迭代时由于没有增益路径(汇点没有被标记)，当前流量已经是最大的了。7/24/2021
