Алгоритм Эдмондса-Карпа: детальный анализ эффективности

Алгоритм Эдмондса-Карпа является конкретной реализацией метода Форда-Фулкерсона для вычисления максимального потока в сети потока. В то время как оригинальный метод Форда-Фулкерсона использует произвольный поиск путей увеличения (который может привести к экспоненциальному времени в патологических случаях), Эдмондс-Карп обеспечивает поиск на основе BFS, гарантируя, что самый короткий путь увеличения (с точки зрения количества краев) выбирается каждой итерацией. Эта гарантия дает четко определенное полиномиальное время выполнения и делает алгоритм краеугольным камнем вводной теории потока сети.

Алгоритмическое описание и ключевые свойства

При наличии направленного графа G = (V, E) с источником s, опусканием t и функцией емкости c:E → R+ алгоритм Эдмондса-Карпа протекает следующим образом:

  1. Инициировать поток f(e) = 0 для всех краев.
  2. Постройте остаточный граф Gf (включая ребра назад с пропускной способностью, равной потоку тока).
  3. В этом случае следует использовать хештег Gfs, чтобы найти кратчайший путь к t (измеряется по количеству краев).
  4. Если нет пути, прекратите; поток тока максимальн.
  5. В противном случае, определите емкость узкого места вдоль пути (минимальная остаточная емкость).
  6. Увеличение потока на эту сумму вдоль пути и обновление остаточных мощностей.
  7. Повторить шаг 2.

Использование BFS гарантирует, что каждый найденный путь увеличения является кратчайшим путем в остаточном графе. появляется критическое свойство: расстояние (по краям) от s до t в остаточном графе никогда не уменьшается и строго увеличивает каждую O(E) итерации.

Анализ сложности

Срок выполнения каждого BFS составляет O(V + E), что упрощает O(E)] для типичных разреженных графиков. Основная задача — ограничить количество дополнений. Поскольку каждое увеличение насыщает по меньшей мере один край (]V/2 раз (поскольку каждое насыщение увеличивает расстояние от до t, общее количество путей увеличения — O(VE). Умножение на стоимость BFS даёт наихудшую сложность O(V E2).

Точнее, стандартный анализ показывает, что число дополнений в лучшем случае O(VE), поэтому общее время составляет O(V E2)O(V E* (V+E)]E = ⁇ (V2), что довольно медленно для больших сетей. Однако на практике производительность часто лучше, чем в наихудшем случае, особенно для сетей с удельной емкостью или когда граф разрежен.

Сравнение с другими алгоритмами Макса Потока

Алгоритм Диника

Алгоритм Диника также использует BFS для построения графа уровня, но затем позволяет несколько путей увеличения в одной фазе через DFS на графе уровня. Это уменьшает количество BFS-бегов до максимума V (поскольку уровень раковины увеличивается на каждой фазе.] Общая сложность составляет O(V2 E)O(E √V) для двухстороннего сопоставления единицы мощности. Для большинства практических сетей Диник превосходит Эдмондс-Карп, потому что он посылает поток по многим путям одновременно.

Алгоритмы Push-Relabel

Методы Push-relabel, такие как общий алгоритм или вариант с самой высокой меткой, достигают границ O(V2 √E) или O(V3). Они работают, толкая поток локально по соответствующим краям и перемаркируя вершины для поддержания действительной маркировки. Эти алгоритмы более сложны для реализации, но часто работают быстрее на практике, особенно для больших плотных графов. Алгоритм с самой высокой меткой push-relabel широко используется в конкурентном программировании и реальных решателях потоков.

Другим важным вариантом является алгоритм масштабирования емкости , который добавляет параметр масштабирования к методу Форда-Фулкерсона, получая O(E2 log U), где U является максимальной емкостью.

Почему Эдмондс-Карп все еще имеет значение

Несмотря на то, что он медленнее, чем Dinic и push-relabel, Edmonds-Karp педагогически ценен. Его простота и интуитивное доказательство полиномиальной среды выполнения (на основе монотонности кратчайшего пути) делают его отличным учебным инструментом. Многие учебные программы по информатике представляют Edmonds-Karp перед переходом на более продвинутые методы. Кроме того, для сетей малого и среднего размера (скажем, до нескольких тысяч вершин и краев) практическая разница в производительности может быть незначительной, особенно если график редкий и имеет низкие граничные возможности.

Практические последствия и случаи использования

В реальных приложениях выбор алгоритма в значительной степени зависит от проблемных ограничений.

  • Бипартитное сопоставление: Эдмондс-Карп сводится к алгоритму Хопкрофта — Карпа, когда мощности являются единицей, а сеть — двухпартийной? На самом деле нет — Хопкрофт — Карп является выделенным алгоритмом с O(E √V) временем; однако Эдмондс-Карп на двухпартийных графах емкости единицы работает в O(V E)? В сетях емкости единицы каждый BFS находит путь увеличения, который насыщает один край, и количество дополнений ограничено значением максимального потока F. Для двухпартийного сопоставления F ≤ V, поэтому сложность становится O(V E), что приемлемо для умеренных размеров
  • Инженерия дорожного движения: В телекоммуникациях и дорожных сетях потоки часто большие и графики редкие.
  • Сегментация изображений: Алгоритмы графического разреза для компьютерного зрения часто полагаются на вычисления с максимальным потоком/мин-разрезом. Алгоритм Бойкова-Колмогорова, специализированный метод пути увеличения, часто превосходит общие алгоритмы для этих сетчатых графов, но Эдмондс-Карп может использоваться для меньших задач.
  • Образование и прототипирование: Когда простота и правильность имеют первостепенное значение по сравнению с сырой скоростью, Edmonds-Karp является безопасным выбором. Его поведение предсказуемо, а отладка проста, потому что BFS легко реализовать.

Эмпирическое исполнение

Сравнительные показатели на случайных графиках показывают, что Эдмондс-Карп на практике часто работает в почти линейное время, когда граничные мощности малы (]O(1)), потому что число увеличений ограничено максимальным значением потока, которое может быть малым. Однако для сетей с высокой пропускной способностью алгоритм может ухудшаться. Например, рассмотрим сеть, где емкости являются большими целыми числами; значение потока может быть огромным, что приводит к многим увеличениям. В таких случаях методы Диника или масштабирования более надежны.

