В теорії оптимізації та теорії графів, задача про максимальний потік полягає у знаходженні такого (потоку) за транспортною мережею, щоб сума потоків з витоку, або, що означає те ж саме, сума потоків до стоку була максимальна.
Задача про максимальний потік є окремим випадком більш складних задач, таких, як, наприклад, задача про циркуляцію.
Історія
Після вступу США у Другу світову війну у 1941 році математик Джордж Бернард Данціг почав працювати у відділі статистичного управління Військово-повітряних сил США у Вашингтоні. З 1941 по 1946 роки він очолював підрозділ аналізу військових дій (Combat Analysis Branch), де працював над різноманітними математичними проблемами. Згодом з використанням роботи Данцига задача про максимальний потік була вперше розв'язана у ході підготовки повітряного мосту під час Берлінського повітряного мосту, що відбувався у 1948–1949 роках.
У 1951 році Джордж Данциг вперше сформулював задачу у загальному вигляді.
У 1955 році [en] і [en] вперше побудували алгоритм, призначений для вирішення цього завдання. Їх алгоритм отримав назву алгоритм Форда — Фалкерсона.
Надалі рішення задачі багато разів поліпшувалося.
У 2010 році дослідники Джонатан Келнер (Jonathan Kelner) і Олександр Мондри (Aleksander Mądry) з МТІ разом зі своїми колегами Даніелєм Спілманом з Єльського університету і [en] з університету Південної Каліфорнії продемонстрували чергове покращення алгоритму, вперше за 10 років.
Визначення
Розглянемо транспортну мережу з джерелом , стоком та пропускними здатностями .
- Величиною (потоку) (value of flow) називається сума потоків з джерела . У статті «Транспортна мережа» доведено, що вона дорівнює сумі потоків у сток .
Задача про максимальний потік полягає в знаходженні потоку такого, щоб величина потоку була максимальна.
Розв'язання
В таблиці перераховано деякі алгоритми розв'язування задачі.
Метод | Складність | Опис |
---|---|---|
Лінійне програмування | Залежить від конкретного алгоритму. Для симплекс-методу експоненціальна. | Розглянемо задачу про максимальний потік як задачу лінійного програмування. Змінними є потоки по ребрах, а обмеженнями — збереження потоку й обмеження пропускної здатності. |
Алгоритм Форда — Фалкерсона | Залежить від алгоритму пошуку шляху, що збільшується. Потребує O(max| f |) таких пошуків. | Знайти будь-який шлях, що збільшується. Збільшити потік по всіх його ребрах на мінімальну з їх залишкових пропускних здатностей. Повторювати, поки є шлях, що збільшується. Алгоритм працює тільки для цілих пропускних здатностей. В іншому випадку, він може працювати нескінченно довго, не сходячись до правильної відповіді. |
Алгоритм Едмондса-Карпа | O(VE²) | Виконуємо алгоритм Форда — Фалкерсона, щоразу обираючи найкоротший шлях, що збільшується (знаходиться пошуком у ширину). |
Алгоритм Дініца | O(V²E) для одиничних пропускних здатностей з використанням динамічних дерев Слетора і Тар'яна | Удосконалення алгоритму Едмондса-Карпа (але хронологічно був знайдений раніше). На кожній ітерації, використовуючи пошук у ширину, визначаємо відстані від джерела до всіх вершин у залишковій мережі. Будуємо граф, який містить лише такі ребра залишкової мережі, на яких ця відстань зростає на 1. Виключаємо з графу усі тупикові вершини з інцидентними їм ребрами, поки всі вершини стануть не тупиковими. (Тупиковою називається вершина, в яку не входить і з якої не виходить жодне ребро, крім джерела і стоку.) На отриманому графі відшукуємо найкоротший шлях, що збільшується (їм буде будь-який шлях з s в t). Виключаємо із залишкової мережі ребро з мінімальною пропускною здатністю, знову виключаємо тупикові вершини, і так поки ще існують шляхи, що збільшуються. |
[en] | O(V²E) | Замість потоку оперує з передпотоком. Різниця в тому, що для будь-якої вершини u, крім джерела і стоку, сума потоків, що входять до неї для потоку повинна бути строго нульовою (умова збереження потоку), а для передпотока — невід'ємною. Ця сума називається надмірним потоком у вершину, а вершина з позитивним надмірним потоком називається переповненою . Крім того, для кожної вершини алгоритм зберігає додаткову характеристику, висоту, яка є цілим невід'ємним числом. Алгоритм використовує дві операції: просування , коли потік по ребру, що йде з більш високої в нижчу вершину, збільшується на максимально можливу величину, і підйом , коли переповнена вершина, просування з якої неможливо через недостатню висоту, підіймається. Просування можливо, коли ребро належить залишковій мережі, коли воно веде з більш високої вершини в більш низьку, і вихідна вершина переповнена. Підйом можливий, коли вершина, що піднімається, переповнена, але жодна з вершин, в котру з неї ведуть ребра залишкової мережі, не нижче за неї. Він вчиняється до висоти на 1 більшою, ніж мінімальна з висот цих вершин. Спочатку висота джерела V, по всім ребрам, що виходять з джерела, тече максимально можливий потік, а решта висоти і потоки нульові. Операція просування і підйому виконуються до тих пір, поки це можливо. |
[en] | O(V³) O(VE log(V²/E)) з використанням динамічних дерев | Варіант попереднього алгоритму, що спеціальним чином визначає порядок операцій просовування і підйому. |
Алгоритм двійкового блокуючого потоку [1] |
Для детальнішого списку, див. [2].
Теорема про цілий потік
Якщо пропускні спроможності цілі, максимальна величина потоку теж ціла.
Теорема випливає, наприклад, з теореми Форда — Фалкерсона.
Узагальнення, що зводяться до вихідної задачі
Деякі узагальнення задачі про максимальний потік легко зводяться до вихідної задачі.
Довільне число джерел та / або стоків
Якщо джерел більше одного, додаємо нову вершину S, яку робимо єдиним джерелом. Додаємо ребра з нескінченною пропускною здатністю від S до кожного зі старих джерел.
Аналогічно, якщо стоків більше одного, додаємо нову вершину T, яку робимо єдиним стоком. Додаємо ребра з нескінченною пропускною здатністю від кожного зі старих стоків до T.
Неорієнтовані ребра
Кожне неорієнтоване ребро (u, v) замінюємо на пару орієнтованих ребер (u, v) і (v, u).
Обмеження пропускної здатності вершин
Кожну вершину v з обмеженою пропускною здатністю розщеплюємо на дві вершини vin і vout. Всі ребра, які до розщеплення входять до v, тепер входять в vin. Всі ребра, які до розщеплення виходять з v, тепер виходять з vout. Додаємо ребро (vin,vout) з пропускною здатністю .
Див. також
Примітки
- Джон Дж. О'Коннор та Едмунд Ф. Робертсон. George Dantzig в архіві MacTutor (англ.)
- Cottle, Richard; Johnson, Ellis; Wets, Roger, «George B. Dantzig (1914–2005)» [ 7 вересня 2015 у Wayback Machine.], Notices of the American Mathematical Society, v.54, no.3, March 2007. Cf. p.348
- Hardesty, Larry, «First improvement of fundamental algorithm in 10 years» [ 28 березня 2014 у Wayback Machine.], MIT News Office, September 27, 2010
- Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas, «Alcuin's Transportation Problems and Integer Programing» [ 7 серпня 2011 у Wayback Machine.], Konrad-Zuse-Zentrum für Informationstechnik, Berlin, Germany, November 1995. Cf. p.3
- Powell, Stewart M., «The Berlin Airlift», Air Force Magazine, June 1998.
- Dantzig, G.B., «Application of the Simplex Method to a Transportation Problem» [ 19 липня 2010 у Wayback Machine.], in T.C. Koopman (ed.): Activity Analysis and Production and Allocation, New York, (1951) 359–373.
- Ford, L.R., Jr.; Fulkerson, D.R., «Maximal Flow through a Network», Canadian Journal of Mathematics (1956), pp.399-404.
- Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
- Kelner, Jonathan, «Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs» [ 24 червня 2011 у Wayback Machine.], talk at CSAIL, MIT, Tuesday, September 28 2010
- Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs [ 29 листопада 2010 у Wayback Machine.], by Paul Cristiano et al., October 19, 2010.
- . Архів оригіналу за 7 травня 2015. Процитовано 18 травня 2015.
Література
- Schrijver, Alexander, «On the history of the transportation and maximum flow problems» [ 10 листопада 2014 у Wayback Machine.], Mathematical Programming 91 (2002) 437—445
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. 26. Максимальний потік. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- ↑ [en] and S. Rao (1998). Beyond the flow decomposition barrier. J. Assoc. Comput. Mach. 45: 753—782. doi:10.1145/290179.290181.
- ↑ [en] and Robert E. Tarjan (1988). A new approach to the maximum-flow problem. Journal of the ACM. New York, New York, U.S.: ACM Press. 35 (4): 921—940. doi:10.1145/48014.61051. ISSN 0004-5411.
- ↑ and Kurt Mehlhorn (1999). An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters. 69 (5): 239—242. doi:10.1016/S0020-0190(99)00019-8.
- ↑ Daniel D. Sleator and Robert E. Tarjan (1983). (PDF). Journal of Computer and System Sciences. 26 (3): 362—391. doi:10.1016/0022-0000(83)90006-5. ISSN 0022-0000. Архів оригіналу (PDF) за 14 травня 2015. Процитовано 18 травня 2015.
- ↑ Daniel D. Sleator and Robert E. Tarjan (1985). (PDF). Journal of the ACM. New York, New York, U.S.: ACM Press. 32 (3): 652—686. doi:10.1145/3828.3835. ISSN 0004-5411. Архів оригіналу (PDF) за 5 березня 2015. Процитовано 18 травня 2015.
- (2001). 4. Network Flows. Combinatorial Optimization: Networks and Matroids. Dover. с. 109—177. ISBN .
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V teoriyi optimizaciyi ta teoriyi grafiv zadacha pro maksimalnij potik polyagaye u znahodzhenni takogo potoku za transportnoyu merezheyu shob suma potokiv z vitoku abo sho oznachaye te zh same suma potokiv do stoku bula maksimalna Maksimalnij potik v transportnij merezhi Chisla poznachayut potoki i propuskni vlastivosti Zadacha pro maksimalnij potik ye okremim vipadkom bilsh skladnih zadach takih yak napriklad zadacha pro cirkulyaciyu IstoriyaPislya vstupu SShA u Drugu svitovu vijnu u 1941 roci matematik Dzhordzh Bernard Dancig pochav pracyuvati u viddili statistichnogo upravlinnya Vijskovo povitryanih sil SShA u Vashingtoni Z 1941 po 1946 roki vin ocholyuvav pidrozdil analizu vijskovih dij Combat Analysis Branch de pracyuvav nad riznomanitnimi matematichnimi problemami Zgodom z vikoristannyam roboti Danciga zadacha pro maksimalnij potik bula vpershe rozv yazana u hodi pidgotovki povitryanogo mostu pid chas Berlinskogo povitryanogo mostu sho vidbuvavsya u 1948 1949 rokah U 1951 roci Dzhordzh Dancig vpershe sformulyuvav zadachu u zagalnomu viglyadi U 1955 roci en i en vpershe pobuduvali algoritm priznachenij dlya virishennya cogo zavdannya Yih algoritm otrimav nazvu algoritm Forda Falkersona Nadali rishennya zadachi bagato raziv polipshuvalosya U 2010 roci doslidniki Dzhonatan Kelner Jonathan Kelner i Oleksandr Mondri Aleksander Madry z MTI razom zi svoyimi kolegami Danielyem Spilmanom z Yelskogo universitetu i en z universitetu Pivdennoyi Kaliforniyi prodemonstruvali chergove pokrashennya algoritmu vpershe za 10 rokiv ViznachennyaRozglyanemo transportnu merezhu N V E displaystyle scriptstyle N V E z dzherelom s V displaystyle scriptstyle s in V stokom t V displaystyle scriptstyle t in V ta propusknimi zdatnostyami c displaystyle scriptstyle c Velichinoyu potoku value of flow nazivayetsya suma potokiv z dzherela f v Vfsv displaystyle scriptstyle f sum v in V f sv U statti Transportna merezha dovedeno sho vona dorivnyuye sumi potokiv u stok w Vf w t displaystyle sum w in V f w t Zadacha pro maksimalnij potik polyagaye v znahodzhenni potoku takogo shob velichina potoku bula maksimalna Rozv yazannyaV tablici pererahovano deyaki algoritmi rozv yazuvannya zadachi Metod Skladnist OpisLinijne programuvannya Zalezhit vid konkretnogo algoritmu Dlya simpleks metodu eksponencialna Rozglyanemo zadachu pro maksimalnij potik yak zadachu linijnogo programuvannya Zminnimi ye potoki po rebrah a obmezhennyami zberezhennya potoku j obmezhennya propusknoyi zdatnosti Algoritm Forda Falkersona Zalezhit vid algoritmu poshuku shlyahu sho zbilshuyetsya Potrebuye O max f takih poshukiv Znajti bud yakij shlyah sho zbilshuyetsya Zbilshiti potik po vsih jogo rebrah na minimalnu z yih zalishkovih propusknih zdatnostej Povtoryuvati poki ye shlyah sho zbilshuyetsya Algoritm pracyuye tilki dlya cilih propusknih zdatnostej V inshomu vipadku vin mozhe pracyuvati neskinchenno dovgo ne shodyachis do pravilnoyi vidpovidi Algoritm Edmondsa Karpa O VE Vikonuyemo algoritm Forda Falkersona shorazu obirayuchi najkorotshij shlyah sho zbilshuyetsya znahoditsya poshukom u shirinu Algoritm Dinica O V E O VE displaystyle scriptscriptstyle O V sqrt E dlya odinichnih propusknih zdatnostej O VElog V displaystyle O VE log V z vikoristannyam dinamichnih derev Sletora i Tar yana Udoskonalennya algoritmu Edmondsa Karpa ale hronologichno buv znajdenij ranishe Na kozhnij iteraciyi vikoristovuyuchi poshuk u shirinu viznachayemo vidstani vid dzherela do vsih vershin u zalishkovij merezhi Buduyemo graf yakij mistit lishe taki rebra zalishkovoyi merezhi na yakih cya vidstan zrostaye na 1 Viklyuchayemo z grafu usi tupikovi vershini z incidentnimi yim rebrami poki vsi vershini stanut ne tupikovimi Tupikovoyu nazivayetsya vershina v yaku ne vhodit i z yakoyi ne vihodit zhodne rebro krim dzherela i stoku Na otrimanomu grafi vidshukuyemo najkorotshij shlyah sho zbilshuyetsya yim bude bud yakij shlyah z s v t Viklyuchayemo iz zalishkovoyi merezhi rebro z minimalnoyu propusknoyu zdatnistyu znovu viklyuchayemo tupikovi vershini i tak poki she isnuyut shlyahi sho zbilshuyutsya en O V E Zamist potoku operuye z peredpotokom Riznicya v tomu sho dlya bud yakoyi vershini u krim dzherela i stoku suma potokiv sho vhodyat do neyi dlya potoku povinna buti strogo nulovoyu umova zberezhennya potoku a dlya peredpotoka nevid yemnoyu Cya suma nazivayetsya nadmirnim potokom u vershinu a vershina z pozitivnim nadmirnim potokom nazivayetsya perepovnenoyu Krim togo dlya kozhnoyi vershini algoritm zberigaye dodatkovu harakteristiku visotu yaka ye cilim nevid yemnim chislom Algoritm vikoristovuye dvi operaciyi prosuvannya koli potik po rebru sho jde z bilsh visokoyi v nizhchu vershinu zbilshuyetsya na maksimalno mozhlivu velichinu i pidjom koli perepovnena vershina prosuvannya z yakoyi nemozhlivo cherez nedostatnyu visotu pidijmayetsya Prosuvannya mozhlivo koli rebro nalezhit zalishkovij merezhi koli vono vede z bilsh visokoyi vershini v bilsh nizku i vihidna vershina perepovnena Pidjom mozhlivij koli vershina sho pidnimayetsya perepovnena ale zhodna z vershin v kotru z neyi vedut rebra zalishkovoyi merezhi ne nizhche za neyi Vin vchinyayetsya do visoti na 1 bilshoyu nizh minimalna z visot cih vershin Spochatku visota dzherela V po vsim rebram sho vihodyat z dzherela teche maksimalno mozhlivij potik a reshta visoti i potoki nulovi Operaciya prosuvannya i pidjomu vikonuyutsya do tih pir poki ce mozhlivo en O V O VE log V E z vikoristannyam dinamichnih derev Variant poperednogo algoritmu sho specialnim chinom viznachaye poryadok operacij prosovuvannya i pidjomu Algoritm dvijkovogo blokuyuchogo potoku 1 O Emin V2 3 E log V2 E log max f displaystyle scriptscriptstyle O E min V 2 3 sqrt E log V 2 E log max f Dlya detalnishogo spisku div 2 Teorema pro cilij potikYaksho propuskni spromozhnosti cili maksimalna velichina potoku tezh cila Teorema viplivaye napriklad z teoremi Forda Falkersona Uzagalnennya sho zvodyatsya do vihidnoyi zadachiDeyaki uzagalnennya zadachi pro maksimalnij potik legko zvodyatsya do vihidnoyi zadachi Dovilne chislo dzherel ta abo stokiv Transformaciya zadachi z dovilnoyu kilkist dzherel i stokiv do pochatkovoyi zadachi Yaksho dzherel bilshe odnogo dodayemo novu vershinu S yaku robimo yedinim dzherelom Dodayemo rebra z neskinchennoyu propusknoyu zdatnistyu vid S do kozhnogo zi starih dzherel Analogichno yaksho stokiv bilshe odnogo dodayemo novu vershinu T yaku robimo yedinim stokom Dodayemo rebra z neskinchennoyu propusknoyu zdatnistyu vid kozhnogo zi starih stokiv do T Neoriyentovani rebra Kozhne neoriyentovane rebro u v zaminyuyemo na paru oriyentovanih reber u v i v u Obmezhennya propusknoyi zdatnosti vershin Transformaciya zadachi z obmezhenoyu propusknoyu zdatnistyu vershin do pochatkovoyi zadachi shlyahom rozsheplennya vershin Kozhnu vershinu v z obmezhenoyu propusknoyu zdatnistyu cv displaystyle c v rozsheplyuyemo na dvi vershini vin i vout Vsi rebra yaki do rozsheplennya vhodyat do v teper vhodyat v vin Vsi rebra yaki do rozsheplennya vihodyat z v teper vihodyat z vout Dodayemo rebro vin vout z propusknoyu zdatnistyu cv displaystyle c v Div takozhPotokova merezhaPrimitkiDzhon Dzh O Konnor ta Edmund F Robertson George Dantzig v arhivi MacTutor angl Cottle Richard Johnson Ellis Wets Roger George B Dantzig 1914 2005 7 veresnya 2015 u Wayback Machine Notices of the American Mathematical Society v 54 no 3 March 2007 Cf p 348 Hardesty Larry First improvement of fundamental algorithm in 10 years 28 bereznya 2014 u Wayback Machine MIT News Office September 27 2010 Borndorfer Ralf Grotschel Martin Lobel Andreas Alcuin s Transportation Problems and Integer Programing 7 serpnya 2011 u Wayback Machine Konrad Zuse Zentrum fur Informationstechnik Berlin Germany November 1995 Cf p 3 Powell Stewart M The Berlin Airlift Air Force Magazine June 1998 Dantzig G B Application of the Simplex Method to a Transportation Problem 19 lipnya 2010 u Wayback Machine in T C Koopman ed Activity Analysis and Production and Allocation New York 1951 359 373 Ford L R Jr Fulkerson D R Maximal Flow through a Network Canadian Journal of Mathematics 1956 pp 399 404 Ford L R Jr Fulkerson D R Flows in Networks Princeton University Press 1962 Kelner Jonathan Electrical Flows Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs 24 chervnya 2011 u Wayback Machine talk at CSAIL MIT Tuesday September 28 2010 Electrical Flows Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs 29 listopada 2010 u Wayback Machine by Paul Cristiano et al October 19 2010 Arhiv originalu za 7 travnya 2015 Procitovano 18 travnya 2015 LiteraturaSchrijver Alexander On the history of the transportation and maximum flow problems 10 listopada 2014 u Wayback Machine Mathematical Programming 91 2002 437 445 Tomas Kormen Charlz Lejzerson Ronald Rivest Kliford Stajn 2009 1990 26 Maksimalnij potik Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 en and S Rao 1998 Beyond the flow decomposition barrier J Assoc Comput Mach 45 753 782 doi 10 1145 290179 290181 en and Robert E Tarjan 1988 A new approach to the maximum flow problem Journal of the ACM New York New York U S ACM Press 35 4 921 940 doi 10 1145 48014 61051 ISSN 0004 5411 and Kurt Mehlhorn 1999 An analysis of the highest level selection rule in the preflow push max flow algorithm Information Processing Letters 69 5 239 242 doi 10 1016 S0020 0190 99 00019 8 Daniel D Sleator and Robert E Tarjan 1983 PDF Journal of Computer and System Sciences 26 3 362 391 doi 10 1016 0022 0000 83 90006 5 ISSN 0022 0000 Arhiv originalu PDF za 14 travnya 2015 Procitovano 18 travnya 2015 Daniel D Sleator and Robert E Tarjan 1985 PDF Journal of the ACM New York New York U S ACM Press 32 3 652 686 doi 10 1145 3828 3835 ISSN 0004 5411 Arhiv originalu PDF za 5 bereznya 2015 Procitovano 18 travnya 2015 2001 4 Network Flows Combinatorial Optimization Networks and Matroids Dover s 109 177 ISBN 0486414531 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi