русс | укр

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

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

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

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


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

Алгоритм построения максимального потока в транспортной сети.


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


Пример 91.

Орграф приращений.

Выделим для заданной транспортной сети D и допустимого потока jв этой сети орграф приращений I(D, j), имеющий те же вершины, что и сеть D. Каждой дуге x = (v, w)ОX транспортной сети D в орграфе приращений I(D, j) соответствуют две дуги: x и x` = (w,v) - дуга, противоположная по направлению дуге x. Припишем дугам x = (v, w)ОX, x` = (w, v)орграфа приращений I(D, j) длину l:

т.е. орграф I(D, j) является нагруженным. При этом, очевидно, что длинна любого пути из v1 в vn орграфе I(D, j) равна либо 0, либо Ґ.

Построить орграф приращений для данной транспортной сети и построенного полного потока в этой сети.

Решение.

Напомним, что орграф приращений имеет в два раза больше дуг, чем исходная транспортная сеть.

Для дуги прямой направленность вес равен 0, если дуга не является насыщенной, Ґ - в противном случае. Для дуги обратной направленности вес равен 0, если поток по ней не равен нулю, Ґ - в противном случае. На рисунке 50 изображен орграф приращений, соответствующий данному потоку в исходной транспортной сети.

Алгоритм построения максимального потока в транспортной сети D:

Шаг 1. Полагаем i = 0. Пусть j0 - любой допустимый поток в транспортной сети D. (например, полный; можно начинать с нулевого потока: j0 (x), x О X).

Шаг 2. По сети D и потоку ji строим орграф приращений I(D, ji).

Шаг 3. Находим простую цепь hi, являющуюся минимальным путем из v1 в vnв нагруженном орграфе I(D, ji)(например, используя алгоритм Форда - Беллмана). Если длина этой цепи равна Ґ, то поток ji максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи hi на максимально допустимую величину ai > 0, где ai О Z (прибавляя ее для каждой дуги x О X, через которую проходит цепь hi, к уже имеющейся величине потока по дуге x, если направления x и hi совпадают, и, вычитая, если направления x и hi противоположны).



Пример 92.

Выяснить является ли полный поток максимальным (рис. 51), если нет, то дополнить его до максимального.

Решение.

Для решения используем алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе.

Построим матрицу длин дуг C(D) и l-матрицу (табл. 69).

Таблица 69

  v1 v2 v3 v4 v5 v6  
v1 Ґ Ґ Ґ Ґ Ґ  
v2 Ґ Ґ Ґ Ґ   Ґ Ґ
v3 Ґ Ґ   Ґ
v4 Ґ Ґ Ґ   Ґ Ґ Ґ Ґ Ґ
v5 Ґ Ґ Ґ   Ґ Ґ Ґ
v6 Ґ Ґ Ґ Ґ   Ґ Ґ Ґ Ґ

Поскольку , то существует нулевой путь из источника v1 в сток v6. Значит, полный поток не является максимальным. Дополним его до максимального. Для этого найдем путь нулевой длины:

Получаем, что k1 = 4. Таким образом, минимальное число дуг в пути среди всех нулевых путей из v1 вv6 в орграфе приращений равняется 4. Определим теперь последовательность номеров i1, i2, i3, i4, i5,где i1 = 6.

Получаем, что в качестве такой последовательности надо взять номера 1, 3, 2, 5, 6, так как

Тогда v1v3v2v5v6 – искомый нулевой путь из v1 в v6 . Дуги, совпадающие по направлению с дугами исходной транспортной сети помечаем знаком «+», не совпадающие – знаком «-».

Получаем, Теперь необходимо найти величину, которую будем перемещать по полученному контуру. Для этого, каждому ребру в контуре поставим в соответствие число a(i, j), которое находим по следующему правилу: если направление ребра (i, j) в контуре совпадает с направлением ребра x в транспортной сети, то a(i,j)=с(х)-j(х); если направление ребра в контуре не совпадает с направлением ребра в транспортной сети, то a(i, j)=j(х). Итак, из чисел a(i, j) найдем минимальное:

min{8-2=6, 2, 6-2=4, 9-4=5}=2.

Перемещаем по контуру 2.

В результате получаем поток, изображенный на рисунке 52.

Заметим, что в полученной транспортной сети не существует пути из источника в сток, по которому возможно пройти. Следовательно, построенный поток в транспортной сети является полным и j = 11. Проверим, является ли он максимальным.

Построим матрицу длин дуг C(D) и l-матрицу (табл. 70).

Таблица 70

  v1 v2 v3 v4 v5 v6  
v1 Ґ Ґ Ґ Ґ Ґ  
v2 Ґ Ґ Ґ   Ґ Ґ Ґ Ґ Ґ Ґ
v3 Ґ Ґ Ґ Ґ Ґ   Ґ
v4 Ґ Ґ Ґ   Ґ Ґ Ґ Ґ Ґ Ґ
v5 Ґ Ґ Ґ   Ґ Ґ Ґ Ґ Ґ Ґ
v6 Ґ Ґ Ґ Ґ   Ґ Ґ Ґ Ґ Ґ Ґ

Так как , то нулевого пути из v1 в v6 не существует. Значит, поток является максимальным.

 



<== предыдущая лекция | следующая лекция ==>
Поток в транспортной сети. | Е) Рекламные средства


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


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

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

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


 


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

 
 

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

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