Znalezienie krótkich i grubych ścieżek

Motywacja: W standardowych algorytmach maksymalnego przepływu ścieżki augmentacyjnej wewnętrzna pętla wymaga znalezienia ścieżek od źródła do zatonięcia na ukierunkowanym, ważonym wykresie. Teoretycznie dobrze wiadomo, że aby algorytm nawet zakończył działanie, gdy istnieją nieracjonalne pojemności krawędzi, musimy nałożyć ograniczenia na ścieżki, które znajdziemy. Na przykład algorytm Edmondsa-Karpa mówi nam, aby znaleźć najkrótsze ścieżki.

Empirycznie zaobserwowano, że możemy również chcieć znaleźć ścieżki tłuszczu (czy istnieje na to lepszy termin?). Na przykład, stosując skalowanie pojemności , znajdujemy najkrótsze ścieżki, które mogą znieść co najmniej przepływu. Nie ma ograniczeń co do długości trasy. Kiedy nie możemy już znaleźć żadnych ścieżek, zmniejszamy i powtarzamy. $\epsilon$ $\epsilon$

Interesuje mnie optymalizacja wyboru ścieżek zwiększania dla bardzo specyficznego zastosowania maksymalnego przepływu i chcę zbadać ten kompromis między ścieżkami krótkimi i grubymi. (Uwaga: nie zawsze muszę rozwiązywać problem. Najbardziej interesuje mnie znalezienie największej dolnej granicy przepływu w jak najkrótszym czasie).

Pytanie: Czy istnieje standardowy sposób interpolacji między podejściem najkrótszej ścieżki a podejściem skalowania zdolności? To znaczy, czy istnieje algorytm znajdowania ścieżek zarówno krótkich, jak i grubych, gdzie idealnie jakiś parametr kontrolowałby, ile długości na ścieżce jesteśmy skłonni zamienić na tłuszcz? W skrajności chciałbym móc odzyskać najkrótsze ścieżki na jednym końcu i ścieżki w stylu skalowania pojemności na drugim.

ds.algorithms graph-theory graph-algorithms

— dan_x
źródło

Zauważ, że jeśli jednocześnie próbujesz zoptymalizować zarówno krótkość, jak i grubość, wejdziesz w sferę optymalizacji wielokryterialnej, co oznacza w większości przypadków twardość NP.

— Raphael

ϵ

$\epsilon$

@Daniel Apon - pseudokod do skalowania pojemności znajduje się na stronie 31 tych slajdów: cs.princeton.edu/~wayne/kleinberg.../07maxflow.pdf

— dan_x

@ Rafael - Zauważ, że szukam jednego celu, który mógłby być np. Liniową kombinacją długości i otyłości. Czy nadal uważa się to za optymalizację wielokryterialną?

— dan_x 12.10.10

ϵ

$\epsilon$

W duchu komentarza na temat „całkiem dobrze, ale niekoniecznie optymalnie”, przedstawiam następujący pomysł bez absolutnie żadnej gwarancji optymalności!

Dla kompletności, oto pseudokod, o którym mówiłeś (uwaga: połączony algorytm zakłada, że pojemności brzegowe są liczbami całkowitymi od 1 do C, a wartości przepływu i resztkowej pojemności są integralne):

Scaling-Max-Flow (G, s, t, C) {
   foreach e ∈ E f (e) ← 0
   Δ ← najmniejsza moc 2 większa lub równa C
   G_f ← wykres resztkowy

   podczas gdy (Δ ≥ 1) {
      G_f (Δ) ← Δ-wykres resztkowy
      podczas gdy (istnieje ścieżka rozszerzająca P w G_f (Δ)) {
         f ← augment (f, C, P)
         aktualizacja G_f (Δ)
      }
      ← ← Δ / 2
   }
   powrót f
}

$\epsilon$ $\epsilon = \Delta$ $\epsilon$

$0 \le \rho \le 1$ $\rho$

$\epsilon$ $\rho$

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

$\rho = 0$ $\rho = 1$ $0 < \rho < 1$ $\epsilon$ $\le 1$

— Daniel Apon
źródło

Dzięki za pomysł - zbliża się do tego, co miałem na myśli. Moją jedyną obawą jest to, że jest to po prostu inny „harmonogram rozpadu” dla skalowania pojemności, prawda?

— dan_x 12.10.10

Gdy rozpadasz się bardziej agresywnie, dostajesz krótsze ścieżki, a gdy gnicie mniej agresywnie, dostajesz grubsze ścieżki. Miałem na myśli to, że każda ścieżka otrzyma wynik na podstawie tego, jak gruba i jak krótka była, wtedy algorytm znajdzie wszystkie ścieżki z wynikiem większym niż pewien próg.

— dan_x

Ale jeśli nie ma standardowego sposobu na zrobienie tego, mogę usiąść i przemyśleć algorytm, który robi to, co chcę.

— dan_x