Przyrostowy maksymalny przepływ na wykresach dynamicznych

Szukam szybkiego algorytmu do obliczenia maksymalnego przepływu na wykresach dynamicznych. tzn. biorąc pod uwagę wykres i , mamy maksymalny przepływ w od do . Następnie nowy / stary węzeł dodane / usunięty z jego odpowiednich krawędziach, tworząc krzywą . Jaki jest maksymalny przepływ na nowo utworzonym wykresie? Czy istnieje sposób, aby zapobiec ponownemu obliczeniu maksymalnego przepływu?s , t ∈ V F G s t u G $G=(V,E)$$s,t\in V$$F$$G$$s$$t$$u$$G^1$

Doceniane jest wszelkie przetwarzanie wstępne, które nie zajmuje dużo czasu / pamięci.

Najprostszym pomysłem jest ponowne obliczenie przepływu.

Innym prostym pomysłem jest zapisanie wszystkich ścieżek rozszerzających, które były użyte w poprzednim obliczeniu maksymalnego przepływu, aby dodać wierzchołek , możemy znaleźć proste ścieżki (w zaktualizowanym wykresie wydajności z poprzedniego kroku), które zaczynają się od źródła, przechodzą do a następnie przechodzą do miejsca docelowego, ale problem polega na tym, że ta ścieżka powinna być prosta, nie mogłem znaleźć lepszego niż dla tego przypadku, dla. (Zauważ też, że jeśli była to tylko jedna ścieżka, można to zrobić w ale tak nie jest.)v O ( n ⋅ m ) m = | E | O ( n + m $v$$v$$O(n\cdot m)$$m=|E|$$O(n+m)$

Również do usuwania węzła powyżej pomysł nie działa.

Widziałem też papiery takie jak Przyrostowe podejście do krawędzi , ale wydaje się, że w tym przypadku nie są wystarczająco dobre, to więcej niż dla każdej krawędzi i wydaje się, że nie jest odpowiednim rozszerzeniem w tym przypadku (po prostu ponownie obliczamy przepływ). Również obecnie używam algorytmu maksymalnego przepływu Forda-Fulkersona Jeśli istnieje lepsza opcja dla algorytmów online, dobrze to wiedzieć.$O(m)$

Opisane podejście może nie być teoretycznie optymalne. To tylko proste praktyczne rozwiązanie, które może działać dla autora. Nie mogę podać żadnych odniesień, ponieważ zawsze uważałem, że jest to powszechnie znany folklor, ale o dziwo nikt nie opublikował go w odpowiedzi. Więc to robię.

Załóżmy, że mamy sieć bezkierunkową . Załóżmy, że jest przechowywany w strukturze danych, która umożliwia łatwe wstawianie / usuwanie wierzchołków / łuków. Czasami użyjemy sieci resztkowej (tj. O zaktualizowanych pojemnościach ).G f c f = c - $G=(V,E,c)$$G_f$$c_f = c - f$

Pierwsza część dotyczy przetwarzania wstawiania / usuwania wierzchołków. W przypadku wstawek jest to mniej lub bardziej proste:

1. Dodaj nowy wierzchołek z odpowiednimi krawędziami do sieci resztkowej.
2. Znajdź maksymalny przepływ w zaktualizowanej sieci resztkowej za pomocą wybranego algorytmu maksymalnego przepływu.

W przypadku usuwania rzeczy stały się bardziej skomplikowane. Wyobraźmy sobie, że podzieliliśmy wierzchołek który zamierzamy usunąć na 2 połówki i tak, że wszystkie łuki wskazują , wszystkie łuki przechodzą od i nowych wierzchołków są połączone łukiem o nieskończonej pojemności. Zatem usunięcie jest równoważne usunięciu łuku między a . Co się stanie w tym przypadku? Oznaczmy przez przepływ przechodzący przez wierzchołek . Wtedy doświadczy nadmiaru jednostek przepływu iv i n v o u t v i n v o u t v v i n v o u t f v v v i n f v v o u t f v ~ f v v i n v o u t v i n v o u t f v f v v Δ $v$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$v$$v_{in}$$v_{out}$$f^v$$v$$v_{in}$$f^v$$v_{out}$zaraz po usunięciu wystąpi niedobór jednostek przepływu (ograniczenia przepływu zostaną oczywiście złamane). Aby ograniczenia przepływu zostały ponownie utrzymane, powinniśmy przestawić przepływy, ale chcemy również utrzymać pierwotną wartość przepływu tak wysoką, jak to możliwe. Sprawdźmy najpierw, czy możemy dokonać przegrupowania bez zmniejszania całkowitego przepływu. Aby to sprawdzić, znajdź maksymalny przepływ z do w „odciętej” sieci resztkowej (tj. Bez łuku łączącego i ). Powinniśmy oczywiście związać to . Jeśli okaże się, że jest równe to mamy szczęście: ponownie przypisaliśmy przepływ, który przepływał przez$f^v$$\tilde{f^v}$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$f^v$$f^v$$v$w taki sposób, że całkowity przepływ nie został zmieniony. W innym przypadku całkowity przepływ musi zostać zmniejszony o „bezużyteczny” nadmiar jednostek . Aby to zrobić, tymczasowe połączenie i na łuku o nieskończonej pojemności i uruchomić algorytmu MaxFlow ponownie z do (należy związany przepływu poprzez ). To naprawi resztkową sieć i sprawi, że ograniczenia przepływu zostaną ponownie utrzymane, automatycznie zmniejszając całkowity przepływ przez .$\Delta = f^v - \tilde{f^v}$$s$$t$$v_{in}$$v_{out}$$\Delta$$\Delta$

Złożoność czasowa takich aktualizacji może zależeć od używanego algorytmu maxflow. Najgorsze przypadki mogą być dość złe, ale wciąż jest to lepsze niż całkowite przeliczanie.

Druga część to algorytm, którego należy użyć. O ile rozumiem, autor nie potrzebuje bardzo złożonego (ale wciąż wydajnego) algorytmu z małą ukrytą stałą do uruchomienia go na platformie mobilnej. Jego pierwszy wybór Forda-Fulkersona (spodziewam się, że będzie to Edmonds-Karp ) wygląda niezbyt źle z tego punktu widzenia. Ale są też inne możliwości. Ten, który poleciłbym najpierw, to wariant algorytmu Dinica, ponieważ jest on dość szybki w praktyce i można go zaimplementować w bardzo prosty sposób. Inne opcje mogą obejmować skalowanie pojemności Ford-Fulkerson w$O(|V|^2|E|)$$O(|E|^2 \log C_{max})$a przecież różne wersje push-relabel z heurystyką. W każdym razie wydajność będzie zależeć od przypadku użycia, więc autor powinien znaleźć najlepszy empirycznie.

ok, biorąc pod uwagę nowe informacje i unikając trudnych wcześniejszych fałszywych startów / referencji red herring (mea culpa), oto kilka nowych referencji na ten temat.

Szybkie rozwiązywanie sekwencji problemów związanych z maksymalnym przepływem online dzięki rozszerzeniom obliczeniowym Solidne minimalne cięcia Doug Altner i Özlem Ergun

niniejszy odnośnik uwzględnia sekwencje online urządzeń wielofunkcyjnych i „ciepłe rozruchy”, tj. bazowanie na przyrostowych zmianach w stosunku do wcześniejszych urządzeń wielofunkcyjnych. „Wykazujemy, że nasze algorytmy skracają czas działania o rząd wielkości w porównaniu z podobnymi kodami, które wykorzystują solver black-box MFP. W szczególności pokazujemy, że nasz algorytm dla solidnych minimalnych cięć może rozwiązać przypadki w ciągu sekund, które wymagałyby ponad czterech godzin przy użyciu solvera czarnego pola maksymalnego przepływu. ”

postępy w zakresie problemów związanych z maksymalnymi przepływami Altner, Douglas S., georgia tech

w tej rozprawie doktorskiej z 2008 r. (plik pdf do pobrania) autor rozważa problem przyrostowego dodawania łuków, który wydaje się „wystarczająco blisko” do problemu dodawania nowych wierzchołków (z wieloma nowymi łukami).

wiele z tych odniesień dotyczy usuwania części sieci (cięcia / „zakaz”), jak stwierdzono w pierwszej części streszczenia

patrz zwłaszcza „IV ROZWIĄZYWANIE SEKWENCJI ONLINE MAKSYMALNYCH PRZEPŁYWÓW....... p63”.

str. 63 „Celem tego rozdziału jest jednak przekonanie czytelnika, że ​​iteracyjne użycie solvera o maksymalnym przepływie czarnej skrzynki do rozwiązania dużej sekwencji urządzeń wielofunkcyjnych może prowadzić do ogromnej liczby niepotrzebnych obliczeń.”

p66 "We wspomnianych powyżej aplikacjach urządzenia wielofunkcyjne są zazwyczaj topologicznie podobne. Oznacza to, że następne urządzenie wielofunkcyjne w sekwencji różni się od poprzedniego przez dodanie lub usunięcie małej liczby łuków lub przez przewidywalną zmianę wydajności zlokalizowanego zestawu łuków. Ponadto , przy rozwiązywaniu tych przypadków czas i miejsce potrzebne do przechowywania czegokolwiek poza rozwiązaniem poprzedniego problemu jest zwykle nieuzasadnione ”.

Autor p67 również tutaj stosuje podejście „ciepłego startu”. „Skuteczną strategią szybkiego rozwiązania całej sekwencji problemów optymalizacyjnych online jest opracowanie wydajnej heurystyki ponownej optymalizacji. W tym celu opracowujemy zmodyfikowany algorytm maksymalnego przepływu, który został zaprojektowany z myślą o wydajnych ciepłych rozruchach.”

patrz esp p71, który ma specyficzny problem przyrostowy nowego łuku:

Nowy problem ponownej optymalizacji maksymalnego przepływu łuku (NAMFRP)

autor rozważa bardziej ogólne problemy str. 67

Problem ponownej optymalizacji
maksymalnego przepływu (MFROP) Problem ponownej optymalizacji maksymalnego przepływu z pojedynczym łukiem (MFSAROP)

po szybkim wyszukiwaniu wygląda na to, że wersja online jest obszarem aktywnych badań. nie wspominasz o obszarze zastosowania, który może pomóc zawęzić wyszukiwanie literatury. jedną z opcji jest poszukiwanie obszaru zastosowania, w którym jest najwięcej lub najnowsza innowacja. stąd jest pewne zastosowanie przyrostowego maksymalnego przepływu w systemach wizyjnych i niektóre algorytmy dla niego; wypróbuj Maximum Flows by Incremental Breadth-First Search w Microsoft Research Labs. parafrazując wprowadzenie do tego artykułu, najwyraźniej w przypadku przypadków widzenia algorytm Bojkowa i Kołmogorowa dobrze sobie radzi i nie ma znanych wykładniczych kontrprzykładów czasu, chociaż poza aplikacjami wizyjnymi może działać słabo. więc może warto wypróbować algorytm B&K na swoich danych i zobaczyć, jak działa.

wydaje się, że mówisz, że algorytm przyrostowy, który jest liniowy w liczbie krawędzi wykresu, nie jest wystarczającą prędkością? ale czyż nie jest to dość wysoka wydajność? z iloma krawędziami masz do czynienia? być może podejście może polegać na zmniejszeniu kosztu przejścia wykresu, jeśli jest to kosztowne lub znaczący czynnik (np. wykres przechowywany w db vs. wykres przechowywany w pamięci)

tutaj jest interesujący artykuł, który dowodzi, że podczas gdy nieinkrementalny algorytm maksymalnego przepływu jest w P, wersja przyrostowa jest NP kompletna. „Zgodnie z naszą najlepszą wiedzą, nasze wyniki jako pierwsze znalazły problem czasu P, którego wersja przyrostowa jest NP kompletna”.

Przepływ przyrostowy według Hartline, Sharp

inną możliwością / kierunkiem jest algorytm maksymalnego przepływu push-relabel , który jest „jednym z najbardziej wydajnych algorytmów maksymalnego przepływu” i może mieć lepsze profile złożoności w zależności od twoich danych. np. jak podaje strona wikipedia

$O(V^3)$$O(V^2 \sqrt E$$O(V \cdot E \cdot log(V^2 / E))$