Американские горки — поиск наибольшего паросочетания в двудольном графе
Привет, Хаброжители!
У нас есть три гипотезы:
- Алгоритмы не должны быть чрезвычайно сложными для понимания!
- Алгоритмы не скучны и не бесполезны!
- Интересные книги про алгоритмы могут быть и с примерами кода на Си!
И «Алгоритмы? Аха!» подтверждает наши предположения на своём примере. Увлекательная книга, которая доступно и на ярких примерах объясняет самые актуальные алгоритмы, а примеры написаны на Си, но пусть вас это не пугает.
Посмотрите сами как выглядит страшный «Поиск наибольшего паросочетания в двудольном графе»
Сеня отправился с друзьями в парк аттракционов и наконец-то может покататься на американских горках. В вагончике несколько рядов сидений по два места в каждом. В целях безопасности девочка должна сидеть в одном ряду с мальчиком. Однако каждый хочет сидеть с тем, кого знает. Если девочка и мальчик знакомы, они могут сидеть рядом. Требуется организовать рассадку так, чтобы максимальное число детей были ею довольны.
Начнем с моделирования задачи. На схеме выше вершины графа слева обозначают девочек, а вершины справа — мальчиков. Если между вершинами есть ребра, значит, они могут сидеть вместе. Такой граф называется двудольным (заметим, что двудольные графы являются неориентированными). Граф считается двудольным, если все его вершины можно разделить на два множества, X и Y, а все ребра имеют две вершины, одна из которых принадлежит множеству X, а другая — множеству Y, то есть вершины внутри множеств не соединены ребрами. Связи в приведенном примере можно разделить на две схемы:
Очевидно, что схема справа позволяет найти лучшее решение. Теперь задача превращается в поиск наибольшего паросочетания в двудольном графе. Самый простой способ решить ее — это перебрать все варианты и вывести тот, при котором получается наибольшее количество сочетаний пар. Временная сложность такого подхода очень высока. Может быть, есть лучший способ?
Начнем решать. Слева находится девочка 1, ее ставят в пару с мальчиком 1, девочку 2 — в пару с мальчиком 2. В этот момент мы обнаруживаем, что девочка 3 может быть в паре только с мальчиком 1, но мы уже поставили его в пару девочке 1… Так что же делать, переделывать все под желания девочки 3? Любители американских горок так просто не сдаются.
Когда девочка 3 подошла к мальчику 1, он все понял и сказал: «Я уже согласился сидеть с девочкой 1, подожди немного, я узнаю, может ли она сидеть с другими мальчиками. Если она найдет других знакомых, то я сяду с тобой».
Далее девочка 1 пробует найти другого знакомого мальчика. Она подходит к мальчику 2 и спрашивает: «Можно я сяду с тобой?» Мальчик 2 отвечает: «Я только что согласился сесть с девочкой 2, подожди минутку, я попрошу ее найти другого знакомого мальчика».
Теперь девочка 2 отправляется на поиски другого знакомого мальчика. Она подходит к мальчику 3 и спрашивает: «Можно я сяду с тобой?» Мальчик 3 отвечает: «Я свободен, конечно, можно!» Тогда девочка 2 снова поворачивается к мальчику 2 и говорит: «Я сяду с другим». Мальчик 2 говорит девочке 1: «Теперь я могу сидеть с тобой». Затем девочка 1 говорит мальчику 1: «Я нашла другого знакомого мальчика». Наконец, мальчик 1 отвечает девочке 3: «Я могу сесть с тобой».
Напоминает цепную реакцию, не правда ли? Но в итоге число довольных пар изменилось от первоначальных двух до трех, то есть увеличилось на 1. Такой процесс называют построением максимального потока.
Построение максимального потока имеет своей целью определение наибольшего паросочетания. Когда мы нашли некоторую схему, как определить, что она является наилучшей? Если мы не можем увеличить поток при текущей схеме, значит, она оптимальна. Алгоритм включает следующие шаги:
- Начиная с любой непарной вершины u, выбираем одно из ее ребер (предположим, что это ребро u → v) и создаем пару. Если вершина v еще не имеет пары, то переходим к следующей точке. Если вершина v уже имеет пару, то пробуем провести «цепную реакцию». Если эта попытка успешна, значит, построен максимальный поток. Здесь необходимо использовать массив match для записи пар. Например, если вершина v соединена с вершиной u, то это записывается как match[v] = u. При успешном сочетании не забудем увеличить на 1 число пар. Для процесса сочетания можно использовать поиск в глубину или ширину.
- Если сочетание выбранного ребра не удалось, то повторим попытку, выбрав другое ребро вершины u. Повторяем эту операцию до тех пор, пока u не будет успешно соединена или пока не будут перебраны все ее ребра.
- Далее продолжаем искать сочетания для оставшихся вершин, пока все они не будут перебраны.
- Выводим количество найденных пар.
Остается только доказать правильность этого метода, и это несложно — подумайте сами. Код выглядит так:
int e[101][101];
int match[101];
int book[101];
int n,m;
int dfs(int u)
{
int i;
for (i=1; i<=n; i++)
{
if (book[i] == 0 && e[u][i] == 1)
{
book[i] = 1; // отмечаем точку i как посещенную
// если точка i не соединена или найдено новое сочетание
if ( match[i] == 0 || dfs(match[i]) )
{
// обновляем пары
match[i] = u;
return 1;
}
}
}
return 0;
}
int main()
{
int i, j, t1, t2, sum=0;
scanf("%d %d",&n,&m); // n точек m ребер
for (i=1; i<=m; i++) // считываем данные графа
{
scanf("%d%d", &t1, &t2);
e[t1][t2]=1;
}
for(i=1;i<=n;i++) match[i]=0;
for (i=1; i<=n; i++)
{
for(j=1;j<=n;j++) book[j]=0; // обнуляем маркеры последнего поиска
if (dfs(i)) sum++; // если пара найдена, увеличиваем
// их количество на 1
}
printf("%d", sum);
getchar(); getchar();
return 0;
}
Для проверки можно ввести приведенные ниже данные. Два числа в первой строке — n и m, n обозначает число возможных пар, а m — число связей. Следующие m строк, каждая из которых содержит числа u и v, указывают на допустимость связи (мальчик номер u может сидеть с девочкой номер v).
3 5
1 1
1 2
2 2
2 3
3 1
Результат прогона:
3
Если двудольный граф имеет n точек, то можно найти не более n/2 пар. Если в графе имеется m ребер, то время, затрачиваемое на поиск каждой пары путем однократного обхода всех ребер, равно m. Таким образом, общая временная сложность алгоритма равна O (NM).
Двудольные графы часто применяются в экономическом планировании, организации труда и т. д. Как определить, является ли граф двудольным? В некоторых случаях это не столь очевидно, как в приведенном выше примере. Однако выявить двудольный граф очень просто: покрасьте одну из вершин в красный цвет, а связанные с ней вершины — в синий. Если в результате все вершины окажутся окрашенными в один из этих цветов, значит, граф является двудольным.
Рассмотренный алгоритм называется «венгерский». В 1972 году его улучшил Джек Эдмондс. Самый же быстрый из существующих в настоящее время алгоритмов определения наибольшего паросочетания в двудольных графах был предложен Джоном Хопкрофтом. Тем, кто заинтересуется этой темой, рекомендую прочитать его статью An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs, SIAM, Journal on Computing, 1973.
Заинтересовал отрывок? Тогда переходите по ссылке и познакомьтесь с книгой «Алгоритмы? Аха!» поближе на нашем сайте!
