二分匹配

Question

如何在 C 或 C++ 中实现二分匹配算法（可能基于最大流算法）？

具体来说，我在文件中输入了以下内容： (1,3) (1,5) (2,5)

(M,F) --> 其中M代表MALE的id，F代表FEMALE的id。

我需要找到最大匹配数并显示匹配的情侣。 喜欢： 匹配： 1&3 , 2&5

我在一些书中读过，我可以将这个问题基于“网络中的最大流量”算法，但除了“这个问题可以解决”这句话之外，我找不到任何具体信息通过......算法”。 我对 max-flow 知之甚少，也不知道如何实现它......

Answer 1

#include<stdio.h> 
#include<conio.h> 


void main() 
{ 
    int m,n,x,y,i,j,i1,j1,maxvalue;
    float s[10][10] = {0,0};
    int s2[10][10] = {0,0};
    float f[20][20] = {0,0};
    float f1[20][20] = {0,0};
    float f2[20][20] = {0,0};

    printf("\nEnter Number of Jobs(rows) and Machines(columns) of Matrix:\n"); 
    scanf_s("%d%d",&m,&n); 
    printf("\nEnter the Pij elements of matrix:\n"); 
    for(x=1;x<m+1;++x)
        for(y=1;y<n+1;++y)
            scanf("%f", &s[x][y]);
    //Find sum of each row
    for(x=1;x<m+1;++x)
    {
        s[x][n+1]=0;
        for(y=1;y<n+1;++y)




s[x][n+1]=s[x][n+1]+s[x][y];

//Find sum of each column
    for(y=1;y<n+1;++y)
    {
        s[m+1][y]=0;
        for(x=1;x<m+1;++x)
            s[m+1][y]+=s[x][y];
    }
    printf("\nMatrix s, Row Sum (Last Column)   and Column Sum (Last Row) : \n");

    printf("\ns:\n");
    for(x=1;x<m+2;++x)
    {
        for(y=1;y<n+2;++y)
            printf(" %2.0f  " , s[x][y]);
        printf("\n");
    }
    //Print sum of each column
    /*x=n+1;
    for(y=1;y<m+1;++y)
    printf(" %2.0f  " , s[x][y]);*/
    printf("\n");

    maxvalue = s[1][1];
    for(x=1; x<m+2; ++x)
        for(y=1; y<n+2; ++y)
        {




if(maxvalue < s[x+1][y+1])
                maxvalue = s[x+1][y+1];
        }



        printf("\n");
        printf("maxvalue = %d" , maxvalue);

        printf("\nd1:\n");
        float d1[20][20] = {0,0};
        for(i=1;i<=m;++i)
        {
            for(j=1;j<=m;++j)
            {
                if(i==j)
                    d1[i][j] = maxvalue - s[i][n+1];
                printf(" %2.0f  " , d1[i][j]);
            }
            printf("\n");
        }

        printf("\nd2\n");
        float d2[20][20] = {0,0};
        for(i=1;i<=n;++i)
        {
            for(j=1;j<=n;++j)
            {
                if(i==j)
                    d2[i][j] = maxvalue - s[m+1][j];
                printf(" %2.0f  " , d2[i][j]);



            }
            printf("\n");
        }



//row diff:
        printf("\n\nRow diff:\n");
        float r[20]= {0};
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(i == j)
                {
                    r[i] = maxvalue - d2[i][j];
                    printf("%f ",r[i]);
                }
            }

            //col diff:
            printf("\n\nCol diff:\n");
            float c[20]= {0};
            for(i=1;i<=m;i++)
                for(j=1;j<=m;j++)
                {
                    if(i == j)
                    {
                        c[i] = maxvalue - d1[i][j];
                        printf("%f ",c[i]);
                    }




                }

                //assignment matrix:
                float am[20][20]={0}; 




                i=j=1; 
ITERATION1: 
                if((c[i]<r[j]) && i<=m && j<=n) 
                { 
                    am[j][i]=c[i]; 
                    r[j]=r[j]-c[i]; 
                    c[i]=0; 
                    i++; 
                } 
                else if((c[i]>r[j]) && i<=m && j<=n) 
                { 
                    am[j][i]=r[j]; 
                    c[i]=c[i]-r[j]; 
                    r[j]=0; 
                    j++; 
                } 
                else if((c[i]==r[j]) && i<=m && j<=n) 
                { 
                    am[j][i]=r[j]; 
                    c[i]=r[j]=0; 
                    i++;j++; 
                } 
                else 



                    goto END; 
                for(int z=0;z<=n;z++) 
                { 
                    if(c[z]==0) 
                        continue; 


                    else 
                        goto ITERATION1; 
                } 

                for(int b=0;b<=m;b++) 
                { 
                    if(r[b]==0) 
                        continue; 
                    else 
                        goto ITERATION1; 
                } 

END: 
                printf("\n\nASSIGNMENT MATRIX:\n"); 

                for(i=1;i<=n;i++) 
                { 
                    for(j=1;j<=m;j++) 
                    { 
                        printf(" %2.0f  ",am[i][j]); 
                    } 
                    printf("\n"); 
                } 




                printf("\n\nf:\n");
                for(i=1; i<(m+n)+1;++i)
                {
                    for(j=1;j<(m+n)+1;++j)
                    {
                        if((i<=m) && (j<=n))


                    {
                            f[i][j]=s[i][j];
                        }
                        if((i<=m)&&(j>n))
                        {
                            f[i][j] = d1[i][j-n];
                        }
                        if((i>m)&&(j<=n))
                        {
                            f[i][j] = d2[i-m][j];
                        }
                        if((i>m)&&(j>n))
                        {
                            f[i][j] = am[i-m][j-n];
                        }

                        printf(" %2.0f  " , f[i][j]);
                    }
                    printf("\n");
                }




                //printf("\n\nf1:\n");
                for(i=1; i<(m+n)+1;++i)
                {
                    for(j=1;j<(m+n)+1;++j)
                    {
                        f1[i][j]=f[i][j];

                        //printf(" %2.0f  " , f1[i][j]);


                }
                    //printf("\n");
                }


                int cnt = 0;
ITERATION2: 
                for(i=1; i<(m+n)+1;++i)
                {
                    for(j=1;j<(m+n)+1;++j)
                    {
                        f2[i][j] = -1;
                    }
                }

                for(i=1; i<(m+n)+1;++i)
                {
                    for(j=1;j<(m+n)+1;++j)
                    {



                        if(f1[i][j]!=0 && f2[i][j]!=0)
                        {
                            f2[i][j] = f1[i][j];
                            for(j1=j+1;j1<(m+n)+1;++j1)
                                f2[i][j1] = 0;
                            for(i1=i+1;i1<(m+n)+1;++i1)
                                f2[i1][j] = 0;
                        }
                    }
                }



                //printf("\n\nf2:\n");
                for(i=1; i<(m+n)+1;++i)
                {
                    for(j=1;j<(m+n)+1;++j)
                    {
                        if(f2[i][j] == -1)
                        {
                            f2[i][j] = 0;
                        }
                        //printf(" %2.0f  " , f2[i][j]);
                    }
                    //printf("\n");
                }

                //printf("\n\nf1:\n");
                for(i=1; i<(m+n)+1;++i)
                {
                    for(j=1;j<(m+n)+1;++j)



                    {
                        if(f2[i][j] != 0)
                        {
                            f1[i][j] = f1[i][j] - 1;
                        }
                        //printf(" %2.0f  " , f1[i][j]);
                    }
                    //printf("\n");
                }

                cnt++;


                printf("\nITERATION - %d", cnt);
                printf("\n\Gant Chart:\n");
                for(i=1; i<=m;++i)
                {
                    for(j=1;j<=n;++j)
                    {
                        if(f2[i][j] != 0)
                        {
                            s2[i][cnt] = j;
                            printf(" J%d -> M%d", i,j);
                        }
                    }
                    printf("\n");
                }

                int sum = 1;
                for(i=1; i<(m+n)+1;++i)
                {



                    for(j=1;j<(m+n)+1;++j)
                    {   
                        sum = sum + f1[i][j];
                    }
                }

                if(sum>1)
                    goto ITERATION2;
                else
                    goto END2;
END2:



                printf("\n\Final Gant Chart:\n");
                for(i=1; i<=m;++i)
                {
                    for(j=0;j<=cnt;++j)
                    {
                        if(j == 0 )
                            printf(" J%d -> ", i);
                        else
                        {
                            if(s2[i][j] !=0)
                                printf(" M%d ", s2[i][j]);
                            else
                                printf(" %2c ", ' ');
                        }
                    }
                    printf("\n");
                }



                getch();
}

