русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

ЛЕКЦИЯ 9. Алгоритмы для нахождения максимального потока и минимального разреза


Дата добавления: 2013-12-23; просмотров: 4566; Нарушение авторских прав


 

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

Алгоритм Форда-Фалкерсона состоит из двух шагов. Первый шаг присваивает узлам метки для поиска увеличивающего пути. Второй шаг увеличивает поток вдоль увеличивающего пути, найденного на первом шаге. Начинаем с нулевого значения потока (т. е. xij = 0 при всех i, j)и повторяем шаги 1 и 2 до тех пор, пока поток не станет максимальным.

Шаг 1. Процесс расстановки пометок. Каждый узел всегда находится в одном из следующих трех состояний.

(1) Непомеченный: узел еще не получил пометки. Вначале каждый узел является непомеченным.

(2) Помеченный и неотсканированный: узел помечен, но не все его соседи являются помеченными.

(3) Помеченный и отсканированный: узел помечен и все его соседи также помечены.

Узел Vj получает пометку [a, c], состоящую из двух чисел. Число а обозначает наибольшую суммарную величину потока, который можно передать из V0в Vj. Число c указывает последний промежуточный узел увеличивающего пути из V0 в Vj. (Заметим сходство этих пометок и тех, которые использовались при решении задач о кратчайших путях в разделе)

В начале алгоритма присваиваем узлу V0пометку [,0], а каждому соседнему с ним узлу Vj присваиваем пометку [, 0]. Пусть у помеченного узла Vi есть еще не помеченный сосед Vj. Тогда узлу Vj присваиваем пометку [, i], где

.

В общем случае дополнительный поток из Vi в Vj можно отправить, если

xij < bij или xji > 0.

Предположим, что Vj имеет пометку [, r+], тогда Vj получает пометку

[, i+], если xij < bij , где .

Узел Vj получает пометку [, i -],если хji > 0, где .

Оба символа i+ и i- указывают, что Vi — последний промежуточный узел, при этом «+» означает, что еij — прямая дуга, а «-» означает, что еij — обратная дуга. Заметим, что узел Vj получает пометку только в случае, когда строго положительно.



Сначала узел V0, помечен и неотсканирован Он станет помеченным и отсканированным тогда, когда будут помечены все его соседи. Соседи V0 также становятся помеченными и отсканированными, когда будут помечены все их соседи. Процесс расстановки пометок продолжается до тех пор, пока не выполнится одно из двух условий:

(1) узел Vn помечен.

(2) узел Vn не помечен и больше нельзя присвоить никаких новых пометок.

В случае (2) все помеченные узлы (отсканированные и неотсканированные) составляют множество X, а непомеченные узлы — множество . Разрез ()является минимальным, а текущий поток — максимальным. Алгоритм завершает работу.

Шаг 2. Изменение потока: если узел Vn помечен, то можно проследовать обратно из Vn в V0и изменить потоки через дуги вдоль увеличивающего пути. Пусть [, k+] - пометка узла Vn, [, j -],— пометка узла Vk, a [, 0+] — пометка узла Vj. Тогда добавляем к xkn и x0j и вычитаем из xkj, т.е. добавляем величину к потокам для прямых дуг и вычитаем e(t) из потоков для обратных дуг.

Стираем все метки и возвращаемся на шаг 1.

 

Алгоритм Форда-Фалкерсона не определяет порядок, в котором происходит помечивание узлов или проверка помеченных и неотсканированных узлов. Если следовать правилу «первый помечен — первый отсканирован», то всегда будет использован кратчайший увеличивающий путь (кратчайший в том смысле, что число дуг в пути наименьшее). Это модификация Эдмондса и Карпа. Правило «первый помечен -первый отсканирован» - это поиск в ширину.

 

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

- если дуга в увеличивающем пути прямая, то ;

- если дуга обратная - .

Дуга из Vi в Vj называется полезной, если =0.

Коротко алгортим Форда-Фалкерсона можно описать следующим образом.

1. На основе существующего потока строится остаточная сеть с пропускными способностями .

