Порівняльний аналіз алгоритмів Форда-Фалкерсона та Дініца для пошуку максимального потоку

Размещено на http://www.allbest.ru/

Порівняльний аналіз алгоритмів Форда-Фалкерсона та Дініца для пошуку максимального потоку

Жиленко Тетяна Іванівна кандидат фізико-математичнх наук, доцент, доцент кафедри математичного аналізу і методів оптимізації, Сумський державний університет

Бабич Злата Андріївна здобувачка вищої освіти факультету електроніки та інформаційних технологій, Сумський державний університет

Штогрін Вячеслав Олександрович здобувач вищої освіти факультету електроніки та інформаційних технологій, Сумський державний університет

Анотація

Важливою проблемою теорії оптимізаї є - створення мереж зв'язку, транспортних та газотранспортних сполучень, які за короткий час можуть пропустити максимальну кількість ресурсів. Тому у роботі розглянуто проблему знаходження максимального потоку в мережі, відому як "maximumnetworkflowproblem", яка виникла на початку двадцятого століття і є актуальною у наш час. У теорії оптимізації та теорії графів проблема побудови мережевих систем і вирішення питання з максимальним потоком виникає постійно. Необхідно знайти такий режим потоку, що забезпечить максимізацію загального потоку у напрямку від джерела до стоку. Для цього було проведено аналіз двох алгоритмів для пошуку максимального потоку в графі: алгоритму Форда-Фалкерсона та алгоритму Дініца. Показано принцип їхньої роботи, а також розглянуті асимптотичні оцінки.

Важливими для алгоритмаФорда-Фалкерсона є: залишкові мережі, шляхи, які постінно збільшуються та розрізи. Також наведено сім кроків його роботи, які унаочнені графами на кожному кроці. Основною метою роботи алгоритму Форда-Фалкерсона є в знаходження шляху від джерела до стоку, де залишкова пропускна здатність усіх ребер буде додатня. Ці ребра можуть бути пройдені як у прямому, так і в зворотньому напрямку.

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

Також у роботі наведено тестові приклади за кожним алгоритмом. Вказані формули для розрахунку часу роботи кожного з алгоритмів. Час залежать від кількості ребер графа і кількості ітерацій. Проведено порівняльний аналіз результатів знаходження часу роботи алгоритмів та зроблено висновок про вдалість використання алгоритму Дініца.

Ключові слова: алгоритм, граф, ребра, джерело, стік, ітерація.

Abstract

ZhylenkoTetianaIvanivnaCandidateofPhysicalandMathematicalSciences, AssociateProfessor, AssociateProfessoroftheDepartmentofMathematicalAnalysisandOptimizationMethods, SumyStateUniversity

BabychZlataAndriivnaPhDcandidate, FacultyofElectronicsandInformation Technologies, SumyStateUniversity

ShtohrinViacheslavOleksandrovichPhDstudent, FacultyofElectronicsandInformation Technologies, SumyStateUniversity

COMPARATIVE ANALYSIS OF THE FORD-FULKERSON AND DIENITS ALGORITHMS FOR SEARCHING FOR THE MAXIMUM

FLOW

Animportantproblemofthetheoryofoptimizationisthecreationofcommunicationnetworks, transportandgastransportconnections, whichcanpassthemaximumamountofresourcesin a shorttime. Therefore, thepaperconsiderstheproblemoffindingthemaximumflowinthenetwork, knownasthe "maximumnetworkflowproblem", whicharoseatthebeginningofthetwentiethcenturyandisrelevantnowadays. Inoptimizationtheoryandgraphtheory, theproblemofbuildingnetworksystemsandsolvingtheproblemwiththemaximumflowarisesconstantly. Itisnecessarytofindsuch a flowregimethatwillensurethemaximizationofthetotalflowinthedirectionfromthesourcetothedrain. Todothis, twoalgorithmsforfindingthemaximumflowin a graphwereanalyzed: the Ford-Fulkerson algorithmandtheDinitzalgorithm. Theprincipleoftheirworkisshown, aswellasasymptoticestimatesareconsidered.

Importantforthe Ford-Fulkerson algorithmare: residualnetworks, everincreasingpaths, andcuts. Alsogivenaresevenstepsofhiswork, whichareillustratedbygraphsateachstep. Themaingoalofthe Ford-Fulkerson algorithmistofind a pathfromthesourcetothesink, wheretheresidualbandwidthofalledgeswillbepositive. Theseribscanbepassedbothintheforwardandreversedirection.

Dinitz'salgorithmisiterativeinnature. Importantforthisalgorithmare: residualnetworks, multilayernetworksandblockingflow. Thealgorithmterminateswiththeflowofthemaximumvalue. Iftheblockingflowisnotfound, thentheleakagecurrentintheauxiliarynetworkcannotbereached, sothecurrentflowwillbemaximum.

