Super Mario płynie w NP?

Klasycznym rozszerzeniem problemu maksymalnego przepływu jest problem „maksymalnego przepływu w czasie”: otrzymujesz wykrój, którego dwa węzły są rozróżniane jako źródło i zlew, przy czym każdy łuk ma dwa parametry, wydajność na czas i opóźnienie. Jesteś również biorąc pod uwagę horyzont czasowy . Celem jest, aby obliczyć przepływ w czasie której dostaje maksymalną ilość materiału od źródła do zlewu przez czas . Przepływ o maksymalnej wartości można obliczyć w czasie wielomianowym poprzez sprytną klasyczną redukcję do maksymalnego przepływu o minimalnym koszcie.$T$$T$

Interesuje mnie rozszerzenie tego modelu, w którym krawędzie mają trzeci parametr „żywotności”. Jeśli łuk ma długość życia , a jest najwcześniejszym momentem, w którym dodatni przepływ jest przesyłany przez łuk, wówczas niszczymy łuk w czasie . Możesz myśleć o tym jak o platformach w Super Mario Brothers, które wypadają / są niszczone wkrótce po nadepnięciu na nie, lub możesz myśleć o nich jako o bateriach potrzebnych do zasilania krawędzi, których nie można wyłączyć po włączeniu . ( Edytuj :) Problemem decyzyjnym jest, gdy przy danej wartości przepływu dolna granica , czy można zaplanować przepływ spełniający zarówno górną granicę horyzontu czasowego, jak i dolną granicę wartości przepływu.t t + ℓ $\ell$$t$$t+\ell$$B$

Jak dotąd widzę, że ten problem jest silnie NP-trudny (przez 3 partycje). Ale tak naprawdę nie wiem, czy jest to w NP: czy jest jakaś gwarancja sposobu wyrażenia rozwiązania w sposób zwarty? W wersji klasycznej stosuje się specjalny rodzaj optymalnego przepływu w celu obejścia tego problemu.

Uwaga: powyższy model jest nieco nieokreślony, ponieważ możesz zezwolić lub zabronić gromadzenia zapasów przepływu w węzłach i możesz mieć dyskretny model czasowy lub ciągły. Rozwiązanie problemu dla któregokolwiek z tych modeli byłoby doskonałe.

Minęło dużo czasu, ale jestem pewien, że ten problem występuje w P.

Pracę doktorską napisałem na ten temat w 1995 r. Patrz „Efektywne algorytmy przepływu dynamicznej sieci” Bruce'a Hoppe'a przedłożone w departamencie Cornell CS. Online pod adresem http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf

Zobacz rozdział 8 „Rozszerzenia” sekcja 8.1 o „śmiertelnych krawędziach”

EDYCJA: odpowiedź jest ZŁA. Przyjąłem (głupie) domniemane założenie, że kiedy przepływ ścieżki rozpoczyna się w czasie s, a kończy w czasie ti przechodzi przez krawędź e, blokuje krawędź e na ten czas. To jednak nie jest prawda. Widzieć *.

Uwaga: Być może takie podejście jest niepotrzebnie skomplikowane lub nieprawidłowe. Chociaż próbowałem to zweryfikować i dokładnie zanotować - nie spędziłem nad tym dużo czasu.

Zakładając, że „gromadzenie zapasów” jest niedopuszczalne, np. Przepływ musi zostać niezwłocznie przekazany. Niech oznacza liczbę krawędzi, a N długość wejściową. Nie określiłem czasu ciągłego ani dyskretnego, ponieważ nie wziąłem go pod uwagę. Powinien działać dla dyskretnego myślenia, dla ciągłości jestem pewien, że jestem pewien.$m$$N$

Następnie możemy opisać to rozwiązanie jako zestaw „ścieżek przepływów” od źródła do ujścia. Ścieżka przepływu jest poczwórna która składa się z następujących elementów: Prosta ścieżka P od źródła do ujścia; Czas ścieżki przepływu począwszy s ; Ilość przepływu przez ścieżkę a ; Przepustowość r .$(P,s,a,r)$$P$$s$$a$$r$

Pozwól, że rozwiązaniem będzie zbiór przepływów ścieżkowych. Możemy zweryfikować, czy rozwiązanie podane przez te ścieżki przepływu jest poprawne w wielomianie czasowym w | F | i N :$F$$|F|$$N$

