Skip to content
Назад к результатам поиска

Алгоритм "проталкивания-перемаркировки"

Автор метода
Andrew V. Goldberg and Robert E. Tarjan
Год
1988
Тип
algorithm
Семейство
Graph Algorithms

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Алгоритм "проталкивания-перемаркировки" (Push-Relabel Algorithm), разработанный Эндрю В. Голдбергом и Робертом Э. Тарьяном в 1988 году, представляет собой высокоэффективный метод вычисления максимального потока в сетях.

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

Интуиция метода

Алгоритм поддерживает "высоту" или "метку расстояния" для каждого узла и использует пред-поток (где узлы могут временно превышать потребность стока). Он многократно проталкивает избыточный поток от узлов с более высокой меткой к соседям с более низкой меткой и перемаркировывает узлы для создания путей к стоку. Ключевая идея заключается в том, что, поддерживая инварианты высоты и используя эффективные структуры данных, алгоритм избегает многократного исследования всего графа, как это необходимо делать методам дополняющих путей. Алгоритм завершается, когда весь избыточный поток достигает стока.

История

Голдберг и Тарьян опубликовали свой алгоритм "проталкивания-перемаркировки" в 1988 году, представив принципиально иную парадигму для вычисления максимального потока. Их алгоритм достиг сложности O(V³) в худшем случае, что стало улучшением по сравнению с O(VE²) алгоритма Эдмондса-Карпа. В последующие десятилетия были разработаны многочисленные варианты, включая эвристики разрыва (Goldberg and Tarjan, 1990), правила наивысшей метки и новейшие варианты, достигающие почти линейной эмпирической производительности в реальных сетях.

Когда применять

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

Ограничения и замечания

  • Более сложен для понимания и реализации, чем методы дополняющих путей
  • Требует тщательной работы со структурами данных (списки разгрузки, эвристики разрыва) для оптимальной производительности
  • Сложность в худшем случае всё ещё выше, чем у некоторых специализированных алгоритмов для особых классов графов
  • Менее интуитивное понимание процесса решения по сравнению с дополняющими путями

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Превосходная временная сложность в худшем случае: O(V³) или O(V²√E) с эвристикой разрыва
  • Высокая эффективность на практике, особенно для больших и плотных сетей
  • Локальность операций (проталкивание/перемаркировка) обеспечивает хорошую производительность кэша
  • Пригоден для распараллеливания и распределённых реализаций
  • Множество вариантов реализации для различных структур задач

Применение

  • Маршрутизация сети: вычисление максимальной пропускной способности в крупномасштабных коммуникационных сетях
  • Обработка изображений: использование максимального потока для сегментации изображений и приложений матирования
  • Оптимизация авиаперевозок: определение максимального пассажиропотока через сложные маршрутные сети
  • Анализ электросетей: вычисление максимальной пропускной способности электропередачи в электрических сетях
  • Управление цепочками поставок: оптимизация потока продуктов через многоуровневые распределительные сети
  • Биологические сети: анализ максимального потока в метаболических и белковых взаимодействующих сетях

Как это работает

Как это работает

1

Установите высоту истока равной количеству вершин, все остальные высоты равными нулю. Насытьте все рёбра, исходящие из истока, создавая начальный пред-поток (избыток в соседних узлах).

2

Многократно выбирайте активный узел (с избыточным потоком) и либо проталкивайте избыток к соседу с меньшей высотой, либо перемаркировывайте узел для увеличения его высоты. Используйте эффективные стратегии выбора и операции разгрузки для минимизации итераций.

3

Продолжайте до тех пор, пока не останется активных узлов, после чего весь пред-поток будет преобразован в максимальный поток от истока к стоку.

Частые ошибки

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

Часто задаваемые вопросы

В чём разница между пред-потоком и потоком?

Пред-поток временно позволяет узлам удерживать избыточный поток (поток входящий минус поток исходящий может быть положительным), тогда как истинный поток должен сохраняться во всех узлах, кроме истока и стока. Алгоритм завершается, когда пред-поток становится допустимым потоком.

Какова цель функции высоты?

Высоты создают квази-меру расстояния: поток может быть протолкнут только "вниз" (от более высоких к более низким высотам), предотвращая ненужные циклы и обеспечивая завершение. Высоты увеличиваются посредством перемаркировки для создания новых путей при необходимости.

Что такое эвристика разрыва и почему она важна?

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

Как алгоритм "проталкивания-перемаркировки" сравнивается на практике с алгоритмом Эдмондса-Карпа?

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

Похожие методы

Источники

  1. Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.

    Открыть ссылку DOI
    Скопировано.
  2. Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.

    Открыть ссылку на публикацию
    Скопировано.