Czy któryś z najnowszych algorytmów maksymalnego przepływu jest praktyczny?

30

W przypadku problemu maksymalnego przepływu wydaje się, że istnieje wiele bardzo wyrafinowanych algorytmów, przy czym co najmniej jeden opracowano dopiero w zeszłym roku. Max przepływy Orlina w czasie O (mn) lub lepiej daje algorytm działający w O (VE).

Z drugiej strony algorytmy, które najczęściej widzę, są zaimplementowane (nie twierdzę, że przeprowadziłem wyczerpujące wyszukiwanie; to tylko przypadkowa obserwacja):

  • Edmonds-Karp: ,O(V.mi2))
  • Push-relabel: lub O ( V 3 ) przy użyciu wyboru wierzchołków FIFO,O(V.2)mi)O(V.3))
  • Algorytm Dinica: .O(V.2)mi)

Czy algorytmy z lepszym asymptotycznym czasem działania są po prostu niepraktyczne dla rozmiarów problemów w świecie rzeczywistym? Widzę też, że „Drzewa dynamiczne” są zaangażowane w wiele algorytmów; czy są one kiedykolwiek stosowane w praktyce?

Uwaga: to pytanie zostało pierwotnie zadane przy przepełnieniu stosu, tutaj , ale powiedziano mi, że będzie lepiej tutaj pasować.

EDYCJA : Zadałem powiązane pytanie na temat cs.stackexchange , w szczególności na temat algorytmów wykorzystujących drzewa dynamiczne (inaczej drzewa cięte łączem), które mogą być interesujące dla osób podążających za tym pytaniem.

ds.algorithms graph-algorithms application-of-theory max-flow Rob Lachlan
źródło
1
mówiąc ogólnie, to, czy algorytm jest „praktyczny” w porównaniu z tym, czy jest „zaimplementowany”, są nieco inne. idealnie, autorzy opublikowaliby implementacje własnych algorytmów, w którym to przypadku zwykle byłoby „praktyczne” ich użycie. mimo że jest to często wyjątek w literaturze TCS. ale często nie „praktyczne” jest „wdrażanie” algorytmów innych autorów, których opisy podano tylko w pismach napisanych pseudokodem, które są czasem znacznie lub bardzo złożone… pomyślna implementacja obejmuje dobre testowanie poprawności, czasem zniechęcający proces…
vzn
3
Andrew Goldberg miał kiedyś bardzo dobrą bazę kodu dla różnych wariantów maksymalnego przepływu w oparciu o swoją pracę z etykietą push. Używałem kodu w przeszłości i był bardzo czysty. Niestety strona wydaje się nieczynna.
Suresh Venkat
3
@vzn Interesuje mnie, czy algorytmy w ogóle nadają się do praktycznej implementacji. Istnieją algorytmy, które tego nie robią, a niektórzy ludzie nazywają te „algorytmy galaktyczne”, ponieważ mają doskonałe zachowanie asymptotyczne, ale na tyle narzut, że obecnie nie ma praktycznych korzyści z ich wdrożenia. (W końcu znaczenie mają terminy niższego rzędu). Mnożenie macierzy jest najlepszym przykładem, jaki mogę wymyślić, gdzie asymptotycznie najlepsze rozwiązania nigdy nie znajdują praktycznego zastosowania. Jestem ciekawy, czy Max flow jest podobną sytuacją.
Rob Lachlan
5
czy algorytm jest „praktyczny” w porównaniu z tym, czy jest „zaimplementowany”, są nieco inne. - To jest poprawne. Algorytm można wdrożyć bez praktyczności, ale nie odwrotnie.
Jeffε
2
Oto kod z eksperymentalnego badania algorytmów cięcia minimalnego .
Austin Buchanan,

Odpowiedzi:

22

Jestem jednym z autorów powyższego artykułu.

Chcę tylko wspomnieć, że użyliśmy `` najnowocześniejszych '', aby oznaczać algorytmy (z publicznie dostępnymi implementacjami), które działają dobrze na instancjach o maksymalnym przepływie powstających w wizji komputerowej.

Chciałbym również dodać, że w tym wąskim (ale praktycznym) kontekście często algorytmy, które działają dobrze, są tymi, które mają słabe gwarancje teoretyczne. Na przykład ref [5] z naszego artykułu (algorytm Bojkowa-Kołmogorowa) jest szeroko stosowany w środowisku komputerowym, ale nie ma silnie związanego z nim czasu działania.

Wreszcie, jeśli ktoś jest zainteresowany, dane z naszych eksperymentów są dostępne tutaj: http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

Wkrótce również będzie dostępny kod.

