bipartite Matching
https://stackoverflow.com/questions/878668
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Como posso implementar um algoritmo de correspondência bipartite (provavelmente baseado em um algoritmo max-flow) em C ou C ++?
Para ser mais específico, eu tenho esta entrada em um arquivo: (1,3) (1,5) (2,5)
(H, F) -.> Em que M representa ID do macho e F é ID de FÊMEA
Eu preciso encontrar o número máximo de partidas e mostrar casais emparelhados. Gostar: jogos 1 e 3, 2 e 5
Eu li em alguns livros que eu posso basear esse problema em um "fluxo máximo em uma rede de" algoritmo, mas eu não poderia encontrar qualquer informação específica que não seja a frase "este problema pode ser resolvido por .... algoritmo ". Eu tenho pouco conhecimento sobre max-flow, e não sei como implementá-lo ou ...
Solução
Sim, correspondência bipartido pode ser reduzida a vazão máxima:
-
Você é dado conjuntos de nós
MeF. Adicionar uma aresta direcionada de ummnó naMa umfnó naFse você tem o(m, f)par no seu arquivo. -
Adicionar um único
Snó com uma borda dirigida a partirSpara cada nó noM(este é o nó "super-source"). -
Adicionar um único
Tnó com uma borda dirigida a partir de cada nó noFparaT(este é o seu "super-pia" nó). -
Agora, você precisa encontrar o fluxo máximo (com todas as suas bordas de peso 1) de
SparaT.
Então, o que o Parreira é o fluxo máximo? Um fluir de S para T é um conjunto de arestas de modo a que para cada nó (excepto S e T), o peso da sua em-fluxo arestas é o mesmo que o peso de seus out-fluxo bordas. Imagine que o seu gráfico é uma série de tubos, e você está derramando água no sistema de S e deixá-lo para fora em T. Em cada nó no meio, a quantidade de água que vai no tem que ser o mesmo que a quantidade de água que sai.
Tente se convencer de que a corresponde fluxo para uma correspondência de seus conjuntos originais. (Dado um fluxo, como você começa uma correspondência? Dada uma correspondência, como você obter um fluxo?)
Finalmente, para encontrar o fluxo máximo em um gráfico, você pode usar o algoritmo Ford-Fulkerson . A página wikipedia acima dá uma boa descrição do mesmo, com pseudo-código.
Outras dicas
Sim, se você já tiver código para resolver o problema de fluxo máximo, você pode usá-lo para resolver correspondência bipartite, transformando o gráfico como mostrado no final de esta palestra , mas que provavelmente não é a abordagem certa se você está começando do zero. Se você quiser apenas para implementar algum código bastante simples de resolver o problema para exemplos que não fique muito grande, você é melhor fora de usar uma abordagem caminho de aumento simples como delineado aqui . Que lhe dá uma O (| V || E |) abordagem que é muito fácil de código e adequada para todos, mas muito grandes gráficos. Se você quiser algo com melhor desempenho pior caso, você poderia tentar o Hopcraft-Karp algoritmo, que encontra vários caminhos aumentantes ao mesmo tempo e tem um o (sqrt (| V |) | e |) tempo de execução vinculada, mas o artigo da Wikipedia sobre ele observa que:
Vários autores têm realizado comparações experimentais de bipartido algoritmos relacionados. Seus resultados em geral tendem a mostrar que o método Hopcroft-Karp não é tão bom em praticar, pois é na teoria: é superou tanto pelo simples em largura e em profundidade estratégias para encontrar de aumento caminhos, e por impulso-relabel técnicas.
Em qualquer caso, você definitivamente deve compreender e ser capaz de implementar uma abordagem de aumento-caminho simples antes de tentar resolver qualquer Hopcraft-Karp ou uma das técnicas empurrar-relable mencionados nas referências do artigo da Wikipedia.
Edit: Por alguma razão, os links acima são não aparecendo corretamente. Aqui estão os URLs em questão: ( http: //oucsace.cs .ohiou.edu / ~ razvan / cursos / cs404 / lecture21.pdf ), ( http://www.maths.lse.ac.uk/Courses/MA314/matching.pdf ), e ( http://en.wikipedia.org/wiki/Hopcroft -Karp_algorithm).
O QuickGraph biblioteca inclui um algoritmo de correspondência bipartite, que eu só trabalhou em e check-in uma correção para . Ela envolve o algoritmo do fluxo máximo Edmonds Karp.
A única documentação para o algoritmo até agora é os testes de unidade I adicionados. Se alguém gostaria de adicionar uma implementação (espero mais rápido), que não se limita a embrulhar um algoritmo Maxflow, entre em contato comigo.
Aqui está um estudo experimental de algoritmos de fluxo para correspondência máxima bipartida:
@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
}
O vencedor foi um algoritmo de push-etiquetagem, que creio que foi a implementação do pacote de Andrew Goldberg "BIM", que você pode baixar aqui:
http://www.avglab.com/andrew/soft.html
Lembre-se, se é importante que você codificar-se a solução, você pode querer se contentar com Ford-Fulkerson, como Jesse sugeriu. Se você fizer isso, eu recomendo que você use em largura de busca, não em profundidade de pesquisa, para encontrar o caminho de aumento (por razões explicadas no artigo acima).
#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();
}
