Я пытаюсь решить следующую проблему, но мой алгоритм работает слишком медленно. Это потому, что я использую алгоритм Эдмондса-Карпа, чтобы найти максимальный поток что в применении к двудольным графам также дает максимальное соответствие. Время работы n ^ 5. Я хотел бы знать какие-либо более быстрые алгоритмы для решения этой проблемы (особенно для двудольных графов). Один алгоритм, который я сейчас изучаю, - это Изменить метку на передний план, что равно n ^ 3.
Алгоритм быстрого максимального соответствия для двудольных графов
comment
Этот алгоритм, который является эффективной реализацией Форда-Фулкерсона, имеет время выполнения O (n ^ 3)
- person Niklas B. schedule 14.04.2014
comment
С этим я получаю переменный ток через 0,018 секунды.
- person Niklas B. schedule 14.04.2014
comment
О, спасибо, Никлас! Как обычно, ты снова решил это, лол! Хорошо, я отлажу ваш код, чтобы понять его, но я подумал, что нам не следует использовать Ford Fulkerson, потому что он использует DFS. Вместо этого мы должны использовать BFS для поиска дополнительных путей. С другой стороны, похоже, что ваш подход делает гораздо больше, чем просто поиск дополнительных путей, поскольку я вижу жадное сопоставление в комментариях.
- person Varun Sharma schedule 15.04.2014
comment
Нет, я не использовал жадное сопоставление. И DFS по какой-то причине на самом деле лучше для двудольного сопоставления
- person Niklas B. schedule 15.04.2014
comment
вы имеете в виду, что ваш алгоритм просто форд-фулкерсон? просто продолжайте находить дополнительные пути, пока не перестанете их искать?
- person Varun Sharma schedule 15.04.2014
comment
Да, точно. Вы можете прочитать об этом здесь
- person Niklas B. schedule 15.04.2014
comment
О, хорошо, спасибо. Это странно, потому что вам нужно запустить dfs, найти путь, найти узкое место, а затем обновить график. Вы сделали все это в 20 строках !!!!!!! Моя обычная реализация ford fulkerson / edmond karp составляет около 100 строк (bfs + найти путь + найти узкое место + обновить график).
- person Varun Sharma schedule 15.04.2014
comment
Ой ну спасибо. Эта ссылка отличная. В нем есть отличные уроки по динамическому программированию (мое самое слабое место) !! Спасибо дружище.
- person Varun Sharma schedule 15.04.2014
comment
Это меньше кода, потому что увеличивающие пути в двудольных сопоставлениях имеют очень особую структуру. Вы можете просто жадно найти путь нечетной длины, а пропускная способность узкого места всегда равна 1. И, очевидно, DFS всегда немного короче, потому что структура данных (стек) представлена неявно с использованием рекурсии.
- person Niklas B. schedule 15.04.2014
comment
Да, правда, не подумал, узкое место - 1, а рекурсия убирает код, который у нас обычно будет в итеративной DFS. Но нужно научиться путям нечетной длины. Сегодня у меня будет время разобраться в вашем коде. Спасибо за усилия и время :-).
- person Varun Sharma schedule 16.04.2014
comment
Спасибо, Никлас, у меня кондиционер! На самом деле изначально моя программа занимала 0,58 секунды, но затем я передал график (2D-вектор) как ссылку на константу, и внезапно время упало до 0,018. Раньше я не воспринимал это всерьез. Спасибо вам, потому что ваша программа работала так быстро, и в результате я пытался настроить свою.
- person Varun Sharma schedule 18.04.2014
comment
Молодец. Удивительно, но даже Динич не может победить это время. 18 мс - это, вероятно, степень детализации измерения времени выполнения, или график слишком мал, чтобы увидеть разницу
- person Niklas B. schedule 18.04.2014
comment
И Престижность за то, что вы написали свою собственную реализацию и придерживались ее. Нет лучшего способа узнать об алгоритме, чем написать его с нуля и чертовски оптимизировать :) Слишком много людей в конкурентном программировании просто повторно используют идеи и код других людей.
- person Niklas B. schedule 18.04.2014
comment
Спасибо, Никлас, мне потребовалась отладка / чтение, чтобы понять, почему этот алгоритм на самом деле работает. К счастью, в той ссылке, которую вы дали, было часовое видео, объясняющее алгоритм. Но ты самый уникальный человек, которого я видел в stackoverflow. Обычно люди либо опускают подобные вопросы об алгоритмах, либо объясняют идею. С другой стороны, вы не только математически объясняете идею (что более важно), но и решаете проблему и получаете AC :-). Я никогда раньше такого не видел :-). Невероятный.
- person Varun Sharma schedule 19.04.2014
comment
Я использую все возможности для практики, так как мы хотим выиграть региональные соревнования ICPC в этом или следующем году. Неудивительно, что другие люди не чувствуют того же :) Но есть такие, например Gassa
- person Niklas B. schedule 19.04.2014
comment
Ладно, всего наилучшего. Я почти уверен, что ты сможешь выйти в мировой финал. Если бы вы учились в нашем университете - вы бы выиграли регионал в одиночку :-). Не уверен, насколько жесткая конкуренция в Германии !!
- person Varun Sharma schedule 21.04.2014
comment
Антарктида ... Я вижу, насколько там конкуренция может быть слабее: D
- person Niklas B. schedule 21.04.2014
comment
Лол, нет, я из Новой Зеландии :-), но до Антарктики всего 8 часов полета !!!
- person Varun Sharma schedule 26.04.2014
Ответы (3)
Я пишу двустороннее сопоставление, используя алгоритм Диница. Также существует теорема, согласно которой для графов типа задач максимального двудольного сопоставления она имеет ту же сложность, что и перемаркировка на передний план (и ее гораздо проще реализовать).
В сетях, возникающих при решении задачи двустороннего согласования, количество фаз ограничено O (\ sqrt {V}), что приводит к ограничению времени O (\ sqrt {V} E). Полученный алгоритм также известен как алгоритм Хопкрофта – Карпа. В более общем смысле, эта граница верна для любой единичной сети - сети, в которой каждая вершина, за исключением источника и приемника, либо имеет одно входное ребро с пропускной способностью один, либо одно исходящее ребро с пропускной способностью единица, а все остальные пропускные способности являются произвольными целыми числами. .
К сожалению, статьи в Википедии об алгоритме недостаточно для его реализации, и я не смог найти лучшего ресурса в Интернете. У меня есть собственная реализация, но я уже давно создал ее, используя рекомендации других сотрудников моего университета.
person
Ivaylo Strandjev
schedule
14.04.2014
У Хопкрофта-Карпа неплохой псевдокод: en.wikipedia.org/wiki/Hopcroft% E2% 80% 93Карп_алгоритм
- person IVlad; 14.04.2014
@IVlad Но Dinic - это почти тот же код, такой же быстрый и работает и для общих графиков.
- person Niklas B.; 14.04.2014
@NiklasB. - Я предложил Hopcroft-Karp только потому, что в нем есть подробный псевдокод, и в ответе говорилось, что это трудно найти для Динича.
- person IVlad; 14.04.2014
Это правда. Трудно найти объяснение и реализацию алгоритма DINIC. Я нашел этот действительно хороший сайт. Спасибо переводчику Google, теперь я тоже могу это читать :-) e-maxx.ru/algo/dinic < / а>
- person Varun Sharma; 15.04.2014
Так называемый венгерский алгоритм для двустороннего сопоставления может быть реализован с меньшей сложностью выполнения.
person
Codor
schedule
14.04.2014
Хорошо, я вижу это здесь - en.wikipedia.org/wiki/, но там написано, что время работы n ^ 4.
- person Varun Sharma; 14.04.2014
Здесь объясняется реализация n ^ 3 - community.topcoder.com/ здесь. Это должно быть хорошо.
- person Varun Sharma; 14.04.2014
Hungerian предназначен для взвешенного сопоставления, для двустороннего сопоставления это довольно неэффективно
- person Niklas B.; 14.04.2014
Да ладно, спасибо за это. Я знаю, что на UVA Online Judge есть некоторые взвешенные проблемы с двусторонним соответствием, может быть, для них я могу попробовать. На данный момент я просто пойму ваш код из 20 лайнеров для максимального двудольного соответствия. На самом деле я планировал около 5-6 задач на двустороннее сопоставление, но застрял на этой из-за TLE. У этой конкретной проблемы был сложный случай с 0 слева / справа, и вы тоже это учли :-).
- person Varun Sharma; 15.04.2014
@VVV Подобно тому, как вы можете решить максимальное сопоставление с использованием максимального потока, вы можете решить сопоставление минимальной стоимости с помощью потока минимальной стоимости. Таким образом, в соревновательном программировании имеет смысл познакомиться с последним, поскольку оно носит более общий характер. Если честно, я никогда не нуждался в Hungerian именно по этой причине
- person Niklas B.; 15.04.2014
Ох, хорошо. Спасибо. На самом деле, мне нужно попрактиковаться в этих типах (Bellman Ford, чтобы найти путь минимальной стоимости несколько раз).
- person Varun Sharma; 16.04.2014
Алгоритм Хопкрофта – Карпа обеспечивает наименьшую временную сложность для поиска максимального совпадения (или минимального покрытия вершин) для Bipartite graph.
Согласно wikipidea, он выполняется в O(E * (V^0.5)), E - это общее количество ребер, а V - это общее количество вершин. В худшем случае (плотный граф) это будет O(V^2.5).
person
User_67128
schedule
26.02.2020
