如何在 C 或 C++ 中实现二分匹配算法（可能基于最大流算法）？
具体来说，我在一个文件中有这个输入： (1,3) (1,5) (2,5)
(M,F) --> 其中 M 代表 MALE 的 id，F 是 FEMALE 的 id。
我需要找到最大匹配数并显示匹配的情侣。喜欢：匹配：1&3、2&5
我读过一些书，我可以将这个问题建立在“网络中的最大流量”算法上，但除了“这个问题可以通过......算法解决”这句话之外，我找不到任何具体信息。我对最大流量知之甚少，也不知道如何实现它......
Karani
问问题
6936 次
5 回答
6
是的，二分匹配可以减少到最大流量：
你得到了一组节点
M和F. 如果您的文件中有这对，则将一个有向边从一个节点添加m到M一个节点。fF(m, f)向其中的每个节点添加一个
S具有有向边的单个节点（这是您的“超级源”节点）。SMT从每个节点添加一个具有有向边的单个节点F到T（这是您的“超级接收器”节点）。现在，您需要找到从 到 的最大流量（所有边的权重为 1
S）T。
那么最大流量到底是什么？从到的流是一组边，使得对于每个节点（除了和），其流入边的权重与其流出边的权重相同。想象一下，您的图表是一系列管道，您将水倒入系统中并在 处放水。在中间的每个节点处，流入的水量必须与流出的水量相同。STSTST
试着说服自己一个流程对应于你的原始集合的匹配。（给定一个流，你如何得到一个匹配？给定一个匹配，你如何得到一个流？）
最后，要在图中找到最大流量，可以使用Ford-Fulkerson 算法。上面的维基百科页面用伪代码很好地描述了它。
于 2009-05-18T17:07:56.927 回答
3
是的，如果您已经有解决最大流问题的代码，您可以使用它来解决二分匹配问题，方法是按照本讲座末尾所示的方式转换图形，但如果您从头开始，这可能不是正确的方法。如果您只想实现一些相当简单的代码来解决不太庞大的示例问题，那么最好使用此处概述的简单扩充路径方法。这为您提供了一种 O(|V||E|) 方法，该方法非常容易编码，并且适用于除非常大的图形之外的所有图形。如果你想要在最坏情况下性能更好的东西，你可以试试Hopcraft-Karp算法，它一次找到多个增广路径并且具有 O(sqrt(|V|)|E|) 运行时间限制，但是关于它的 Wikipedia 文章指出：
几位作者已经对二分匹配算法进行了实验比较。他们的结果总体上倾向于表明，Hopcroft-Karp 方法在实践中不如理论上那么好：它在寻找增强路径的更简单的广度优先和深度优先策略以及推送重新标记技术方面都优于.
在任何情况下，在尝试解决 Hopcraft-Karp 或 Wikipedia 文章参考文献中提到的一种可推相关技术之前，您绝对应该理解并能够实现一种简单的增广路径方法。
编辑：由于某种原因，上面的链接没有正确显示。以下是有问题的网址：（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）。
于 2009-05-18T19:19:17.347 回答
1
QuickGraph库包括一个二分匹配算法，我刚刚研究并检查了一个修复程序。它包装了 Edmonds Karp 最大流量算法。
到目前为止，该算法的唯一文档是我添加的单元测试。如果有人想添加一个（希望更快）不简单地包装 maxflow 算法的实现，请与我联系。
于 2010-08-11T06:04:01.947 回答
0
这是最大二分匹配的流算法的实验研究：
@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
请注意，如果您自己编写解决方案很重要，那么您可能希望像 Jesse 建议的那样选择 Ford-Fulkerson。如果你这样做，我建议你使用广度优先搜索，而不是深度优先搜索，来查找增广路径（原因在上面的文章中解释过）。
于 2009-08-17T03:26:31.540 回答
-2
#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();
}
于 2017-11-21T06:40:16.873 回答