第九讲  二分图匹配问题
一、问题
设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。
    给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)
如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先出全部匹配，然后保留匹配数最多的。即回溯法，但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。
二 、算法分析
    二分图的最大匹配有2种实现，网络流和匈牙利算法。
1.匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若边集合P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
2.由增广路径的定义可以推出下述三个结论：
（1）. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
（2）. P经过“取反操作”（即非M中的边变为M中的边，原来M中的边去掉）可以得到一个更大的匹配M’。
（3）. M为G的最大匹配当且仅当不存在相对于M的增广路径。
3.从而可以得到求解最大匹配的匈牙利算法：
(1)置M为空；
(2)出一条增广路径P，通过“取反操作”获得更大的匹配M’代替M；
(3)重复(2)操作直到不出增广路径为止；
根据该算法，可以选择深搜或者广搜实现，下面给出易于实现的深度优先搜索（DFS）实现。
三、实现
1.    匈牙利算法的算廓
 bool 寻从k出发的对应项出的可增广路{
while(j与k邻接){
        if(j不在增广路上){
            把j加入增广路;
            if(j是未盖点 或者 从j的对应项出发有可增广路)
                则从k的对应项出有可增广路,返回true;
            修改j的对应项为k;
        }
    }
    从k的对应项出没有可增广路,返回false;
}
2.    匈牙利算法流程
3.代码
int    n, m, match[100]; //二分图的两个集合分别含有n和m个元素,match[i]存储集合m中的节点i在集合n中的匹配节点,初值为-1。设当前匹配为M
bool    visited[100], map[100][100]; //map存储邻接矩阵
bool DFS(const int &k)
{
      for(int i = 0; i < m; i++)
          if( map[k][i] && !visited[i]    )
          {
              visited[i] = true;
            if( match[i] == -1 || DFS(match[i]) )  //寻是否为增广路径
        {
           match[i] = k;            //路径取反操作。如果match[i]=-1,表示m集合中定点i不在M中，
是增广路径；如果match[i]<>-1,由于DFS（match[i]）为true说明到了增广路径，将定点i在原来M中的边替换掉。（即实现异或操作）
          return true;
              }
          }
      return false;
}
void hungary()
{
        for(i = 0; i < n; i++)
      {    //以二分集中的较小集为n进行匹配较优
      memset(visited, 0,sizeof(visited));
      if( DFS(i) )    ++count;    //count为匹配数
      }
    输出 匹配数count;
}
int main(void)
{//...........
      int    count = 0;//统计寻最大匹配过程中增广路径的条数
      memset(match, -1, sizeof(match));//初始匹配M为空
      Hungary（）；//............
return 0;
}
四、实例：
map矩阵如下：
执行过程：
Hungary函数中第一次循环时，得到增广路径：n1----m1，也就是一个匹配
第二次循环时，得到增广路径：n2----m1----n1----m2,得到新匹配：n2—m1,n1—m2
第三次循环时，得到增光路径：n3—m2—n1—m1---n2----m3,得到新的匹配：n3---m2,n1---m1,n2-m3;
第四次循环时，不能得到增光路径，所以第三次得到的为最大匹配。
优点：实现简洁，容易理解，适用于边比较多的图，DFS增广路快.
练习1：完美的牛栏
农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。不幸的是，由于工程问题，每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。给出奶牛们的爱好的信息，计算最大分配方案。
INPUT FORMAT：
第一行  两个整数，N (0 <= N <= 200) 和 M (0 <= M <= 200) 。N 是农夫约翰的奶牛数量，M 是新牛棚的牛栏数量。
第二行到第N+1行  一共 N 行，每行对应一只奶牛。第一个数字 (Si) 是这头奶牛愿意在其中产奶的牛栏的数目 (0 <= Si <= M) 。后面的 Si 个数表示这些牛栏的编号。牛栏的编号限定在区间 (1..M) 中，在同一行，一个牛栏不会被列出两次。
SAMPLE INPUT (file stall4.in)
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

OUTPUT FORMAT：
只有一行。输出一个整数，表示最多能分配到的牛栏的数量。
SAMPLE OUTPUT (file stall4.out)
4
五、二分图最优匹配
     对于二分图的每条边都有一个权（非负），要求一种匹配方案，使得所有匹配边的权和最大，记做二分图的最优匹配。
