小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. 正文

算法笔记之线性规划网络流问题(3)

2019年3月8日 945点热度 0人点赞 0条评论

优化扩展——重贴标签算法ISAP

首先对所有的结点标记到汇点的最短距离,称之为高度。标高从汇点开始,用BFS方式,汇点的邻接点高度为1,继续访问的结点高度是2,一直到源点结束。

贴好标签之后,就可以从源点开始,沿着高度h(u)=h(v)+1且具有可行邻接边(cap>flow)的方向前进。我们找到了1-2-4-6。

我们再次从源点开始搜索,沿着高度h(u)=h(v)+1且具有可行邻接边(cap>flow)的方向前进,h(1)=3,h(2)=2,走到这里无法走到4号结点,因为没有邻接边,3号结点不近没有邻接边,而且高度也不满足条件,也不能走到1号结点,怎么办呢?

可以用重贴标签的方法。当前结点无法前进时,令当前结点的高度=所有邻接点高度的最小值+1;如果没有邻接边,则令当前结点的高度=结点数;退回一步,重新搜索。

算法设计

  1. 确定合适的数据结构。采用邻接表存储网络。
  2. 对网络结点贴标签,即标高操作。
  3. 如果源点的高度≥结点数,则转向第6步;否则从源点开始,沿着高度h(u)=h(v)+1且具有可行邻接边(cap>flow)的方向前进,如果到达汇点,则转向第4步;如果无法进行,则第5步。
  4. 增流操作:沿着找到的可增广路同向边增流,反向边减流。注意:在原网络上操作。
  5. 重贴标签:如果拥有当前结点高度的结点只有一个,转向第6步;令当前结点的高度=所有邻接点高度的最小值+1;如果没有邻接边,则令当前结点的高度=结点数;退回一步;转向第3步。
  6. 算法结束,已经找到最大流。

算法实现

const int inf = 0x3fffffff;
const int N=100;
const int M=10000;
int top;
int h[N], pre[N], g[N];

struct Vertex
{
   int first;
}V[N];
struct Edge
{
   int v, next;
   int cap, flow;
}E[M];
void init()
{
    memset(V, -1, sizeof(V));
    top = 0;
}
void add_edge(int u, int v, int c)
{
    E[top].v = v;
    E[top].cap = c;
    E[top].flow = 0;
    E[top].next = V[u].first;
    V[u].first = top++;
}
void add(int u,int v, int c)
{
    add_edge(u,v,c);
    add_edge(v,u,0);
}
void set_h(int t,int n)
{
    queue<int> Q;
    memset(h, -1, sizeof(h));
    memset(g, 0, sizeof(g));
    h[t] = 0;
    Q.push(t);
    while(!Q.empty())
    {
       int v = Q.front(); Q.pop();
       ++g[h[v]];
       for(int i = V[v].first; ~i; i = E[i].next)
       {
          int u = E[i].v;
          if(h[u] == -1)
          {
             h[u] = h[v] + 1;
             Q.push(u);
           }
        }
    }
    cout<<"初始化高度"<<endl;
    cout<<"h[ ]=";
    for(int i=1;i<=n;i++)
       cout<<"  "<<h[i];
    cout<<endl;
}
int Isap(int s, int t,int n)
{
    set_h(t,n);
    int ans=0, u=s;
    int d;
    while(h[s]<n)
    {
        int i=V[u].first;
        if(u==s)
           d=inf;
        for(; ~i; i=E[i].next)
        {
           int v=E[i].v;
           if(E[i].cap>E[i].flow && h[u]==h[v]+1)
           {
                u=v;
                pre[v]=i;
                d=min(d, E[i].cap-E[i].flow);
                if(u==t)
                {
                   cout<<endl;
                   cout<<"增广路径:"<<t;
                   while(u!=s)
                   {
                       int j=pre[u];
                       E[j].flow+=d;
                       E[j^1].flow-=d;
                       u=E[j^1].v;
                       cout<<"--"<<u;
                   }
                   cout<<"增流:"<<d<<endl;
                   ans+=d;
                   d=inf;
                }
                break;
            }
        }
        if(i==-1)
        {
           if(--g[h[u]]==0)
              break;
           int hmin=n-1;
           //cur[u]=V[u].first;
           for(int j=V[u].first; ~j; j=E[j].next)
              if(E[j].cap>E[j].flow)
                 hmin=min(hmin, h[E[j].v]);
           h[u]=hmin+1;
           cout<<"重贴标签后高度"<<endl;
           cout<<"h[ ]=";
           for(int i=1;i<=n;i++)
              cout<<"  "<<h[i];
           cout<<endl;
           ++g[h[u]];
           if(u!=s)
              u=E[pre[u]^1].v;
        }
    }
    return ans;
}
void printg(int n)//输出网络邻接表
{
   cout<<"----------网络邻接表如下:----------"<<endl;
   for(int i=1;i<=n;i++)
   {
       cout<<"v"<<i<<"  ["<<V[i].first;
       for(int j=V[i].first;~j;j=E[j].next)
           cout<<"]--["<<E[j].v<<"   "<<E[j].cap<<"   "<<E[j].flow<<"   "<<E[j].next;
       cout<<"]"<<endl;

   }

}
void printflow(int n)//输出实流边
{
   cout<<"----------实流边如下:----------"<<endl;
   for(int i=1;i<=n;i++)
     for(int j=V[i].first;~j;j=E[j].next)
        if(E[j].flow>0)
        {
           cout<<"v"<<i<<"--"<<"v"<<E[j].v<<"   "<<E[j].flow;
           cout<<endl;
        }
}