Answer 2

以下是最大二分匹配的流算法的实验研究：

@article{cherkassky98,
   author = {Boris V. Cherkassky and Andrew V. Goldberg and Paul Martin and Joao C. Setubal and Jorge Stolfi},
   title = {Augment or Push:  A Computational Study of Bipartite Matching and Unit Capacity Flow Algorithms},
   journal = {Journal of Experimental Algorithmics},
   volume = 3,
   number = 8,
   year = 1998
}

获胜者是推送重新标记算法，我相信该算法是来自 Andrew Goldberg 的“BIM”包的实现，您可以在此处下载：

http://www.avglab.com/andrew/soft.html

请注意，如果编写代码很重要正如杰西建议的那样，您可能想选择福特-福克森。 如果您这样做，我建议您使用广度优先搜索，而不是深度优先搜索，来查找增广路径（原因在上面的文章中解释）。

Answer 3

QuickGraph 库包含一个二分匹配算法，我刚刚研究并检查了修复。 它封装了 Edmonds Karp 最大流算法。

到目前为止，该算法的唯一文档是我添加的单元测试。 如果有人想添加一个（希望更快的）实现，而不是简单地包装最大流算法，请与我联系。

Answer 4

是的，如果您已经有解决最大流问题的代码，您可以使用它通过转换图形来解决二分匹配，如 这个讲座，但如果您从头开始，这可能不是正确的方法。 如果您只想实现一些相当简单的代码来解决问题，但示例不会太大，那么最好使用简单的增强路径方法，如下所示 此处。 这为您提供了一种 O(|V||E|) 方法，该方法非常容易编码，并且适用于除非常大的图形之外的所有图形。 如果您想要具有更好的最坏情况性能的东西，您可以尝试 Hopcraft-Karp 算法，它一次找到多个增广路径，并且具有 O(sqrt(|V|)|E|) 运行时间限制，但维基百科上的文章指出：

