精华内容
下载资源
问答
  • 最大流问题

    千次阅读 2016-09-06 16:45:15
    举例描述最大流问题是一个很经典的问题,很多人对此也很熟悉,它能够等同于一个线性规划问题。下面给出最大流问题的一个基本描述:如下图所示,s是源点,t为汇点,每条边上数字的含义是边能够允许流过的最大流量。...

    举例描述

    最大流问题是一个很经典的问题,很多人对此也很熟悉,它能够等同于一个线性规划问题。下面给出最大流问题的一个基本描述:如下图所示,s是源点,t为汇点,每条边上数字的含义是边能够允许流过的最大流量。可以将边看成管道,0/3代表该管道每秒最多能通过3个单位的流量,0代表当前流量。最大流问题即是说,从s点到t点,最大允许流量是多少?

    这里写图片描述

    公式描述

    这里写图片描述
    的流量等于流出该点的流量。这个可以理解为流量守恒,就如同电流一样,流入一个电阻的电流必然等于流出的电流。

    那么最大流就可以表示为:
    这里写图片描述

    Ford-Fulkerson解法介绍

    该方法依赖于三种重要思想:残留网络,增广路径和割

    Ford-Fulkerson思想

    Ford-Fulkerson是一种迭代的方法。开始时,对所有的u,v属于V,f(u,v)=0(这里f(u,v)代表u到v的边当前流量),即初始状态时流的值为0。在每次迭代中,可以通过寻找一个“增广路径”来增加流值。增广路径可以看做是从源点s到汇点t之间的一条路径,沿该路径可以压入更多的流,从而增加流的值。反复进行这一过程,直到增广路径都被找出为止。

    增广路径

    举个例子来说明下,如图所示,每条红线就代表了一条增广路径,当前s到t的流量为3。当然这并不是该网络的最大流,根据寻找增广路径的算法我们其实还可以继续寻找增广路径。

    这里写图片描述

    残留网络

    顾名思义,残留网络是指给定网络和一个流,其对应还可以容纳的流组成的网络。具体说来,就是假定一个网络G=(V,E),其源点s,汇点t。设f为G中的一个流,对应顶点u到顶点v的流。在不超过C(u,v)的条件下(C代表边容量),从u到v之间可以压入的额外网络流量,就是边(u,v)的残余容量(residual capacity),定义如下:

    r(u,v)=c(u,v)-f(u,v)

    举个例子,假设(u,v)当前流量为3/4,那么就是说c(u,v)=4,f(u,v)=3,那么r(u,v)=1。

    我们知道,在网络流中还有这么一条规律。从u到v已经有了3个单位流量,那么从反方向上看,也就是从v到u就有了3个单位的残留网络,这时r(v,u)=3。可以这样理解,从u到v有3个单位流量,那么从v到u就有了将这3个单位流量的压回去的能力。

    我们来具体看一个例子,如下图所示一个流网络

    这里写图片描述

    对应的残留网络:

    这里写图片描述

    求解步骤举例

    1.获得残留网络

    2.穷举所有的增广路径

    如下图所示:

    这里写图片描述

    计算最大流的标号法

    这里介绍计算网络最大流的简便方法—标号法,此方法是Ford—Fulkerson 于1956年提出来的,它的原理是利用寻找增广链来不断改善可行流。
    设μ是网络中 到 的一条链,规定 到 的方向为μ的方向。 μ上与μ的方向一致的弧称为前向弧,前向弧的集合记为μ+, μ上与μ的方向相反的弧称为后向弧,后向弧的集合记为μ-。

    这里写图片描述
    上图
    若给一个可行流{},称网络中 = 的弧为饱和弧,称 <的弧为非饱和弧,称 =0的弧为零流弧,称 >0的弧为非零流弧。
    增广链:设{}是可行流, μ是 到 的一条链,若μ满足下列条件,则称μ为关于 f 的增广链。(注意: f ={})
    1°对于任何( ,)∈μ+,0≤ < (前向弧为非饱和弧)
    2°对于任何( ,)∈μ-,0 <≤ (后向弧为非零流弧)

    博客参考:

    smartxxyx的两篇博客:
    http://blog.csdn.net/smartxxyx/article/details/9275177
    http://blog.csdn.net/smartxxyx/article/details/9293665/
    以及:
    http://dec3.jlu.edu.cn/webcourse/t000048/yun/ch7_04.htm

    展开全文
  • 最小费用最大流问题

    千次阅读 2019-07-04 11:11:13
    最小费用最大流问题 解决如下最小费用最大流问题。 查了很多资源发现用MATLAB操作的好用的不多,所以综合了一下很多资源,给出了自己的理解。 基本思路为:把各条弧上单位流量的费用当做距离,用Floyd算法求最...

    最小费用最大流问题
    解决如下最小费用最大流问题。
    以前的资源由于matlab版本问题等已不适用。现在做出修改,适用于matlab2014a以后的版本。
    注意,数据格式按代码中的例子的格式,否则需要修改代码。
    查了很多资源发现用MATLAB操作的好用的不多,所以综合了一下很多资源,给出了自己的理解。
    网络
    基本思路为:把各条弧上单位流量的费用当做距离,用Floyd算法求最短路,确定一条自V1至Vn的最短路;再将这条最短路作为初始路径,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流。
    代码由GreenSim原创(源代码下载积分46),在其基础上加调试。读者根据自己需要设置流量矩阵和费用矩阵。
    代码

    展开全文
  • 图论--网络流最大流问题

    千次阅读 多人点赞 2019-10-28 21:21:05
    在介绍最大流问题的解决方法之前,先介绍几个概念. 网络:网络是一个有向带权图,包含一个源点和一个汇点,没有反向平行边。 网络流:网络流即网上的流,是定义在网络边集E上的一个非负函数flow={flow(u,v)}, ...

    问题表述:给定一幅图(n个结点,m条边),每一条边有一个容量,现在需要将一些物品从结点s(称为源点)运送到结点t(称为汇点),可以从其他结点中转,求最大的运送量。

    在介绍最大流问题的解决方法之前,先介绍几个概念.

    网络:网络是一个有向带权图,包含一个源点和一个汇点,没有反向平行边。

    网络流:网络流即网上的流,是定义在网络边集E上的一个非负函数flow={flow(u,v)}, flow(u,v)是边上的流量。

    可行流:满足以下两个性质的网络流flow称为可行流。

    容量约束:每条边的实际流量不能超过改变的最大流量。

    流量守恒:除了源点s和汇点t之外,所有内部节点流入量等于流出量。

    源点s:源点主要是流出,但也有可能流入。

    源点的净输出值=流出量之和-流入量之和。

    汇点t:汇点主要是流入,但也有可能流出。

    汇点的净输入值=流入量之和-流出量之和。

    对于一个网络可行流flow,净输出等于净输入,这仍然是流量守恒。

    网络最大流:在满足容量约束和流量守恒的前提下,在流网络中找到一个净输出最大的网络流。

    反向弧:若从u到v的边的容量为c ,这条边上有流量 f 流过(称为正向弧),则相当于v到u有一条容量为0的边,其流量为- f ,这条边就是反向弧。反向弧的作用主要是用于寻找增广路。

    反向弧的意义:反向弧的作用是起到有更优决策的时候会使当前选择的弧会自动放弃。反向弧有流量的原因是因为如果刚刚选择了正向弧,下一次如果存在更优策略使这f的流量流入汇点,就可以选择反向弧,将流量 f 撤销。

    残余网络计算出图中的每条边上容量与流量之差(称为残余容量),即可得到残余网络。注意由于反向边的存在,残余网络中的边数可能到达原图中边数的两倍。

    观察图下图,这种状态下它的残余网络。

    增广路径残余网络中任何一条从s到t的有向道路都对应一条原图中的增广路径 —— 只要求出该道路中所有残量的最小值d ,把对应的所有边上的流量增加d 即可,这个过程称为增广。

    最大流定理:如果残留网络上找不到增广路径,则当前流为最大流;反之,如果当前流不为最大流,则一定有增广路径。

    这样的话,求解最大流就只需要在残余网络中寻找增广路,直到不存在可以从s流向t 的增广路,此时即为最大流。求解最大流问题的高效算法有 dinic,sap和isap。

    我们今天讲最基础的FF算法与EK算法,他俩的区别在于一个是DFS找增广路,一个是BFS找增广路。后者高效一点。

    Edmonds-Karp算法:以广度优先的增广路算法,又称为最短增广路算法(Shortest Augument Panth, SAP)。

    最短增广路算法步骤:采用队列q 来存放已访问未检查的结点。布尔数组vis[]标识结点是否被访问过,pre[]数组记录可增广路上结点的前驱。pre[v]=u 表示可增广路上v 结点的前驱是u,最大流值maxflow=0。

    1. 初始化可行流flow 为零流,即实流网络中全是零流边,残余网络中全是最大容量边(可增量)。初始化vis[]数组为false,pre[]数组为−1。
    2. 令vis[s]=true,s 加入队列q。
    3. 如果队列不空,继续下一步,否则算法结束,找不到可增广路。当前的实流网络就是最大流网络,返回最大流值maxflow。
    4. 队头元素new 出队,在残余网络中检查new 的所有邻接结点i。如果未被访问,则访问之,令vis[i]=true,pre[i]=new;如果i=t,说明已到达汇点,找到一条可增广路,转向第(5)步;否则结点i 加入队列q,转向第(3)步。
    5. 从汇点开始,通过前驱数组pre[],逆向找可增广路上每条边值的最小值,即可增量d。
    6. 在实流网络中增流,在残余网络中减流,Maxflow+=d,转向第(2)步。

     这里给出EK算法模板:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <queue>
    #define INF 0x3f3f3f3f
    using namespace std;
    int n,m;
    const int maxn=1005;
    int g[maxn][maxn];//容量
    int f[maxn][maxn];//流量
    bool vis[maxn];
    int pre[maxn];
    bool bfs(int s,int t){
        memset(pre,-1,sizeof pre);
        memset(vis,false,sizeof vis);
        queue<int> q;
        vis[s]=true;
        q.push(s);
        while(!q.empty()){
            int now=q.front();
            q.pop();
            for(int i=1;i<=n;i++){
                if(!vis[i]&&g[now][i]){
                    vis[i]=true;
                    pre[i]=now;
                    if(i==t) return true;
                    q.push(i);
                }
            }
        }
        return false;
    }
    int EK(int s,int t){
        int maxflow=0;
        int u,v;
        while(bfs(s,t)){
            int d=INF;
            v=t;
            while(v!=s){
                u=pre[v];
                if(d>g[u][v])
                    d=g[u][v];
                v=u;
            }
            maxflow+=d;
            v=t;
            while(v!=s){
                u=pre[v];
                g[u][v]-=d;
                g[v][u]+=d;
                if(f[v][u]>0)
                    f[v][u]-=d;
                else f[u][v]+=d;
                v=u;
            }
        }
        return maxflow;
    }
    int main()
    {
        //int s,t;
        int u,v,c;
        while(~scanf("%d%d",&m,&n)){
            memset(f,0,sizeof f);
            memset(g,0,sizeof g);
            for(int i=1;i<=m;i++){
                scanf("%d%d%d",&u,&v,&c);
                g[u][v]+=c;
            }
            printf("%d\n",EK(1,n));
        }
        return 0;
    }
    

     

     

    展开全文
  • 网络流之最大流问题

    千次阅读 2016-05-17 15:20:50
    网络流的三个性质: 1、容量限制: f[u,v] 2、反对称性:f[u,v] = - f[v,u] ...最大流问题,就是求在满足网络流性质的情况下,源点 s 到汇点 t 的最大流量。 算法的关键在于 1)如何找出增广路径。 2)如何更新流

    网络流的三个性质:
    1、容量限制: f[u,v]<=c[u,v]
    2、反对称性:f[u,v] = - f[v,u]
    3、流量平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。
    只要满足这三个性质,就是一个合法的网络流.
    最大流问题,就是求在满足网络流性质的情况下,源点 s 到汇点 t 的最大流量。

    算法的关键在于
    1)如何找出增广路径。
    2)如何更新流量
    何为增广路径,说的直白些,所谓增广路径,就是找到这样一条路径,其流量不满,未达到容量上限。所有的可能的增广路径在一起便构成了残量网络。
    残量网络:为了更方便算法的实现,一般根据原网络定义一个残量网络。其中r(u,v)为残量网络的容量。r(u,v) = c(u,v) – f(u,v),通俗地讲:就是对于某一条边(也称弧),还能再有多少流量经过。
    增广路算法:每次用BFS找一条最短的增广路径,然后沿着这条路径修改流量值(实际修改的是残量网络的边权)。当没有增广路时,算法停止,此时的流就是最大流。
    图解最大流:





    可以证明,可行流为最大流,当且仅当不存在新的增广路径。
    下面是代码实现:
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<cstring>
    #include<iostream>
    using namespace std;
    #define INF 0x3f3f3f
    #define maxn 100000
    struct Edge
    {
        int from,to,cap,flow;
        Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f) {}
    };
    struct EdmondsKarp
    {
        int m;
        vector<Edge> edges;///边数的两倍
        vector<int> G[maxn];///邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
        int a[maxn];///起点到i的可改进量
        int p[maxn];///最短路树上p的入弧编号
        void init(int n)
        {
            for(int i=0; i<n; i++)
                G[i].clear();
            edges.clear();
        }
        void AddEgde(int from,int to,int cap)
        {
            edges.push_back(Edge(from,to,cap,0));
            edges.push_back(Edge(to,from,0,0));///反向弧
            m=edges.size();
            G[from].push_back(m-2);///记录每条弧的编号
            G[to].push_back(m-1);///记录对应反向弧的编号
        }
    
        int Maxflow(int s,int t)
        {
            int flow=0;
            for(;;)
            {
                memset(a,0,sizeof(a));
                queue<int>Q;
                a[s]=INF;
                Q.push(s);
                while(!Q.empty())///寻找増广路
                {
                    int x=Q.front();
                    Q.pop();
                    for(int i=0; i<G[x].size(); i++)
                    {
                        Edge& e=edges[G[x][i]];
                        if(!a[e.to]&&e.cap>e.flow)
                        {
                            p[e.to]=G[x][i];
                            a[e.to]=min(a[x],e.cap-e.flow);
                            Q.push(e.to);
                        }
                    }
                    if(a[t])break;
                }
                if(!a[t])break;
                for(int u=t; u!=s; u=edges[p[u]].from)///沿着増广路更新流
                {
                    edges[p[u]].flow+=a[t];
                    edges[p[u]^1].flow-=a[t];
                }
                flow+=a[t];
            }
            return flow;
        }
    } w;
    int main()
    {
        int n,i,from,to,cap,s,t;
        while(~scanf("%d%d",&n,&t))///n为边数t为结点数
        {
            w.init(n);
            for(i=0; i<n; i++)
            {
                scanf("%d%d%d",&from,&to,&cap);
                w.AddEgde(from,to,cap);
            }
            cout<<w.Maxflow(1,t)<<endl;
        }
    }
    /*
    输入
    8 6
    1 2 6
    2 3 4
    1 4 7
    4 5 2
    4 3 3
    2 5 4
    5 6 8
    3 6 4
    输出
    10
    */
    


    展开全文
  • 最大流问题使用MATLAB编写 程序 运筹学相关程序设计
  • FF最大流问题算法

    千次阅读 2018-11-23 11:38:13
    一、最大流问题 最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,以取得最好的效果。 实际来源: 有一个自来水管道运输系统,起点是 s,终点是 t,...
  • 文章目录基本概念图邻接矩阵最大流问题python解决最大流问题 基本概念 图 定义: 图G(V,E)是指一个二元组(V(G),E(G)),其中: V(G)={v1,v2,…, vn}是非空有限集,称为顶点集, E(G)是V(G)中的元素对(vi,vj)...
  • 网络最大流问题

    千次阅读 2014-01-17 13:56:26
    §4 网络最大流问题   网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量,金融系统有现金流,控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的...
  • 【运筹学】最大流问题

    千次阅读 2020-06-05 09:49:15
    ## 最大流问题 - 基本思路 1.找可行流(观察法设定即可或者直接设定所有的流量为0作为初始流) 2.找增广链 (1)找到,进入第三步。 (2)找不到,则目前的流是最优解。 3.调整流 割集:由V集合的点作起点,...
  • 最大流问题(超详细!!!)

    千次阅读 2019-10-12 09:11:40
    最大流问题是找出可以从顶点source到顶点sink总的物品数量(最大的那个)。 如上图所示,当0->1和2->1汇聚的时候不能超出1->3的值12(1的输出最大为12)。最后可以到达5的最大物品个数就是19+4=23。也...
  • 本篇承接上一篇文章,主要讲解最大流问题的Ford-Fulkerson解法。可是说这是一种方法,而不是算法,因为它包含具有不同运行时间的几种实现。该方法依赖于三种重要思想:残留网络,增广路径和割。本文将会详细介绍这些...
  • 网络最大流问题求解方法及实现

    千次阅读 2018-08-03 13:35:04
    最大流问题 在解决最大流问题中,我们需要求解就是在一个给定的流网络中找出最大流(同时给定源点和汇点) 具有多个源点和汇点的流网络问题的求解 在求解最大流问题时我们可能遇到具有多个源点和汇点的流网络,...
  • 之前学完最大流问题后没及时整理,最近学离散数学涉及到这方面的知识,就回过头来复习一下,顺便整理下来。 什首先,什么是最大流问题? 假设要把一些物品从结点S运送到结点T,可以借助其他结点进行中转,各...
  • 最大流问题以及FF算法

    千次阅读 2017-05-15 16:24:46
    最大流问题问题描述:给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).约束条件:设 G = (V, E) 是一个流网络,其容量函数为 ...
  • 最大流问题的Ford-Fulkerson方法,java实现
  • Java实现最小费用最大流问题

    万次阅读 多人点赞 2019-07-26 17:48:33
    最大流有多组解时,给每条边在附上一个单位费用的量,问在满足最大流时的最小费用是多少? 2 解决方案 下面代码所使用的测试数据如下图: package com.liuzhen.practice; import java.util.ArrayList; import ...
  • Bellman-Ford、SPFA、改进的Dijkstra三种算法解决最小费用最大流问题以及相关代码的实现。
  • 最小费用最大流问题

    千次阅读 2010-10-04 19:36:00
    ◆ 最小费用最大流【MCMF问题及数学模型】 在介绍最大流问题时,我们列举了一个最大物资输送流问题。如果这个问题的已知条件还包括每条边运送单位物资的费用,那么怎样运送,才能得到最大运输量,并且输送费用最少...
  • 使用标号算法(Ford-Fulkerson)解决最大流问题。 其基本思想是从某个可行流F出发,找到关于这个流的一个可改进路经P,然后沿着P调整F,对新的可行流试图寻找关于他的可改进路经,如此反复直至求得最大流。
  • 最大流问题 最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,以取得最好的效果。管道网络中每条边的最大通过能力(容量)是有限的,实际流量不超过...
  • 最大流问题:增广路径算法的比较

    千次阅读 2017-03-26 20:34:13
    最大流问题:增广路径算法的比较  这篇文章我们将重温最大流问题,实现一些最有名的增广路径算法的实际分析的目标。我们将讨论的这几种算法的复杂度在O(n*m*m)到O(n*mlogU)之间,并且从讨论的结果中得到在实践中...
  • 网络最大流问题是网络的另一个基本问题。许多系统包含了流量问题。例如交通系统有车流量,金融系统有现金流,控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 545,427
精华内容 218,170
关键字:

最大流问题