Алгоритм Форда-Фалкерсона
- Автор метода
- Lester R. Ford and Delbert R. Fulkerson
- Год
- 1956
- Тип
- algorithm
- Семейство
- Graph Algorithms
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Алгоритм Форда-Фалкерсона, разработанный Лестером Р. Фордом и Делбертом Р. Фалкерсоном в 1956 году, является фундаментальным методом для вычисления максимального потока в транспортной сети.
Он находит максимальный объем потока, который может быть отправлен от источника к стоку через ориентированный граф с ограничениями пропускной способности на ребрах.
Интуиция метода
Алгоритм работает путем многократного нахождения увеличивающих путей от источника к стоку в остаточной сети, где каждое ребро имеет оставшуюся пропускную способность. Каждый путь вносит дополнительный поток, равный его «бутылочной» пропускной способности (ребро с минимальной оставшейся пропускной способностью на пути). Процесс продолжается до тех пор, пока не останется увеличивающих путей, после чего достигается максимальный поток. Ключевая идея заключается в теореме о максимальном потоке и минимальном разрезе: максимальный поток равен минимальной пропускной способности разреза в сети.
История
Форд и Фалкерсон представили задачу о максимальном потоке и свой основополагающий алгоритм в 1956 году. Эта работа была революционной, установив как алгоритмический метод, так и знаменитую теорему о максимальном потоке и минимальном разрезе. Эдмондс и Карп (1972) улучшили сложность в худшем случае, используя поиск в ширину для выбора пути. Последующие достижения Диница, Карзанова и других привели к еще более быстрым алгоритмам, но метод Форда-Фалкерсона остается классическим и педагогически ценным алгоритмом в информатике.
Когда применять
Применяйте алгоритм Форда-Фалкерсона для нахождения максимального потока в ориентированных или неориентированных транспортных сетях с положительными целочисленными пропускными способностями. Он хорошо работает для сетей малого и среднего размера и обеспечивает интуитивное понимание концепций сетевого потока. Для очень больших сетей или когда требуются целочисленные потоки, рассмотрите алгоритм Эдмондса-Карпа (использующий BFS) или алгоритм Диница для лучшей производительности в худшем случае. Используйте его, когда понимание поведения алгоритма так же важно, как и скорость.
Ограничения и замечания
- Временная сложность зависит от значений пропускной способности (в общем случае не полиномиальна; может быть экспоненциальной при иррациональных пропускных способностях)
- Может не завершиться, если пропускные способности иррациональны (требует тщательной реализации с рациональной арифметикой)
- Менее эффективен, чем специализированные алгоритмы, такие как Эдмондса-Карпа или Диница, на больших сетях
- Чувствителен к порядку выбора увеличивающего пути
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Простой и интуитивно понятный подход, основанный на увеличивающих путях
- Гарантированное оптимальное решение, когда пропускные способности рациональны или целочисленны
- Эффективен для сетей с малыми целочисленными пропускными способностями
- Формирует теоретическую основу для понимания двойственности максимального потока и минимального разреза
- Работает как с ориентированными, так и с неориентированными графами
Применение
- Маршрутизация сети: максимизация пропускной способности данных от источника к месту назначения в коммуникационных сетях
- Транспортные сети: определение максимальной грузоподъемности между городами с учетом ограничений автомобильных и железнодорожных путей
- Двудольный граф: нахождение максимальных паросочетаний в двудольных графах путем построения потоковых сетей
- Сегментация изображений: использование алгоритмов максимального потока для разделения изображений на передний план и фон
- Планирование авиарейсов: оптимизация маршрутизации самолетов для максимизации пассажиропотока через хабовые сети
- Анализ белков: вычисление максимального потока в биологических сетях для понимания путей взаимодействия
Как это работает
Как это работает
Инициализируйте остаточный граф с пропускными способностями, равными исходным пропускным способностям ребер, и нулевым потоком на всех ребрах.
Найдите увеличивающий путь от источника к стоку в остаточном графе, используя поиск в глубину или поиск в ширину, вычислите минимальную пропускную способность вдоль пути и добавьте этот поток ко всем ребрам на пути, одновременно уменьшая их остаточные пропускные способности.
Повторяйте увеличение до тех пор, пока в остаточном графе не останется увеличивающих путей; общий накопленный поток является максимальным потоком.
Частые ошибки
- Выбор неудачных увеличивающих путей, приводящих к медленной сходимости или неверным результатам
- Неправильное обновление остаточных пропускных способностей или добавление обратных ребер для отмены потока
- Использование целочисленного деления или арифметики с плавающей запятой, когда для корректности требуется точная арифметика
Часто задаваемые вопросы
Что такое теорема о максимальном потоке и минимальном разрезе?
Теорема утверждает, что максимальный поток от источника к стоку равен минимальной пропускной способности любого разреза, отделяющего источник от стока. Это обеспечивает как теоретическое понимание, так и метод проверки для алгоритмов потока.
Почему алгоритм иногда сходится медленно?
При неудачном выборе пути алгоритм может увеличивать поток только на одну единицу за итерацию, даже когда возможны большие увеличения. Использование поиска в ширину (Эдмондс-Карп) обеспечивает сходимость за полиномиальное время.
Как алгоритм обрабатывает неориентированные ребра?
Замените каждое неориентированное ребро двумя ориентированными ребрами в противоположных направлениях, оба с одинаковой пропускной способностью. Затем алгоритм находит поток в ориентированной сети.
В чем разница между потоком на ребре и остаточной пропускной способностью?
Поток на ребре представляет собой количество материала, отправленного по нему, в то время как остаточная пропускная способность — это оставшаяся доступная пропускная способность. Остаточная пропускная способность уменьшается по мере увеличения потока, а обратные ребра отслеживают возможность отмены потока.
Похожие методы
Источники
Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.
Открыть ссылку DOIСкопировано.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Скопировано.