Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Максимальное паросочетание

Автор: Silent 21.2.2009, 21:42

Задача:
дан взвешенный граф, найти в нем паросочетание с максимальной суммой весов ребер

Насколько я понимаю, суть решения сводится к генерации всех остовных деревьев, построению на их основе паросочетаний и выделению из этого множества искомого? хочу услышать ваши идеи, может все гораздо проще?

Автор: maxdiver 21.2.2009, 23:50

Я так понимаю, имеется в виду, что в первую очередь надо максимизировать мощность паросочетания, во вторую его вес?

Тогда это алгоритм Эдмондса. Я, правда, разбирался недавно только с невзвешенным случаем (и реализацией за N^3), с ним могу помочь. Судя по книге Кристофидеса, алгоритм для взвешенного графа базируется на нём. Я не особо вчитывался, но думаю, что алгоритм примерно такой же, просто для нахождения увеличивающих цепей вместо обхода в ширину используется Дейкстра (хотя, возможно, я не прав).

Автор: Silent 23.2.2009, 23:13

Как раз то что доктор прописал, maxdiver, в самую точку
И еще буду ооочень благодарен если приведешь ссылочки на литературу, где про него рекомендуешь подробнее ознакомиться (я только поверхностно знаком), и, совсем уж для полного щастья - код

Автор: maxdiver 24.2.2009, 18:46

Ну по поводу невзвешенного паросочетания я много статей перерыл, ну и как обычно на свой сайт добавил smile

http://e-maxx.ru/algo/matching_edmonds
Там вся теория (пока бета-версия, док-ва ещё перепроверить надо) и проверенный на нескольких олимпиадных сайтах код.

Если литература, то описание есть в "Теория графов" Кристофидес, но его изложение мне не очень нравится, хотя суть алгоритма можно понять и по ней. Вроде неплохо описано в "Комбинаторная оптимизация" Пападимитриу. Но больше информации лично я почерпнул из статей: "Sketchy Notes on Edmonds’ Incredible Shrinking Blossom Algorithm for General Matching" Tarjan, "Edmonds’s Non-Bipartite Matching Algorithm" - лекции из унив. Berkeley, лекции "Matching Algorithms" Muller-Hannemann'а (которые судя по всему перепечатаны из книги Tarjan'а "Data structures and network algorithms" smile

), а также ещё из каких-то презентаций.

По поводу взвешенного случая - в Кристофидесе и Пападимитриу есть они, также должны быть ещё в каких-нибудь статьях, но я специально не искал этого.

Автор: aram90 27.2.2009, 20:27

Есть алгоритм, называется Венгерский Алгоритм (Hungarian Algorithm)

Также порекомендую эту ссылку, "Задача о назначениях"
http://vuz.exponenta.ru/PDF/MPEI/NAZN/naznach.html

Автор: maxdiver 27.2.2009, 23:32

aram90, вообще-то это только для двудольных графов пойдёт.

Для них, кстати, есть прекрасная реализация венгерского алгоритма за N^3, сделанная Андреем Лопатиным. Я думаю, в интернете можно найти. Если кому надо, могу и здесь выложить.

Но к задаче данного топика это слабо относится.