• Dla każdego zbocza momentu t dodaj sumę przepustowości wszystkich przepływów ścieżki przechodzących przez e w czasie t . Każdy przepływ ścieżki ma czas rozpoczęcia i zakończenia, dlatego musimy jedynie wziąć pod uwagę momenty, w których przepływ ścieżki zaczyna się lub kończy (między tymi momentami nic się nie zmienia w odniesieniu do przepływów ścieżki, które przekraczają krawędź e .$e$$t$$e$$t$$e$
• Dla każdej ścieżki przepływowy możemy zweryfikować, czy wszystkim jest to strumień dotrze do zlewu przed czasem .$T$
• Dla każdej krawędzi możemy zweryfikować, czy przepływ ścieżki przechodzi po jej zniszczeniu, czy nie.
• Dolną granicę przepływu możemy po prostu sprawdzić, sumując wielkości przepływu ścieżek przepływu.$B$

Teraz „tylko” trzeba pokazać, że liczba path-płynie jest wielomian w .$N$

Dla danego rozwiązania możemy określić czas, w którym pewien przepływ przekroczył krawędź i kiedy krawędź została zniszczona. Przekształć to w problem z równoważnym rozwiązaniem: istnieją twarde granice na każdej krawędzi, kiedy można jej użyć, a kiedy nie - czas rozpoczęcia i zakończenia. Niech oznacza zbiór wszystkich tych czasów.$\{t_1,...,t_k\}$

Zastanów się nad jakimś niekompaktowym rozwiązaniem i (początkowo) pustym zestawem ścieżek przepływów. Chodzi o to, że iteracyjnie znajdujemy ścieżkę przepływu w nie kompaktowym rozwiązaniu, usuwamy ją i przechowujemy w naszym zestawie ścieżek przepływu.

Znaleźć ścieżki przepływów to początek i koniec od i t j , ı < j , ale nie kończy pomiędzy każdym t p i t q takie, że [ T P , T Q ] ⊆ [ t i , t j ] . Niech K I , J oznacza zbiór ścieżki przepływów między t J i t j o właściwościach opisanych powyżej.$t_i$$t_j$$i<j$$t_p$$t_q$$[t_p,t_q] \subseteq [t_i,t_j]$$F_{i,j}$$t_j$$t_j$

Załóżmy, że już usunęliśmy wszystkie przepływy ścieżek dla wszystkich mniejszych przedziałów niż . Chciwie znajduj przepływy ścieżek, które zaczynają się i kończą w [ t i , t j ] . Kiedy go znajdziemy, usuń ten przepływ z rozwiązania i odpowiednio dostosuj przepustowości wierzchołków oraz ilość przepływu wysyłanego ze źródła do tonącego. Dla tego przepływu ścieżki maksymalizujemy przepustowość. Oznacza to, że dla co najmniej jednej krawędzi osiągnęliśmy maksymalną przepustowość lub po usunięciu tego przepływu ścieżki nie ma już przepływu przez tę krawędź. Należy zauważyć, że dotyczy to okresu [ t i + 1 , t $[i,j]$$[t_i,t_j]$. W obu przypadkach nie ma już przepływu przez tę krawędź i możemy stwierdzić, że | F s , t | ≤m.$[t_{i+1},t_{j-1}]$$|F_{s,t}| \leq m$

(*) Dlaczego poprzednie twierdzenie jest prawdziwe? Cóż, każdy inny przepływ ścieżka w zaczyna się przed t i + 1 i kończy się po t j - 1 . Dlatego muszą nakładać się na siebie w czasie, gdy używają określonej krawędzi. Ponieważ przepływ jest zmaksymalizowany dla przepływu ścieżki, musi istnieć krawędź tam, gdzie jest ciasno.$F_{t_i,t_j}$$t_{i+1}$$t_{j-1}$

$\sum_{i,j \in [k]} | F_{i,j} |\leq c m^3$$c$

W moim rozumieniu musisz zapisać tylko jedną liczbę na łuk, co oznacza moment, w którym przepływ zaczyna być wysyłany przez łuk. Zakłada się, że potem łuk stanie się niezdatny do użytku. Jeśli w przeciwnym razie łuk może zostać ponownie użyty po tym, jak przestanie być używany, powinien mieć rozwiązania arbitralnie zbliżone do rozwiązań zapewniających maksymalny przepływ w czasie (ponieważ przepływ może przestać być wysyłany przez dowolnie krótki czas, a następnie ponownie zacząć pompować ).