Алгоритмы поиска максимального потока

 

 

 

 

4.min(c_f(A,B),c_f(B,C),c_f(C,E),c_f(E,D),c_f(D,F),c_f(F,G)) =

min(3 − 1,4 − 1,2 − 0,0 − − 1,6 − 3,9 − 3) = 
min(2,3,2,1,3,6) = 1

 

 

 

 

 

 

2.2.3  Алгоритм Дініца

Дініц розробив алгоритм, в якому використовується та ж ідея, що і в алгоритмі Едмондса-Карпа. Але модифікація полягає в тому, що шукається не один найкоротший шлях від джерела до стоку, а відразу кілька шляхів, які утворюють так званий блокуючий потік. 

Отже, щоб зрозуміти ідею Дініца введемо кілька нових понять. Потік називається блокуючим (blocking), якщо кожен шлях від джерела до стоку містить насичене ребро (ребро, по якому рухається потік, рівний пропускній здатності ребра). Величина блокуючого потоку не може бути збільшена шляхом знаходження доповнюючого шляху. Звідси й назва - блокуючий (або замикаючий). Збільшивши потік за допомогою блокуючого потоку можна побудувати кінцеву мережу і збільшувати потік вже в ній, повторюючи процедуру пошуку блокуючого потоку.

Для пошуку блокуючого потоку використовується граф рівня. Нехай - мережа і - потік в ній. Нехай - кінцева мережа. Для кожної вершини знайдемо її рівень ( ) - довжину найкоротшого шляху від джерела до . Графом рівня називається граф , який складається з тих ребер графа , для яких . Іншими словами, граф рівня складається з усіх ребер, які можуть входити в найкоротший шлях від джерела. Такий граф можна побудувати за операцій за допомогою пошуку в ширину.

Алгоритм Дініца працює так: 
Крок 0. Покласти потік рівним нулю ( ). 
Крок 1. Побудувати кінцеву мережу і її граф рівня . Якщо ,то завершити роботу, – шуканий потік.

Інакше, знайти блокуючий потік і перейти до кроку 2. 
Крок 2: Збільшити потік за правилом і перейти до кроку 1.

Теоретична оцінка наступна. 

У довільній мережі алгоритм зійдеться після збільшень потоку вздовж блокуючого.

Це пояснюється тим, що черговий знайдений блокуючий потік збільшує рівень стоку.

1. Він не може бути збільшений більше, ніж на . У по-одиночних мережах алгоритм вимагає всього кроків пошуку блокуючого потоку.

Для пошуку блокуючого потоку Дініц використовував пошук в глибину і знаходив цей потік за операцій у довільній мережі і за операцій – в одиничній. Опишемо його алгоритм. Шукаємо блокуючий потік в графі рівня .

Початок. Покласти і  , блокуючий потік поки дорівнює 0. Перейти на крок «наступ».

Наступ. Якщо немає ребер з вершини , перейти на крок «відступ». Інакше, нехай – ребро, що виходить з . Покласти і . Якщо повторити крок «наступ», якщо ж , перейти на крок «збільшення ».

Збільшення. Нехай , додати до поточного блокуючого потоку вздовж шляху і видалити з всі тільки що насичені ребра. Перейти на «початок ».

Відступ. Якщо закінчити роботу алгоритму. Інакше, нехай останнє ребро на шляху . Видалити з і з . Покласти і перейти на крок «наступ». Отже, загальний час роботи алгоритму пошуку потоку в довільній мережі є . У одиничній – . Значить, в одиничної мережі алгоритм працює дуже швидко. 

Приклад 2.4 Пошук максимального потоку за алгоритмом Дініца

                          Початкова мережа крок 1

Початкова мережу вважаємо нульовим. Шукаємо ланцюг, що може збільшитись. Вершини з нульовим потенціалом виключає з обробки. З решти вершин шукаємо вершину з мінімальним потенціалом. Від неї, переміщаючи відповідний «вантаж» на початок і в кінець мережі, знаходимо псевдомаксімальний потік.

        врахування  кроку 1                         крок 2

Переносимо знайдений потік в мережу і повторюємо все з начала. Зверніть увагу на те, що потік, знайдений на кроці 2 - не максимальний.

врахування кроку 2                     крок 3

Знову переносимо знайдений потік в мережу. Між вершинами 3 та 7 насичуємо потоком одну дугу, а залишок передаємо в іншу.

В знайденій мережі уже неможна знайти ланцюг,що може збільшитись, отже, знайдений потік - максимальний. 

Висновки

В Даній  курсовій роботі були розглянуті основні  поняття про графи, представлення графів в пам’яті ЕОМ, поняття потоку та розрізу у мережі,задача  про максимальний потік в мережі та алгоритми його знаходження. Для розв’язання задачі пошуку максимального потоку в мережі відомо багато різних методів. Самий перший метод в 1956 році винайшли Форд і Фалкересон. Існує багато алгоритмів, які реалізують їх метод і кожен алгоритм має свою складність. Наприклад, є алгоритм, який є частковим випадком алгоритму Форда, який називається алгоритм Едмонса – Карпа(написаний в 1969 році). Час роботи алгоритму складає . Подальший розвиток ідеї Форда і Фалкерсона призвело до появи алгоритму Дініца та ідеї блокуючих потоків. Існує також метод «проштовхування предпотоку» Ідея предпотоку належить Карзанову (1974 р.). Його різні реалізації дають різні оцінки від до . Остання оцінка, досягається алгоритмом «підняти-і-в-начало». Найбільш бистрий алгоритм , що реалізує метод проштовхування розробили Гольдберг і Тарьян (1980 р.).

В ході курсової роботи , мною було розглянуто три алгоритми: алгоритм Форда знаходження максимального потоку, алгоритм Едмондса– Карпа та алгоритм Дініца. Реалізовано програмно алгоритм Форда. Форд і Фалкресон довели, що потік в мережі, для якої не можна побудувати збільшуючий ланцюг, є максимальним. Алгоритм Форда гарантує знаходження максимального потоку тільки в мережах з цілочисловими пропускними спроможностями.  Для знаходження збільшуючого  ланцюга ними  був запропонований   “Метод  розстановки міток”.  Процес  розстановки  міток  починається  в  джерелі  мережі  і закінчується  в  стоці.  Як  тільки  стік  виявився  поміченим, ми  можемо  говорити  про існування збільшуючого  ланцюга з джерела в стік. Мітка, що  “наноситься”  на  вершини мережі, містить необхідний  мінімум інформації,  достатній для того, щоб відновити цей ланцюг  і визначити величину,  на  яку можна змінити потік  в  ній. Вершина  мережі  може  знаходитися  в  одному  з  3-х станів: “непомічена”,  “помічена”  і  “переглянута.

Ідея алгоритму Форда полягає в поступальному нарощуванні потоку через мережу до тих пір, поки його величина не досягне максимуму і подальше збільшення потоку перестане бути можливим.

 

 

Список використаної літератури

1. Акуліч Н.А. Математичне програмування в прикладах і завданнях. - М.: Вища школа, 2003.

2. Іозайтіс В.С., Львов Ю.А. економіко-математичне моделювання виробничих систем. - М.: Вища школа, 2000.

3. Костевич Л.С. , Лапко А.А Теорія ігор. Дослідження  операцій.

–М.: Вища школа, 1982.

4. Н. Крістофідес «теорія графов, алгоритмический подход» Москва, 1978.

5. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2000.

6. A. V. Karzanov. Determining the maximal flow in a network by the method of preflows. – Soviet Mathematics Doklady, 15:434-437, 1974.

7. Вікіпедія.

8. http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/ford-fulkerson-2008