Читайте также:
|
Если мы припишем каждой дуге ориентированного графа поток некоторого вещества, то граф становится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с действительным или воображаемым движением товаров, информации или людей. И очень часто встает вопрос о передвижении чего-либо в нужный пункт назначения с наибольшей рациональностью. Отсюда возникает важная задача в теории графов, называющаяся задачей о наибольшем потоке.
Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?
Два наиболее популярных алгоритма — алгоритм Форда-Фалкерсона и алгоритм "проталкивания предпотока".
Алгоритм Форда-Фалкерсона
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех 
. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.
Схема алгоритма:
1) Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
2) В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
3) Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
a) На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью 
.
b) Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему - уменьшаем на .
c) Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
4) Возвращаемся на шаг 2.
Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению. Это является основной сложностью данного алгоритма.
Применение алгоритма решения задачи
Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в сети интернет. Исследования данной задачи проводятся во множестве крупнейших университетов мира.
ЗАКЛЮЧЕНИЕ
В настоящее время теория графов охватывает большой материал и активно развивается. И прежде всего это развитие обусловлено прогрессом вычислительной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Поэтому, учитывая сегодняшнюю тенденцию развития вычислительной техники, можно судить, что этот предмет еще недостаточно изучен и представляет собой огромное поле для исследований и интересных открытий.
Дата добавления: 2015-02-16; просмотров: 105 | Поможем написать вашу работу | Нарушение авторских прав |