Венгерский алгоритм - это комбинаторный алгоритм оптимизации, который решает проблему согласования двудольных с максимальным весом за полиномиальное время и предвосхищает дальнейшее развитие важного первично-двойственного метода . Алгоритм был разработан и опубликован Гарольдом Куном в 1955 году, который дал название «Венгерский алгоритм», потому что алгоритм основан на более ранних работах двух венгерских математиков: Дениса Кенига и Йено Эгервари. Мункрес пересмотрел алгоритм в 1957 году и заметил, что это действительно время. С тех пор алгоритм также известен как алгоритм Куна-Мункреса.
Несмотря на то, что венгерский язык содержит основную идею метода прямого двойственного преобразования, он решает проблему согласования двудольных с максимальным весом напрямую, без использования какого-либо механизма линейного программирования (LP). Так, в ответ на следующий вопрос Юкка Суомела прокомментировал
Конечно, вы можете решить любой LP, используя универсальный LP-решатель, но специализированные алгоритмы обычно имеют гораздо лучшую производительность. [...] Вы также можете часто избегать проблем, таких как использование точных рациональных чисел и чисел с плавающей запятой; все можно легко сделать с помощью целых чисел.
Другими словами, вам не нужно беспокоиться о том, как округлить рациональное / с плавающей запятой решение из решателя LP, чтобы получить максимальное идеальное соответствие веса для данного двудольного графа.
Мой вопрос заключается в следующем:
Существует ли обобщение венгерского алгоритма, который работает для общего неориентированного графа без использования механизма LP, аналогично духу оригинального венгерского алгоритма?
Я бы предпочел современную и удобную для чтения экспозицию вместо оригинальной сложной бумаги. Но любой указатель будет очень признателен!
Большое спасибо заранее и счастливого Рождества !!!
Обновление: вопрос хорошо ответил Арманом ниже. Я просто хочу отметить, что еще одним хорошим источником для изучения алгоритма цветения Эдмондса (для взвешенного случая) является глава 11 « Комбинаторная оптимизация » Кортэ и Выгена . Книга Google на самом деле показывает почти все части, которые мне нужны, чтобы понять алгоритм.
Ответы:
Алгоритм сопоставления Эдмондса (также называемый Алгоритмом Блоссом) решает максимальное сопоставление на общих графах. На самом деле это обобщение метода переменных путей. (Я не уверен в названии метода, но это должен быть метод Кенига-Холла.) Он в основном находит пути расширения (см. Страницу википедии: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm ), чтобы расширить текущее соответствие и останавливается, если нет больше путей расширения. В общих графах единственная проблема возникает в нечетных циклах. В алгоритме сравнения Эдмондса нечетные циклы сжимаются (расцветают) и расходуются обратно, чтобы найти решение.
Существует также соответствие между алгоритмом Blossom и методом Primal Dual. Нечетные циклы вызывают дробные крайние точки. Поэтому мы добавляем так называемые неравенства цветов для каждого нечетного цикла.
С этим подходом также можно справиться с задачами идеального соответствия с минимальным весом и максимальным весом.
Подробнее об алгоритме см. Http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf.
Математическая формулировка и соответствующий первично-двойной метод см. По адресу http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf.
источник
Два года назад, исследуя (невзвешенный) алгоритм цветения, я обнаружил два замечательных набора заметок: одну Тарьяна и одну Цвика. Они сделали невзвешенный случай довольно простым, и я смог реализовать его в Mathematica с помощью рекурсии. Это работает довольно хорошо.
Заметки, которые я нашел полезными
http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf и http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/ Тарьян-blossom.pdf
Они разбирают все это до очень простых терминов, которые позволяют мыслить рекурсивно, а затем, как уже отмечалось, программировать рекурсивно.
Я думаю, что все должно работать в взвешенном случае, который я пытаюсь реализовать сейчас.
источник