Dhruv Batra
źródło
bardzo fajnie, że dołączyłeś do grupy! Witamy! jedno pytanie dotyczące pracy [od pierwszego znalezienia]. bardzo interesujące byłoby usłyszeć więcej o procesie selekcji algorytmów zastosowanych w artykule - nie wydaje się, aby w pełni je rozwinąć. może mógłbyś gdzieś podzielić się „zakulisowymi” notatkami w tle [np. strona internetowa?] o tym, które algorytmy zostały wybrane, które zostały pominięte, dlaczego, jakie były trudności w uzyskaniu / uruchomieniu implementacji, co myślisz o bardziej egzotycznych algorytmy, takie jak najnowszy Orlins i ich szanse na ostateczne wdrożenie, itp.!
wzn
7

istnieje kilka sposobów na udzielenie odpowiedzi na to pytanie, ale niekoniecznie odpowiedź konsensusu. ogólnie algorytmy, które zostały zaimplementowane i udostępnione do publicznej dystrybucji, są „praktyczne”. jednak niektóre algorytmy, które zostały opracowane, ale jeszcze nie wdrożone, mogą być praktyczne, ale można powiedzieć, że „nie ma jury”.

dobrą strategią do celów praktycznych jest poszukiwanie ankiety. również dla osób zainteresowanych praktycznymi algorytmami testy porównawcze w stosunku do rzeczywistych danych mogą być doskonałą wskazówką dotyczącą ich oczekiwanego zachowania w „prawdziwym świecie”.

badanie porównawcze może być wystarczające, ale będzie błędne ze strony wykonalnych algorytmów. jest to ostatnia, gruntowna analiza empiryczna 14 „najnowocześniejszych” algorytmów maksymalnego przepływu porównanych empirycznie z instancjami przetwarzania obrazu, w których maksymalny przepływ ma wiele zastosowań. „stan techniki” odnosi się do „wdrożonych” algorytmów.

[1] Weryfikacja MaxFlow: empiryczne porównanie algorytmów Maxflow dla problemów z gęstym widzeniem, Verma i Batra, 2012

** niektóre algorytmy teoretyczne są coraz częściej zaliczane do kategorii w społeczności TCS, która jest nieformalnie nazywana „galaktyczną”, ale niestety autorzy TCS obecnie nie określają wprost swoich algorytmów w tej kategorii i nie ma opublikowanych ani ogólnie przyjętych kryteriów dla algorytmy „galaktyczne”, choć na blogach znajduje się odniesienie .

praktyczność w tym sensie jest prawdopodobnie nowym wyłaniającym się wymiarem dla studiów teoretycznych. idealnie byłoby przeprowadzenie badania algorytmów maksymalnego przepływu specjalnie na tej „praktycznej” osi / kryteriach, ale prawdopodobnie nie istnieje ona w chwili pisania. jest to niedawno uznana / uznana koncepcja w TCS, która nie została jeszcze gruntownie sformalizowana (w przeciwieństwie np. do powszechnej akceptacji algorytmów P jako „wydajnych”).

vzn
źródło
3
+1. Nie jestem pewien, dlaczego zostało to odrzucone; Czytam gazetę, z którą się łączyłeś, i bardzo pomogło mi przyjrzeć się praktycznym rozwiązaniom, przynajmniej w tej dziedzinie problemów.
Rob Lachlan
3
Robert Sedgewick powiedział w dość niedawnym przemówieniu, że projektant algorytmu, który nie przeprowadza eksperymentów, może zagubić się w abstrakcji. Dyskusja dotyczy znalezienia ścieżek na wykresach i jest w pewnym stopniu związana z maxflow. Nie odpowiada na pytanie, ale może być dla kogoś interesujące.
Juho
5
@Rob, jedyną istotną częścią tej odpowiedzi jest link do artykułu i w odpowiedzi niewiele wyjaśnia, dlaczego ten papier jest w ogóle powiązany. Domyślam się, że OP znalazł link Google i go nie przeczytał. Pozostała część odpowiedzi to kilka ogólnych uwag i komentarzy określających osobistą perspektywę OP w kwestiach, w których nie jest on ekspertem i nie ma tutaj istotnego znaczenia. Odpowiedzi nie są postami na blogu. Link do odpowiedniego artykułu może być dobrym komentarzem, ale nie daje odpowiedzi. To zła odpowiedź, jeśli tak jest. Właśnie dlatego głosowałem za tym.
Kaveh
2
@Kaveh wystarczy. Uważam, że ten artykuł jest przydatnym wskaźnikiem tego, co ludzie uważają za praktycznie przydatne algorytmy. Zgadzam się, że wiele pozostaje bez odpowiedzi.
Rob Lachlan
3
Nie rozumiem też głosów negatywnych. Nie ma powodu, aby sądzić, że plakat NIE przeczytał połączonego artykułu i wydaje się, że jest odpowiedni. Widzę pragnienie, by nie głosować pozytywnie, ale nie głosować negatywnie.
Suresh Venkat