Алгоритм "проталкивания-перемаркировки"
- Автор метода
- 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) с эвристикой разрыва
- Высокая эффективность на практике, особенно для больших и плотных сетей
- Локальность операций (проталкивание/перемаркировка) обеспечивает хорошую производительность кэша
- Пригоден для распараллеливания и распределённых реализаций
- Множество вариантов реализации для различных структур задач
Применение
- Маршрутизация сети: вычисление максимальной пропускной способности в крупномасштабных коммуникационных сетях
- Обработка изображений: использование максимального потока для сегментации изображений и приложений матирования
- Оптимизация авиаперевозок: определение максимального пассажиропотока через сложные маршрутные сети
- Анализ электросетей: вычисление максимальной пропускной способности электропередачи в электрических сетях
- Управление цепочками поставок: оптимизация потока продуктов через многоуровневые распределительные сети
- Биологические сети: анализ максимального потока в метаболических и белковых взаимодействующих сетях
Как это работает
Как это работает
Установите высоту истока равной количеству вершин, все остальные высоты равными нулю. Насытьте все рёбра, исходящие из истока, создавая начальный пред-поток (избыток в соседних узлах).
Многократно выбирайте активный узел (с избыточным потоком) и либо проталкивайте избыток к соседу с меньшей высотой, либо перемаркировывайте узел для увеличения его высоты. Используйте эффективные стратегии выбора и операции разгрузки для минимизации итераций.
Продолжайте до тех пор, пока не останется активных узлов, после чего весь пред-поток будет преобразован в максимальный поток от истока к стоку.
Частые ошибки
- Неправильная реализация обновлений высоты или операций проталкивания, приводящая к не максимальным потокам
- Пренебрежение использованием эвристик разрыва и эффективного выбора узлов, что приводит к низкой практической производительности
- Неспособность правильно поддерживать инвариант пред-потока (избыток в узлах и ограничения пропускной способности на рёбрах)
Часто задаваемые вопросы
В чём разница между пред-потоком и потоком?
Пред-поток временно позволяет узлам удерживать избыточный поток (поток входящий минус поток исходящий может быть положительным), тогда как истинный поток должен сохраняться во всех узлах, кроме истока и стока. Алгоритм завершается, когда пред-поток становится допустимым потоком.
Какова цель функции высоты?
Высоты создают квази-меру расстояния: поток может быть протолкнут только "вниз" (от более высоких к более низким высотам), предотвращая ненужные циклы и обеспечивая завершение. Высоты увеличиваются посредством перемаркировки для создания новых путей при необходимости.
Что такое эвристика разрыва и почему она важна?
Эвристика разрыва обнаруживает, когда ни один узел не имеет высоты в определённом диапазоне, указывая на то, что некоторые узлы не могут достичь стока. Эти узлы и их избыток быстро идентифицируются и обрабатываются, значительно улучшая практическую производительность.
Как алгоритм "проталкивания-перемаркировки" сравнивается на практике с алгоритмом Эдмондса-Карпа?
Алгоритм "проталкивания-перемаркировки" имеет лучшую сложность в худшем случае и обычно превосходит алгоритм Эдмондса-Карпа на больших сетях, но для малых сетей или разреженных графов алгоритм Эдмондса-Карпа может быть проще в реализации с конкурентной производительностью.
Похожие методы
Источники
Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940.
Открыть ссылку DOIСкопировано.Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin.
Открыть ссылку на публикациюСкопировано.