Двудольное Сопоставление
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 представляет идентификатор МУЖЧИНЫ, а F - идентификатор ЖЕНЩИНЫ.
Мне нужно найти максимальное количество совпадений и показать совпадающие пары.Нравится:Матчи:1&3 , 2&5
Я читал в некоторых книгах, что могу основать эту проблему на алгоритме "максимального потока в сети", но я не смог найти никакой конкретной информации, кроме предложения "эта проблема может быть решена с помощью ....алгоритм".У меня мало знаний о max-flow, и я также не знаю, как это реализовать...
Решение
Да, двудольное сопоставление может быть сведено к максимальному потоку:
Вам даны наборы узлов
MиF.Добавьте направленное ребро из узлаmвMк узлуfвFесли у вас есть пара(m, f)в вашем досье.Добавьте один узел
Sс направленным краем отSк каждому узлу вM(это ваш узел "суперисточника").Добавьте один узел
Tс направленным ребром от каждого узла вFДляT(это ваш узел "супер-приемника").Теперь вам нужно найти максимальный поток (со всеми вашими ребрами веса 1) из
SДляT.
Так что же, черт возьми, такое максимальный поток?A поток От S Для T представляет собой набор ребер , такой, что для каждого узла (за исключением S и T), вес его в постоянном движении ребер совпадает с весом его выходной поток края.Представьте, что ваш график представляет собой ряд труб, и вы заливаете воду в систему в S и выпуская это наружу в T.В каждом промежуточном узле количество поступающей воды должно быть таким же, как и количество выходящей.
Попытайтесь убедить себя, что поток соответствует совпадению ваших исходных наборов.(Учитывая поток, как вам получить соответствие?Учитывая соответствие, как вам получить поток?)
Наконец, чтобы найти максимальный поток на графике, вы можете использовать Алгоритм Форда-Фулкерсона.Приведенная выше страница википедии дает хорошее описание этого с псевдокодом.
Другие советы
Да, если у вас уже есть код для решения задачи максимального потока, вы можете использовать его для решения двудольного сопоставления путем преобразования графика, как показано в конце это лекция, но это, вероятно, неправильный подход, если вы начинаете с нуля.Если вы просто хотите реализовать какой-нибудь довольно простой код для решения проблемы для примеров, которые не становятся слишком большими, вам лучше использовать простой подход к расширению пути, как описано выше здесь.Это дает вам подход O (| V ||E |), который довольно прост в кодировании и подходит для всех, кроме очень больших графиков.Если вам нужно что-то с лучшей производительностью в наихудшем случае, вы могли бы попробовать Хопкрафт-Карп алгоритм, который находит сразу несколько путей расширения и имеет ограничение по времени выполнения O (sqrt (|V |) | E |), но в статье Википедии о нем отмечается, что:
Несколько авторов выполнили экспериментальные сравнения двудольных алгоритмов сопоставления.Их результаты в в целом, как правило, показывают, что Метод Хопкрофта–Карпа не так хорош на практике, как в теории:он превосходит как более простой ориентированный в первую очередь на ширину, так и на глубину стратегии поиска расширяющих путей, так и методы повторной маркировки .
В любом случае, вы определенно должны понимать и уметь реализовать простой подход с расширением пути, прежде чем пытаться использовать Hopcraft-Karp или один из методов, связанных с нажатием, упомянутых в ссылках на статью в Википедии.
Редактировать:По какой-то причине приведенные выше ссылки отображаются некорректно.Вот URL-адреса, о которых идет речь:(http://oucsace.cs.ohiou.edu /~razvan/курсы/cs404/лекция21.pdf), (http://www.maths.lse.ac.uk/Courses/MA314/matching.pdf), и (http://en.wikipedia.org/wiki/Hopcroft–Karp_algorithm).
В Краткий график библиотека включает двудольный алгоритм сопоставления, над которым я только что поработал и проверил исправление.Он обертывает алгоритм максимального потока Эдмондса Карпа.
Единственная документация по алгоритму на данный момент - это модульные тесты, которые я добавил.Если кто-нибудь хотел бы добавить (надеюсь, более быструю) реализацию, которая не просто оборачивает алгоритм 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, который, как я полагаю, был реализацией из пакета "BIM" Эндрю Голдберга, который вы можете скачать здесь:
http://www.avglab.com/andrew/soft.html
Имейте в виду, если вам важно самостоятельно разработать решение, возможно, вы захотите остановиться на Ford-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();
}