2. В остаточной сети производим систематический поиск увеличивающего пути и увеличиваем поток вдоль увеличивающего пути.

 

Алгоритм Эдмондсома и Карпа. Если использовать поиск в ширину, предложенный Эдмондсом и Карпом, то поток всегда будет увеличиваться вдоль кратчайшего увеличивающего пути. Длиной пути называем число дуг в нем. Вначале используется увеличивающий путь длины 1. Если не существует увеличивающих путей длины 1, используется увеличивающий путь длины 2. Эти действия повторяются до тех пор, пока длина кратчайшего увеличивающего пути не станет равной n - 1.

Разобьем вычисления на n- 1 этапов. На каждом этапе происходит увеличение потоков вдоль увеличивающих путей заданной длины k (k = 1, 2, . . . ,n - 1). (От этапа к этапу длина кратчайшего увеличивающего пути возрастает.) В конце каждого этапа строится остаточная сеть, порожденная существующим потоком. В начале каждого этапа имеется остаточная сеть с пропускными способностями дуг, равными .

Разобьем все узлы сети на слои. По определению, источник V0лежит в нулевом слое. Узел Vi лежит в слое k, если кратчайший путь из V0в Vi имеет длину k.

На рис. 26 показана сеть, разбитая на четыре слоя. Заметим, что узел Vn лежит в слое 3. Следовательно, длина кратчайшего увеличивающего пути равна 3. Поток в сети, относительно которого нет увеличивающих путей длины 3, называется тупиковым. Например, если положить на рис. 26 пропускные способности всех дуг равными 1, то можно отправить единицу потока вдоль пути (e0i, e14, e4n). Тогда не существует увеличивающего пути длины 3, откуда заключаем, что текущий поток (величина которого равна 1) является тупиковым, хотя величина максимального потока в этой сети равна 2.

 

 

 

Рис. 26. Разделение сети на слои

 

Этап алгоритма:

1) Найти остаточную сеть,

2) Разбить множество узлов на слои,

3) Найти тупиковый поток.

Алгоритм состоит из последовательности таких этапов с ростом длины кратчайших увеличивающих путей.

Если длина увеличивающего пути от этапа к этапу возрастает, то число этих этапов не превосходит n- 1. Предположим, что имеется m дуг, В течение этапа существует не более m увеличивающих путей, и на поиск каждого такого пути требуется не более, чем О(т) шагов. Следовательно, итоговая трудоемкость поиска составляет О (m2) в течение этапа и O(nm2) для всего алгоритма Эдмондса и Карпа.

Оценка О (nm2) получается в предположении, что каждый увеличивающий путь в сети ищется независимо. Можно улучшить эту оценку до величины О(n2m), если на каждом этапе скоординировать поиск увеличивающих путей заданной длины. Эта улучшенная оценка принадлежит Диницу.

Алгоритм Диница. Вначале, используя поиск в ширину, строим подсеть N(f). После этого, применяя поиск в глубину, в N(f) отыскиваем увеличивающие пути, достигающие Vn . Если сток Vn достигнут, то увеличиваем поток вдоль найденного пути, корректируем пропускные способности дуг, проходя вдоль увеличивающего пути в обратном направлении, и удаляем дуги, пропускные способности которых стали равны нулю.

Если в процессе поиска в глубину при отыскании увеличивающего пути делается «шаг назад» из узла Vi, то все дуги, инцидентные узлу Vi, вычеркиваем из N(f) . Поиск в глубину затрачивает время О(п) и, поскольку в течение этапа имеется не более m увеличивающих путей, итоговая трудоемкость алгоритма составляет O(nm) для каждого этапа и O(n2m) в целом.

Заметим, что трудоемкость нахождения увеличивающего пути поиском в глубину не превосходит О(п), и при каждом поиске удаляется по крайней мере одна дуга. Алгоритм Диница на каждом этапе при построении тупикового потока насыщает по одной дуге.

Алгоритм Карзанова состоит из нескольких этапов, на каждом из которых ищется тупиковый поток в многослойной сети.

