Corrispondenza bipartite
https://stackoverflow.com/questions/878668
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Come posso implementare un algoritmo di matching bipartita (probabilmente sulla base di un algoritmo di max-flow) in C o C ++?
Per essere precisi, ho questo ingresso in un file: (1,3) (1,5) (2,5)
(M, F) -.> Dove M rappresenta id del maschio e F è id FEMMINA
Ho bisogno di trovare il numero massimo di partite e show abbinato coppie. Piace: gli incontri: 1 e 3, 2 e 5
Ho letto in alcuni libri posso basare questo problema su un "flusso massimo in una rete di" algoritmo, ma non sono riuscito a trovare alcuna info specifica diversa la frase "questo problema può essere risolto .... algoritmo ". Ho poca conoscenza di max-flow, e non so come implementarlo o ...
Soluzione
Sì, corrispondente bipartito può essere ridotto ad un massimo di flusso:
-
Si è dato set di nodi
MeF. Aggiungere un bordo diretto da unmnodoMad unfnodoFse hai la coppia(m, f)nel file. -
Aggiungere un singolo
Snodo con un bordo diretto daSa ogni nodoM(questo è il nodo "super-source"). -
Aggiungere un singolo
Tnodo con un bordo diretto da ogni nodoFaT(questo è il tuo "super-sink" nodo). -
Ora, è necessario trovare il flusso massimo (con tutti i bordi del peso 1) dal
SaT.
Quindi, cosa diavolo è un flusso massimo? A flusso da S a T è un insieme di archi tale che per ogni nodo (tranne S e T), il peso del suo in-flux bordi è lo stesso del peso delle out-flux bordi. Immaginate che il grafico è una serie di tubi, e si sta versando l'acqua nel sistema a S e lasciando fuori a T. Ad ogni nodo tra, la quantità di acqua che va in deve essere uguale alla quantità di acqua che esce.
Prova a convincersi che un flusso corrisponde a un incontro tra il vostro set originali. (Dato un flusso, come si ottiene un abbinamento? Data una corrispondenza, come si ottiene un flusso?)
Infine, per trovare il massimo flusso in un grafico, è possibile utilizzare l'algoritmo Ford-Fulkerson . La pagina di Wikipedia di cui sopra dà una buona descrizione di esso, con pseudo-codice.
Altri suggerimenti
Sì, se si dispone già di codice per risolvere il problema max-flow, è possibile utilizzarlo per risolvere corrispondenza bipartita trasformando il grafico come mostrato verso la fine del questo conferenza, ma che probabilmente non è l'approccio giusto se si inizia da zero. Se si desidera solo per implementare un codice abbastanza semplice per risolvere il problema per gli esempi che non diventi troppo grande, si sta meglio con un approccio semplice percorso che aumenta come indicato qui . Che ti dà un O approccio che è abbastanza facile da codificare e adeguata per tutti, ma i grafici molto grandi (| | V || E). Se si desidera qualcosa con la migliore prestazione nel caso peggiore, si potrebbe provare la Hopcraft-Karp algoritmo, che trova molteplici cammini aumentanti in una sola volta e ha un O (sqrt (| V |) | e |) fase di esecuzione legato, ma l'articolo di Wikipedia su di esso osserva che:
Diversi autori hanno eseguito confronti sperimentali di bipartita corrispondenti algoritmi. I loro risultati in generale tendono a dimostrare che il Metodo Hopcroft-Karp non è buono in pratica in quanto è in teoria: è sovraperformato sia dai più semplici ampiezza e profondità prima strategie per la ricerca augmenting percorsi, e premendo un relabel tecniche.
In ogni caso, si dovrebbe assolutamente capire ed essere in grado di implementare un approccio semplice augmenting-percorso prima di tentare di affrontare sia Hopcraft-Karp o una delle tecniche innesto relable di cui i riferimenti alle voci di Wikipedia.
Modifica: Per qualche ragione, i link qui sopra non vengono visualizzati correttamente. Qui ci sono gli URL in questione: ( http: //oucsace.cs .ohiou.edu / ~ Razvan / corsi / cs404 / lecture21.pdf ), ( http://www.maths.lse.ac.uk/Courses/MA314/matching.pdf ), e ( http://en.wikipedia.org/wiki/Hopcroft -Karp_algorithm).
Il QuickGraph biblioteca comprende un algoritmo di matching bipartita, che ho appena lavorato e registrato una correzione per . Si avvolge l'algoritmo di flusso massimo Edmonds Karp.
L'unica documentazione per l'algoritmo finora è i test di unità che ho aggiunto. Se qualcuno volesse aggiungere un'implementazione (si spera più veloce), che non si limita a un algoritmo di avvolgere MaxFlow, si prega di contattare me.
Ecco uno studio sperimentale di algoritmi di flusso per la corrispondenza massima bipartito:
@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
}
Il vincitore è stato un algoritmo di push-rietichettatura, che a mio avviso è stata la realizzazione di pacchetti di Andrew Goldberg "BIM", che potete scaricare qui:
http://www.avglab.com/andrew/soft.html
Intendiamoci, se è importante che si codifica la soluzione da soli, si potrebbe desiderare di accontentarsi di Ford-Fulkerson, come suggerito Jesse. Se lo fai, vi consiglio di utilizzare in ampiezza prima ricerca, non in profondità di ricerca, per trovare il percorso che aumenta (per i motivi spiegati nell'articolo sopra).
#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();
}
