https://stackoverflow.com/questions/878668
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
如何在 C 或 C++ 中实现二分匹配算法（可能基于最大流算法）？
具体来说，我在文件中输入了以下内容：（1,3）（1,5）（2,5）
(M,F) --> 其中 M 代表 MALE 的 id，F 代表 FEMALE 的 id。
我需要找到最大匹配数并显示匹配的情侣。喜欢：火柴：1&3 , 2&5
我在一些书中读过，我可以将这个问题基于“网络中的最大流量”算法，但是除了“这个问题可以通过......解决”这句话之外，我找不到任何具体信息。算法”。我对 max-flow 知之甚少，也不知道如何实现它......
解决方案
是的，分配可以减少到最大流量：
你在给定的集结点
M和F.添加向边缘由一个节点m在M节点f在F如果你有一对(m, f)在你的文件。添加一个单独的节点
S与针对边缘由S每个节点M(这是你的"超级源"节点)。添加一个单独的节点
T与针对边缘从中每个节点F要T(这是你的"超级散"节点)。现在，你需要找到的最大流量(与所有你的边缘重量的1)
S要T.
那么到底是最大的流动？一个 流 从 S 要 T 是一个设定的边缘，使得为每个节点(除了 S 和 T)，其重量的 在通 边缘相同重量的 出通量 的边缘。想象一下，你的曲线图是一系列的管道，和你在倒水的系统 S 并让它在 T.中的每一个环节之间，水量将在有相同的水量出来。
试图说服自己这一流动对应一个匹配的你的原始的集合。(给出一个流动，如何你会得到一匹配？给予一个配套，怎么你会得到一流?)
最后，找到最大的流量在一个曲线图，可以使用 福特-Fulkerson算法.上述维基百科网页提供了一个很好的描述，与伪码。
其他提示
是的，如果您已经有解决最大流问题的代码，您可以使用它通过转换图形来解决二分匹配，如接近末尾所示 这 讲座，但如果您从头开始，这可能不是正确的方法。如果您只想实现一些相当简单的代码来解决不太庞大的示例问题，那么最好使用概述的简单增强路径方法 这里. 。这为您提供了一种 O(|V||E|) 方法，该方法非常容易编码，并且适用于除非常大的图形以外的所有图形。如果您想要具有更好的最坏情况性能的东西，您可以尝试 霍普克拉夫特-卡普 算法，它一次找到多个增广路径，并且具有 O(sqrt(|V|)|E|) 运行时间限制，但维基百科文章指出：
几位作者对匹配算法进行了实验比较。他们的结果一般而言倾向于表明，霍普罗夫特 - 凯普方法在实践中不如理论上好：它的表现优于更简单的广度优先和深度优先的策略，用于寻找增强路径，也可以通过推送标签技术来表现。
无论如何，在尝试解决 Hopcraft-Karp 或维基百科文章参考文献中提到的推送相关技术之一之前，您绝对应该理解并能够实现简单的增强路径方法。
编辑：由于某种原因，上面的链接无法正确显示。以下是有问题的 URL：（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_算法）。
在 QuickGraph 库包括二分匹配算法，这是我刚制作和在修复检查。它包装埃德蒙兹卡普最大流量算法。
该算法的唯一文档到目前为止我添加单元测试。如果有人想加一个（希望更快）的实施不只是裹maxflow算法，请与我联系。
下面是流的算法，最大二分匹配的实验研究：
@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
}
获胜的是一个推重标记算法，我相信是从安德鲁·戈德堡的“BIM”包，你可以从这里下载的实现：
http://www.avglab.com/andrew/soft.html
你，如果是你自己编写了该解决方案是非常重要的，你可能要解决的福特Fulkerson增，杰西建议心灵。如果你这样做，我建议你使用广度优先搜索，而不是深度优先搜索，找到增广路径（原因在文章中解释以上）。
#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();
}