算法复杂度分析
时间复杂度:找到一条可增广路时间为O(V),最多会执行O(VE)次,因为关键边的总数为O(VE),因此总的时间复杂度为O(V2E),其中V为结点个数,E为边的数量。

空间复杂度O(V)。

最小费用路算法——最小费用最大流

问题分析

除了流量之外,还定义了一个单位流量的费用。对于网络上的一个流flow,其费用为

$\cos t(flow)=\sum\limits_{<x,y>\in E}{\cos t(x,y)*flow(x,y)}$

网络流的费用=单位流量费用*每条边的流量

算法设计

有两种思路:
1. 先找最小费用路,在该路径上增流,增加到最大流,称为最小费用路算法。
2. 先找最大流,然后找负费用圈,消减费用,减少到最小费用,称为消圈算法。
最小费用路算法,是在残余网络上寻找从源点到汇点的最小费用路,即从源点到汇点的以单位费用为权的最短路,然后沿着最小费用路增流,直到找不到最小费用路为止。

算法解释

  1. 创建混合网络。先初始化为零流,零流对应混合网络中,正向边容量为cap,流量为0,费用为cost,反向边容量为0,流量为0,费用为-cost。
  2. 找最小费用路。先初始化每个结点的距离为无穷大,然后令源点的距离dist[v1]=0。在混合网络中,从源点出发,沿可行边(E[i].cap>E[i].flow)广度搜索每个邻接点,如果当前距离dist[v]>dist[u]+E[i].cost,则更新为最短距离:dist[v]=dist[u]+E[i].cost,并记录前驱。根据前驱数组,找到一条最短费用路,增广路经:1-2-5-6。
  3. 然后沿着增广路经正向增流d,反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow),增流量d=3,产生费用为mincost+=dist[v6]d=83=24。
  4. 找最小费用路。先初始化每个结点距离为无穷大,然后令源点的距离dist[v1]=0。在混合网络中,从源点出发,沿可行边(E[i].cap>E[i].flow)广度搜索每个邻接点,如果当前距离dist[v]>dist[u]+E[i].cost,则更新为最短距离:dist[v]=dist[u]+E[i].cost,并记录前驱。根据前驱数组,找到一条最短费用路,增广路经:1-3-4-6。
  5. 然后沿着增广路经正向增流d,反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow),增流量d=4,产生费用为mincost+=24+dist[v6]d=24+164=88。
  6. 找最小费用路。先初始化每个结点距离为无穷大,然后令源点的距离dist[v1]=0。在混合网络中,从源点出发,沿可行边(E[i].cap>E[i].flow)广度搜索每个邻接点,发现从源点出发已经没有可行边,结束,得到的网络流就是最小费用最大流。把混合网络中flow>0的边输出,就是我们要的实流网络。

代码实现

(1)定义结构体。结构体的定义与ISAP中结构体相同,边只是多了一个cost域,fisrt指向第一个邻接边,next是吓一跳邻接边,该结构体用于创建邻接表。

   struct Vertex
{
   int first;
}V[N];
struct Edge
{
   int v, next;
   int cap, flow,cost;
}E[M];

(2)创建残余网络边。正向边的容量为cap,流量为0,费用为cost,反向边容量为0,流量为0,费用为-cost。

void add_edge(int u, int v, int c,int cost)
{
    E[top].v = v;
    E[top].cap = c;
    E[top].flow = 0;
    E[top].cost = cost;
    E[top].next = V[u].first;
    V[u].first = top++;
}
void add(int u,int v, int c,int cost)
{
    add_edge(u,v,c,cost);
    add_edge(v,u,0,-cost);
}

(3)求最小费用路。先初始化每个结点距离无穷大,然后令源点的距离dist[v1]=0。在混合网络中,从源点出发,沿可行边(E[i].cap>E[i].flow)广度搜索每个邻接点,如果当前距离dist[v]>dist[u]+E[i].cost,则更新为最短距离:dist[v]=dist[u]+E[i].cost,并记录前驱。