二分图最优匹配的经典算法是由Kuhn和Munkres独立提出的KM算法，值得一提的是最初的KM算法是在1955年和1957年提出的，因此当时的KM算法是以矩阵为基础的，随着匈牙利算法被Edmonds提出之后，现有的KM算法利用匈牙利树可以得到更漂亮的实现。
    KM算法中的基本概念是可行顶标(feasible vertex labeling)，它是节点的实函数并且对于任意弧(x,y)满足l(x)+l(y)≥w(x,y)，此外一个概念是相等子图，它是G的一个生成子图，但是只包含满足l(xi)+l(yj)=w(xi,yj)的所有弧(xi,yj)。
  定理：如果相等子图有完美匹配，那么该匹配是最大权匹配，证明非常直观也非常简单，
反设其他匹配是最优匹配，它的权必然比相等子图的完美匹配的权要小。
    KM算法主要就是控制了怎样修改可行顶标的策略使得最终可以达到一个完美匹配，首先任意设置可行顶标（如每个X节点的可行顶标设为它出发的所有弧的最大权，Y节点的可行顶标设为0），然后在相等子图中寻增广路，到增广路就沿着增广路增广。
    而如果没有到增广路呢，那么就考虑所有现在在匈牙利树中的X节点（记为S集合），所有现在在匈牙利树中的Y节点（记为T集合），考察所有一端在S集合，一端在not T集合中的弧，取
    delta =  min {l(xi)+l(yj)-w(xi,yj),xi ∈ S, yj ∈ not T}
    明显的，当我们把所有S集合中的l(xi)减少delta之后，一定会有至少一条属于(S,not T)的边进入相等子图，进而可以继续扩展匈牙利树，为了保证原来属于(S,T)的边不退出相等子图，把所有在T集合中的点的可行顶标增加delta。
    随后匈牙利树继续扩展，如果新加入匈牙利树的Y节点是未盖点，那么到增广路，否则把该节点的对应的X匹配点加入匈牙利树继续尝试增广。
　Kuhn－Munkras算法流程：
  (1)初始化可行顶标的值 ；
  (2)用匈牙利算法寻完备匹配；
  (3)若未到完备匹配则修改可行顶标的值 ；
  (4)重复(2)(3)直到到相等子图的完备匹配为止 。
C代码：
const int N=110;
const int INF=999999999;
bool x[N],y[N];
int lx[N],ly[N],map[N][N],link[N],d,i,j,k,sum,n;
//lx[],ly[]  可行顶标，何谓“可行顶标”，即人为限制每次DFS各边应达到的权，当然要尽量大
//map[][]  边权
/
/link[]    标记y[]所连接的x[]
//sum      最大权和
bool dfs(int v)        //增广路径，看各边能否达到可行顶标，标记
 {
    int t;
    int temp;
    x[v]=true;
    for(t=1;t<=n;t++)
    {
        if(!y[t]&&lx[v]+ly[t]==map[v][t])
        {
            y[t]=true;
            temp=link[t];
            link[t]=v;
            if(temp==0||dfs(temp))
                return true;
            link[t]=temp;
        }
    }
    return false;
 }

int KM()
{
    fill(lx,lx+N,-INF);
    fill(ly,ly+N,0);
    fill(link,link+N,0);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
          lx[i]=max(lx[i],map[i][j]);  //初始化可行顶标，既是“人为”规定，当然应该越大越好
    for(i=1;i<=n;i++)                    //KM过程
        do{
            fill(x,x+N,false);
            fill(y,y+N,false);
            if(dfs(i))
sort of link                break;
            d=INF;
            for(j=1;j<=n;j++)
                if(x[j])
                    for(k=1;k<=n;k++)
                        if(!y[k])
                            d=min(d,lx[j]+ly[k]-map[j][k]);
            for(j=1;j<=n;j++)  //某些边无法匹配，说明“人为”规定的权太大，故减为比它小的最大权
            {
                if(x[j])
                    lx[j]-=d;
                if(y[j])
                    ly[j]+=d;
            }
        }while(1);
    sum=0;
    for(i=1;i<=n;i++)
        sum+=map[link[i]][i];
    return 0;
  }
 
 int main()
 {
    //此处读入map[][];
            KM();
 }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。