Testexamplesforeachalgorithmarealsogiveninthework. Formulasforcalculatingtheoperatingtimeofeachofthealgorithmsareindicated. Thetimedependsonthenumberofedgesofthegraphandthenumberofiterations. A comparativeanalysisoftheresultsoffindingtheoperatingtimeofthealgorithmswascarriedoutand a conclusionwasmadeaboutthesuccessofusingtheDinitzalgorithm.

Keywords: algorithm, graph, edges, source, sink, iteration.

Постановка проблеми

алгоритми форда-фалкерсона дініца зв'язок мережа

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

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

Аналіз останніх досліджень і публікацій. Початок цієї теми припадає на середину 20 століття, коли вчені вперше почали застосовувати математичні концепції для моделювання транспортних систем та комунікаційних мереж. Однією з перших теоретичних робіт, що вказує на проблему максимального потоку, була робота математика та інженера Томаса Кіркмана в 1847 році. Він вивчав проблему потоку в трубопроводах та річковому руслі [1].

Згодом, після появи теорії графів у середині 20 століття, проблема максимального потоку стала центральним об'єктом досліджень. Алгоритми та методи розв'язання цієї проблеми стали необхідними для ефективного управління мережами в різних галузях.

Мета статті -розглянути та порівняти алгоритми Форда-Фалкерсона і Дініца. Визначити найбільш швидкий та вдалий алгоритм.

Виклад основного матеріалу

Алгоритм Форда-Фалкерсона був представлений у першому звіті, який датується 19 листопада 1954 року, і має авторів Форда і Фалкерсона [2]. У цьому звіті вони довели теорему про максимальний потік і мінімальний розріз для неорієнтованих графів: значення максимального потоку в мережі дорівнює мінімальній пропускній здатності розрізу.

Робота Форда і Фалкерсона в області потоків і розрізів була обумовлена дослідженням транспортних мереж залізниць. У тому ж звіті вони також представили простий алгоритм знаходження максимального потоку для планарних графів, що володіють деякими додатковими властивостями.

Алгоритм Форда-Фалкерсона для вирішення проблеми "maximumnetworkflowproblem" базується на трьох ключових концепціях:

1. Залишкові мережі: Вони визначаються як мережі, які виникають під час пошуку максимального потоку.

2. Шляхи, що збільшуються: Алгоритм шукає шляхи в залишкових мережах, які дозволяють збільшити потік в мережі.

3. Розрізи: Використовуються для знаходження мінімального розрізу у мережі.

Залишковою пропускною спроможністю ребра (u, v) називається додатковий потік, який можна направити з вершини u в вершину v, не перевищуючи пропускну спроможність c(u, v). Іншими словами, cf(u, v) = c(u, v) - f(u, v).



Рис. 1. Граф з неповним потоком

Рис.2. Залишкова мережа графа

"Шлях, що збільшується", це будь-який маршрут в залишковій мережі, що виходить з джерела s і завершується в стоку t, де ребра мають властивість: потік через кожне ребро (ui, vj) не перевищує його пропускної здатності, тобто f(ui, vj) < c(ui, vj).

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

Рис.3. Приклад розрізу графу

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

Кроки алгоритму Форда-Фалкерсона:

1. Початкові значення потоку встановлюються на нуль: f(ui,vj) = 0 для всіх u, v у множині вершин V.

2. На кожній ітерації величина потоку збільшується шляхом пошуку "шляху, що збільшується", тобто шляху від джерела s до стоку t, де можна направити більший потік. Якщо такого шляху немає, то потік в мережі максимальний.

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

4. На знайденому шляху в залишковій мережі шукається ребро з мінімальною пропускною здатністю Cmin.

5. Для кожного ребра на знайденому шляху збільшується потік на Cmin, а для зворотного потоку зменшується на Cmin.

6. Модифікується залишкова мережа. Для всіх ребер на знайденому шляху обчислюється нова пропускна здатність. Якщо нова пропускна здатність не рівна нулю, то ребро додається до залишкової мережі, в іншому випадку воно видаляється.

7. Повернення на крок 2.

Представимо роботу алгоритну на прикладі задачі по знаходженню максимального потоку в графі за допомогою алгоритму Форда-Фалкерсона.



Рис. 4. Початковий граф

Рис. 4.1. Початкова задишкова мережа

Рис. 4.2. Залишкова мережа після 1-ї ітерації

Рис.4.3. Проведення 2-ї ітерації



Рис. 4.4. Залишкова мережа після 2-ї ітерації

Рис. 4.5. Проведення 3-ї ітерації

Рис. 4.6. Залишковамережа після 3-ї ітерації

Рис.4.7. Проведення 4-ї ітерації

Рис.4.8. Результуюча залишкова мережа

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

Алгоритм Дініца, запропонований Юхимом Дініцем у 1970 році, є поліноміальним методом для визначення максимального потоку в транспортній мережі. Цей алгоритм має величезне значення, оскільки сприяв подальшим дослідженням та вдосконаленням асимптотичних оцінок в цій області. На той момент усі покращення у вирішенні задачі про максимальний потік ґрунтувалися на ідеях алгоритму Дініца [3].