bool SPFA(int s, int t, int n)//求最短费用路的SPFA
{
    int i, u, v;
    queue <int> qu; // 队列,STL实现
    memset(vis,false,sizeof(vis));//访问标记初始化
    memset(c,0,sizeof(c));   //入队次数初始化
    memset(pre,-1,sizeof(pre)); //前驱初始化
    for(i=1;i<=n;i++)
    {
        dist[i]=INF; //距离初始化
    }
    vis[s]=true; //顶点入队vis要做标记
    c[s]++;     //要统计顶点的入队次数
    dist[s]=0;
    qu.push(s);
    while(!qu.empty())
    {
        u=qu.front();
        qu.pop();
        vis[u]=false;
        //队头元素出队,并且消除标记
        for(i=V[u].first; i!=-1; i=E[i].next)//遍历顶点u的邻接表
        {
            v=E[i].v;
            if(E[i].cap>E[i].flow && dist[v]>dist[u]+E[i].cost)//松弛操作
            {
                dist[v]=dist[u]+E[i].cost;
                pre[v]=i; //记录前驱
                if(!vis[v]) //顶点v不在队内
                {
                    c[v]++;
                    qu.push(v);   //入队
                    vis[v]=true; //标记
                    if(c[v]>n) //超过入队上限,说明有负环
                        return false;
                }
            }
        }
    }
    cout<<"最短路数组"<<endl;
    cout<<"dist[ ]=";
    for(int i=1;i<=n;i++)
       cout<<"  "<<dist[i];
    cout<<endl;
    if(dist[t]==INF)
        return false; //如果距离为INF,说明无法到达,返回false
    return true;
}

(4)沿着最小费用路增流。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow)。沿着增广路径正向边增流d,反向边减流d,产生费用为mincost+=dist[t]*d。

int MCMF(int s,int t,int n) //minCostMaxFlow
{
    int d; //可增流量
    int i,mincost;//maxflow 当前最大流量,mincost当前最小费用
    mincost=0;
    while(SPFA(s,t,n))//表示找到了从s到t的最短路
    {
        d=INF;
        cout<<endl;
        cout<<"增广路径:"<<t;
        for(i=pre[t]; i!=-1; i=pre[E[i^1].v])
        {
            d=min(d, E[i].cap-E[i].flow); //找最小可增流量
            cout<<"--"<<E[i^1].v;
        }
        cout<<"增流:"<<d<<endl;
        cout<<endl;
        maxflow+=d; //更新最大流
        for(i=pre[t]; i!=-1; i=pre[E[i^1].v])//修改残余网络,增加增广路上相应弧的容量,并减少其反向边容量
        {
            E[i].flow+=d;
            E[i^1].flow-=d;
        }
        mincost+=dist[t]*d; //dist[t]为该路径上单位流量费用之和 ,最小费用更新
   }
    return mincost;
}

复杂度分析

  1. 时间复杂度:找到一条可增广路时间为O(E),最多会执行O(VE)次,因为关键边的总数为O(VE),因此总的时间复杂度为O(VE2),其中V为结点个数,E为边的数量。
  2. 空间复杂度:O(V)。

消圈算法

算法设计
三个过程:

  1. 找给定网络的最大流。
  2. 在最大流对应的混合网络找负费用圈。
  3. 消负费用圈:负费用圈同方向的边流量加d,反方向的边流量减d。d为负费用圈所有边的最小可增量cap-flow。

算法的核心是在残余网络中找负费用圈。

算法解释

  1. 求最大流。用最大流求解算法求解最大流。
  2. 在最大流对应的混合网络中找负费用圈。在最大流的混合网络中,沿着cap>flow的边找负费用圈,就是各边费用之和为负的圈。
  3. 负费用圈同方向的边流量加d,反方向的边流量减d。沿找到的负费用全增流,其增量为组成负费用圈的所有边的最小可增量cap-flow。负费用圈说明费用较高,可以对费用为负的边减流,因为该残余网络为特殊的残余网络,负费用的边流量也是负值,减流实际上需要加上增流量d,为了维持平衡性,负费用圈同方向的边流量加d,反方向的边流量减d。
  4. 在混合网络中继续找负费用圈。在混合网络中,沿着cap>flow的边找负费用圈,已经找不到负费用圈,算法结束。把混合网络中flow>0的边输出,就是我们需要的实流网络。

复杂度分析

  1. 时间复杂度:最大流方法为O(V2E),如果每次消去负费用圈至少使费用下降一个单位,最多执行ECM此找负费用圈和增减流操作(C为每条边费用上界,M为每条边容量上界)。该算法时间复杂度为O(V2E2CM)。
  2. 空间复杂度O(V)。
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 算法 线性规划 网络流
最后更新:2019年3月8日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
C++ Primer Plus(第五版)第9章编程题答案 Andrew Ng深度学习作业1:线性回归 Java语言程序设计【学堂在线】编程作业(第二章) 《新少林寺》观后感 新青年报[New Youth]第四期发布! 2010 S.V Beijing Travel Ready:财政问题
标签聚合
鸟哥的linux私房菜 linux leetcode 高中 Java python学习 学习 算法 Python 生活
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号