При поиске тупикового потока каждый раз насыщается один узел. Каждый этап начинается с проталкивания предпотока из V0, а затем из слоя в слой до тех пор, пока не будет достигнут узел Vn. Затем происходит балансировка предпотока в каждом узле. Таким образом, каждый этап состоит из двух шагов. Первый шаг называется продвижением предпотока, а второй — балансировкой предпотока. Эти шаги повторяются до получения тупикового потока в остаточной подсети N(f).

Шаг 1. Продвижение предпотока. Цель этой подпрограммы — протолкнуть предпоток наибольшей возможной величины из источника в сток.

Начинаем процесс в источнике V0 (в слое 0) и передаем предпоток с наибольшим возможным значением в узлы 1-го слоя, полагая x0j = b0j для всех узлов Vj из 1-го слоя. Считаем, что предпоток передан из слоя 0 в слой 1.

Вообще мы рассматриваем несбалансированные узлы из самого ниж­него слоя и пытаемся протолкнуть предпоток в следующий слой и далее до Vn. Подпрограмма продвижения останавливается тогда, когда никакой предпоток невозможно передать вперед из любого узла Vj. Это обязательно произойдет, если дуги в 0(Vj) либо закрыты, либо насыщены.

Шаг 2. Балансировка предпотока. Цель этой подпрограммы — сделать несбалансированные узлы сбалансированными и эффективно преобразовать предпотоки в регулярные потоки.

Начинаем с наивысшего слоя, содержащего несбалансированные узлы. Для каждого такого узла Vj уменьшаем потоки, входящие в него, по принципу «вошел последним — вышел первым» до тех пор, пока узел не станет сбалансированным. Все дуги в a(Vj), относящиеся к вновь сбалансированному узлу, объявляются закрытыми. Если в данном слое все несбалансированные узлы стали сбалансированными, то возвращаемся на шаг 1 (даже если остались несбалансированные узлы в низших слоях).

Заметим, что при первом выполнении шага 1 происходит продвижение предпотока из слоя 0 в слой 1, из слоя 1 в слой 2 и т. д. до тех пор, пока не будет достигнут узел Vn, после этого переходим к шагу 2. Однако в подпрограмме балансировки рассматривается только один слой — наивысший слой j, содержащий несбалансированные узлы. При балансировке узлов слоя j могут появиться несбалансированные узлы в слое j- 1. Поскольку все узлы слоев j - 2,..., 0 уже обработаны, можно начать шаг 1 из слоя j - 1 и продвигать наибольший возможный предпоток в сток n.

В этом алгоритме есть шаги балансировки и шаги продвижения. На шаге балансировки, если поток через дугу уменьшается, то эта дуга становится закрытой, следовательно, суммарное число уменьшений потока ограничено числом дуг О(т). Когда поток через дугу возрастает, она либо насыщенная, либо ненасыщенная. Но насыщение может произойти для каждой дуги не более одного раза, так как после любого уменьшения потока эта дуга станет закрытой. Следовательно, число насыщений также ограниче­но величиной О(m). Ситуация, при которой поток через дугу возрастает, но не до предельно возможного значения, может наблюдаться не более n -1 раз при начальном продвижении предпотока и не более n - 2 раз при следующем продвижении, поскольку некоторый узел балансировался при начальном продвижении предпотока и, следовательно, недоступен. Продолжая эти рассуждения, видим, что число шагов, увеличивающих поток, но не до предельно возможного значения, равно (n - 1) + (n - 2) + 1 = O(п2). Трудоемкость алгоритма Карзанова построения тупиковых потоков в многослойной сети ограничена величиной O(n2).

Следовательно, трудоемкость алгоритма ограничена величиной О (т) + О(п2) = О(п2). Поскольку число этапов равно n, суммарное время работы алгоритма Карзанова составляет О(п3).

Итак, на каждом этапе алгоритм Карзанова затрачивает О(п2) единиц времени. Так как число этапов не превосходит n - 1, то общая трудоемкость составляет О(n3).



<== предыдущая лекция | следующая лекция ==>
Теорема о максимальных разрезах | ЛЕКЦИЯ 10. Потоки с минимальной стоимостью. Метод анализа и оценки проекта REPT-метод


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.