Рассмотрение осуществления

При реализации Edmonds-Karp необходимо тщательное управление остатками графов. Представление как передних, так и задних краев позволяет легко увеличивать и отсылать. Использование списка смежности с указателями для обратного края (или хранения индексов обратного края) упрощает обновления. BFS также должна записывать предшественников для реконструкции пути увеличения. Использование памяти O(V + E), аналогично другим алгоритмам.

Оптимизация включает в себя:

  • Если же он не может быть устранен, то он не может быть устранен (устранен) до наступления срока.
  • Использование целых мощностей и потоков для избежания проблем с плавающей запятой.
  • Агрегирование множественных увеличений, если граф имеет много параллельных краев (хотя и менее распространенных).

Для очень больших сетей рассмотрите возможность использования динамической BFS, которая постепенно обновляет расстояния, но это часто добавляет сложность без значительного выигрыша для Edmonds-Karp.

Связь с оригинальным методом Форда-Фулкерсона

Джек Эдмондс и Ричард Карп опубликовали свой алгоритм в 1972 году, продемонстрировав, что использование BFS даёт алгоритм максимального потока полиномиального времени. До этого метод Форда-Фулкерсона (1956) не определял правило выбора пути, и было известно, что плохой выбор может привести к экспоненциальному времени. Работа Эдмондса и Карпа была основополагающим шагом в разработке сильно полиномиальных алгоритмов для сетевых потоков. Статья «Теоретические улучшения алгоритмической эффективности для проблем сетевого потока» остаётся классическим справочником.

Расширения и вариации

Варианты Эдмондс-Карп включают:

  • Версия масштабирования пропускной способности: Вместо того, чтобы всегда увеличиваться по кратчайшему пути, алгоритм работает с параметром масштабирования Δ и рассматривает только края с остаточной емкостью ≥ Δ.Это даёт алгоритм O(E2 log U).
  • Оптимизация пропускной способности узла : Когда все мощности равны 1, алгоритм пути увеличения на основе BFS специализируется на алгоритме Хопкрофта-Карпа, хотя последний использует тщательный чередование BFS/DFS для достижения O(E √V).
  • Неотъемлемость: Алгоритм естественным образом поддерживает интегральные потоки, когда интегральные возможности, что делает его пригодным для комбинаторных задач.

Заключение

Алгоритм Эдмондса-Карпа является надежным и хорошо понятным методом решения задач с максимальным потоком. Его O(V E2) наихудшая временная сложность делает его непрактичным для очень больших или плотных сетей, но его простота и четкое доказательство полиномиальной среды выполнения закрепили его место в учебниках по алгоритмам. Для реальных систем, требующих высокой производительности, алгоритм Диника или методы push-переименования, как правило, предпочтительны. Однако для образовательных настроек, небольших проблем или в качестве базового уровня для проверки правильности, Эдмондс-Карп остается ценным инструментом.

Дальнейшее чтение по расширенным алгоритмам потока можно найти в статье Википедии и в классическом учебнике Введение в алгоритмы (CLRS). Для более глубокого анализа производительности алгоритма потока см. Примечания к реализации потока NetworkX .