二分匹配

如何在C或C ++中实现二分匹配算法(可能基于最大流算法)?

具体来说,我把这个输入放在一个文件中:(1,3)(1,5)(2,5)

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

我需要找到最大匹配数并显示匹配的夫妻。 喜欢:匹配:1&3,2和5

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

是的,二分匹配可以减少到最大流量:

  1. 你得到了节点MF集合。 如果你的文件中有对(m, f) ,则从M的节点mF的节点f添加有向边。

  2. 将带有S有向边的单个节点S添加到M每个节点(这是您的“超级源”节点)。

  3. FT每个节点添加一个带有有向边的单个节点T (这是您的“超级宿”节点)。

  4. 现在,您需要找到从ST的最大流量(所有边缘的权重为1)。

那么最大的流量是什么呢? 从ST 是一组边缘,使得对于每个节点( ST除外),其磁通边缘的权重与其磁通边缘的权重相同。 想象一下,你的图表是一系列管道,你在S系统中倒水并在T处放出它。 在它们之间的每个节点,进入的水量必须与出水量相同。

尝试说服自己,流程对应于原始集合的匹配。 (给定流程,如何获得匹配?给定匹配,如何获得流量?)

最后,要在图表中找到最大流量,您可以使用Ford-Fulkerson算法 。 上面的维基百科页面用伪代码对它进行了很好的描述。

是的,如果您已经有代码来解决最大流量问题,您可以使用它来通过转换图形来解决二分匹配,如本演讲结束时所示,但如果您从头开始,这可能不是正确的方法。 如果你只是想实现一些相当简单的代码来解决问题而不是太大的例子,你最好使用这里概述的简单扩充路径方法。 这为您提供了一种O(| V || E |)方法,该方法非常容易编码,并且适用于所有非常大的图形。 如果你想要具有更好的最坏情况性能的东西,你可以尝试Hopcraft-Karp算法,它一次找到多个扩充路径并且具有O(sqrt(| V |)| E |)运行时限,但维基百科文章在它上面注意到:

一些作者已经进行了二分匹配算法的实验比较。 他们的结果总体上倾向于表明Hopcroft-Karp方法在实践中并不像理论上那样好:它通过更简单的广度优先和深度优先策略来寻找增强路径,并且通过推 – 重新技术技术表现得更好。 。

在任何情况下,在尝试解决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_algorithm)。

QuickGraph库包含一个二分匹配算法,我刚刚处理并检查了修复程序。 它包装了Edmonds Karp最大流量算法。

到目前为止,该算法的唯一文档是我添加的unit testing。 如果有人想添加一个(希望更快)实现,而不是简单地包装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 } 

获胜者是push-relabel算法,我认为这是Andrew Goldberg的“BIM”软件包的实现,你可以在这里下载:

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

请注意,如果您自己编写解决方案很重要,那么您可能希望像Jeffse所建议的那样选择Ford-Fulkerson。 如果你这样做,我建议你使用广度优先搜索而不是深度优先搜索来找到扩充路径(由于上面文章中解释的原因)。

 #include #include 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;xr[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][jn]; } if((i>m)&&(j<=n)) { f[i][j] = d2[im][j]; } if((i>m)&&(j>n)) { f[i][j] = am[im][jn]; } 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(); }