Цей алгоритм носить ітеративний підхід та базується на трьох ключових концепціях:

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

2. Багатошарові мережі: За допомогою довжин найкоротших шляхів від джерела s до кожної вершини v визначається багатошарова мережа. Тут враховуються лише ребра, для яких довжина шляху визначає їхній "шар" у мережі.

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

Зокрема, визначаючи багатошарові мережі, вводиться довжина найкоротшого шляху для кожної вершини, що дозволяє створити ациклічну мережу, де кожен s-t іп.іях є най корон ним шляхом в початковій мережі.

Рис.5. Багатошарова мережа

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

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

Покроковий алгоритм Дініца:

1. Побудова залишкової мережі для вихідного графа.

2.1. Знаходження найдовший шлях від витоку до стоку. Якщо шлях відсутній - закінчення циклу.

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

2.3. . Збільшення потоку на знайденому шляху на Cmin, а для зворотнього потоку - зменшення його на Cmin.

2.4. Видалення насичених ребер та видалення вершин без виходів або входів.

2.5. Повторення попереднього кроку, доки можливо видалення.

3. Якщо знайдений потік не дорівнює нулю, додавання його до загального потоку і повернення на крок 1.

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



Рис. 6.1.Проведення 1-ї ітерації

Блокуючий потік складається з шляхів:

1. {s,1,3,t} з 4 од. Потоку

2. {s,1,4,t} з 6 од. Потоку

3. {s,2,4,t} з 4 од. Потоку

Отже, блокуючий потік містить 14 одиниць, а величина потоку дорівнює 14. Зауважимо, що доповнюючий шлях має 3 ребра.

Рис.6.2. Проведення 2-ї ітерації

Блокуючий потік складається з шляхів:

1.{s,2,4,3,t} з 5 од. потоку

Тож блокуючий потік містить 5 одиниць, а величина потоку дорівнює

14 + 5 = 19. Зауважимо, що доповнюючий шлях має 4 ребра.

Рис.6.3. Проведення 3-ї ітерації

Сток t недосягнутий в залишковій мережі Gf. Таким чином, алгоритм завершує свою роботу і повертає максимальний потік розміром 19. Важливо відзначити, що в кожному блокуючому потоці кількість ребер у доповнюючому шляху збільшується хоча б на одне.



Тестовий приклад за алгоритмом Форда-Фалкерсона

Тестовий приклад за алгоритмом Дініца

Асимптотика алгоритму Форда-Фалкерсона.

Максимальний потік буде знайдено не більш ніж за O(F) ітерацій, де F - максимальний потік у мережі. Кожна ітерація вимагає О(Е) часу, де E - число ребер у мережі. Отже загальний час роботи алгоритму: O(E-F).

Асимптотика алгоритму Дініца

В алгоритмі Дініца щоразу кількість ребер у блокуючому потоці збільшується принаймні на одне, тому в алгоритмі не більше V-1 блокуючих потоків. Допоміжна мережа Gl може бути побудована обходом у ширину за час O(E), а блокуючий потік на кожному рівні графа може бути знайдений за час O(VE). Таким чином, можемо зробити висновок, що час роботи алгоритму Дініца дорівнює O(V) * (O(E) + O(VE)) = O(V²E).

Таблиця 2.Порівняльна таблиця тестових прикладів

Висновки

Отже ми ретельно розглянули та порівняли два алгоритми пошуку максимального потоку в транспортній мережі: алгоритми Форда-Фалкерсона та Дініца. Також були розглянуті принципи їх роботи та проведено порівняльний аналіз асимптотичних оцінок.

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

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

Література

1. Dinic'salgorithmforMaximumFlow. [Електронний ресурс] - Режим доступу до ресурсу: https://www.geeksforgeeks.org/dinics-algorithm-maximum-flow/

2. Paul E. Black. DictionaryofAlgorithmsandDataStructures [Електронний ресурс] - Режим доступу до ресурсу: https://xlinux.nist.gov/dads/

3 Hochbaum D., S. . LectureNotesfor IEOR 266: GraphAlgorithmsandNetworkFlows [Електронний ресурс] - Режим доступу до ресурсу: https://hochbaum.ieor.berkeley.edu/ files/ieor266-2014.pdf

References

1. Dinic'salgorithmforMaximumFlow. [Електронний ресурс] - Режим доступу до ресурсу: https://www.geeksforgeeks.org/dinics-algorithm-maximum-flow/

2. Paul E. Black. DictionaryofAlgorithmsandDataStructures - Режим доступу до ресурсу: https://xlinux.nist.gov/dads/

3 Hochbaum D., S. . LectureNotesfor IEOR 266: GraphAlgorithmsandNetworkFlows https://hochbaum.ieor.berkeley.edu/files/ieor266-2014.pdf

Размещено на Allbest.ru

...