多位作者曾表演过
两部分的实验比较
匹配算法。 他们的结果是
一般倾向于表明
Hopcroft-Karp 方法在以下方面的效果较差
理论上的实践：它是
比两者都更简单
广度优先和深度优先
寻找增强的策略
路径，并通过推送重新标记
技术。

无论如何，在尝试解决 Hopcraft-Karp 或维基百科文章参考文献中提到的推送相关技术之一之前，您绝对应该理解并能够实现简单的增强路径方法。

编辑：由于某种原因，上面的链接没有正确显示。 以下是有问题的网址：(http://oucsace.cs .ohiou.edu/~razvan/courses/cs404/lecture21.pdf), (http://www.maths.lse.ac.uk/Courses/MA314/matching.pdf），以及（http://en.wikipedia.org/wiki/Hopcroft–Karp_algorithm）。

Answer 5

是的，二分匹配可以减少到最大流量：

1. 您将获得一组节点 M 和 F。 如果您已经获得了从 M 中的节点 m 到 F 中的节点 f 的有向边，请添加一条有向边在您的文件中配对 (m, f)。

2. 添加一个节点S，其有向边从S到M中的每个节点（这是您的“超级源”节点）。

3. 添加一个节点 T，该节点具有从 F 中的每个节点到 T 的有向边（这是您的“超级接收器”节点） ）。

4. 现在，您需要找到从 S 到 T 的最大流量（所有边的权重均为 1）。

那么最大流量到底是多少呢？ 从 S 到 T 的流是一组边，使得对于每个节点（S 和 >T），其流入边的权重与其流出边的权重相同。 想象一下，您的图表是一系列管道，您将水从 S 处倒入系统，并在 T 处放出。 在其间的每个节点，流入的水量必须与流出的水量相同。

尝试让自己相信一个流程对应于您的原始集合的匹配。 （给定一个流量，如何获得匹配？给定一个匹配，如何获得流量？）

最后，要找到图中的最大流量，可以使用 福特-Fulkerson 算法。 上面的维基百科页面用伪代码对其进行了很好的描述。