|
Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира.
60 лет назад, эта задача решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения задачи о максимальном потоке ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов. Асимптотическая оценка его быстродействия превзошла O(nm), о такой скорости многие годы можно было только мечтать. Уверен, что за прошедшие годы алгоритм Голдберга и Рао тщательно изучался и улучшался.
К сожалению, в России, в настоящее время, передовые алгоритмы освещаются слабо. Во всех русскоязычных учебниках, рассматривающих задачу о максимальном потоке в сети, вы вряд ли встретите что-либо, кроме метода пометок Форда-Фалкерсона 60-летней давности. В то время как в зарубежной литературе им редко ограничиваются.
В этой работе, я рассматриваются 12 алгоритмов решения задачи о максимальном потоке, динамические структуры для их реализации, и применение метода Форда-Фалкерсона для выделения Web-групп в WWW.
|
|
1. Вентцель Е.С. Исследование операции: задачи, принципы, методология.
2. Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций.
3. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях.
4. Шикин Е.В., Чхартишвилли А.Г. Математические методы и модели управления.
|
На уровень вверх
Купить