„Krewni” problemu najkrótszej ścieżki

Rozważ dołączony niekierowany wykres z nieujemnymi wagami krawędzi i dwoma wyróżnionymi wierzchołkami . Poniżej przedstawiono niektóre problemy ze ścieżką, które mają następującą postać: znajdź ścieżkę , tak aby jakaś funkcja ciężaru krawędzi na ścieżce była minimalna. W tym sensie wszyscy są „krewnymi” problemu najkrótszej ścieżki; w tym ostatnim funkcja jest po prostu sumą. $s,t$ $s-t$

Uwaga: Szukamy prostych ścieżek, to znaczy bez powtarzających się wierzchołków. Ponieważ w literaturze nie znalazłem standardowych nazw tych problemów, sam je nazwałem.

Ścieżka o minimalnej przerwie ciężaru: znajdź ścieżkę , tak aby różnica między największą i najmniejszą wagą krawędzi na ścieżce była minimalna. $s-t$

Płynniejsza ścieżka: znajdź ścieżkę , tak aby największy rozmiar kroku na ścieżce był minimalny, gdzie rozmiar kroku jest wartością bezwzględną różnicy masy między dwiema kolejnymi krawędziami. $s-t$

Ścieżka z minimalną wysokością: zdefiniujmy wysokość ścieżki na podstawie sumy rozmiarów kroków wzdłuż ścieżki (patrz definicja wielkości kroku powyżej). Znajdź ścieżkę o minimalnej wysokości. $s-t$

Ścieżka z minimalną wagą pierwszą: zakładając, że wszystkie masy krawędzi są dodatnimi liczbami całkowitymi, znajdź ścieżkę , tak aby jej waga była liczbą pierwszą. Jeśli istnieje taka ścieżka, znajdź ją o najmniejszej możliwej masie podstawowej. $s-t$

Pytanie: co wiadomo o tych problemach ze ścieżką? (I inne, które można by pomyśleć w podobnym duchu, stosując inną funkcję odważników.) Ogólnie, czy istnieją jakieś wskazówki, które funkcje odważników krawędziowych można zminimalizować w czasie wielomianowym, a które są trudne NP?

Uwaga: interesujące jest na przykład to, że chociaż suma wag jest łatwa do zminimalizowania (jest to klasyczny problem najkrótszej ścieżki), ale minimalizacja ściśle powiązanej średniej wag na ścieżce jest trudna NP. (Przypisz wagę 2 do wszystkich krawędzi padających do i , a wagę 1 do wszystkich innych. Wtedy minimalna średnia ścieżka ciężaru będzie najdłuższą ścieżką ). $s$ $t$ $s-t$

— Andras Farago
źródło

Odpowiedzi:

Oto odpowiedź na pierwszy problem:

Ścieżka o minimalnej przerwie ciężaru: znajdź ścieżkę , tak aby różnica między największą i najmniejszą wagą krawędzi na ścieżce była minimalna. $s-t$

Artykuł z 1984 r. Pokazuje, że ilekroć możemy podjąć decyzję o wykonalności (czy istnieje rozwiązanie w przypadku nieważonym) dla jakiegoś kombinatorycznego problemu optymalizacji w czasie wielomianowym, wówczas możemy również znaleźć w czasie wielomianowym rozwiązanie, które minimalizuje różnicę między największym a najmniejszym współczynnik kosztów (w przypadku ważonym):

S. Martello, WR Pulleyblank, P. Toth, D. de Werra
Zrównoważone problemy z optymalizacją
Operations Research Letters 3, 1984, strony 275-278

To implikuje algorytm wielomianowy do twojego pytania.

— Gamow
źródło

Można tego również dokonać poprzez brutalne przeszukanie wszystkich par krawędzi, które mogą stanowić maksimum i min, oraz ich kolejność / orientacje.

— Yonatan N

Ścieżka z minimalną różnicą masy : można to rozwiązać w czasie , gdzieto liczba krawędzi (przy założeniu, że jest co najmniej liniowa pod względem liczby wierzchołków). Możesz zapętlić minimalną wagę i przeprowadzić wyszukiwanie binarne (lub wydajne aktualizacje) powyżej maksymalnej wagi i sprawdzić łączność. Nie wiem, czy można to poprawić. $\tilde{O}(|E|^2)$ $|E|$ $|E|$

Ścieżka z minimalną wysokością (według twojej terminologii): Można to rozwiązać w czasie . Możesz obliczyć odległość (jak suma rozmiarów „kroków”) do wszystkich krawędzi analogicznie do zwykłej ważonej najkrótszej ścieżki. Zauważ, że powtarzające się wierzchołki nie mogą skracać ścieżki. Aby efektywnie obsługiwać wierzchołki wysokiego stopnia (jak w celu uniknięcia czasu ), możesz podzielić wierzchołek stopnia na ścieżkę wierzchołków . $\tilde{O}(|E|)$ $|E|^2$ $k$ $k-1$

Ścieżka o minimalnej masie podstawowej: jeśli wagi są w systemie binarnym, powinna być NP kompletna: należy użyć krawędzi o masie 1, z wyjątkiem początkowej krawędzi o wysokiej masie, tak że tylko ścieżka Hamiltona ma masę pierwszą (waga jest sumą mas krawędzi) . (Zastrzeżenie polega na tym, że nie udowodniliśmy, że wystarczająco duże liczby pierwsze (nawet bez minimalnych luk pierwszych) można szybko znaleźć bez przypadkowości.) Nawet w przypadku jednostkowych wag, nie oczekuję, że będzie w P.
Minimalna masa pierwsza umożliwiająca samodzielne przecięcia: w P dla wag jednostkowych. Jeśli zamiast zbioru liczb pierwszych użyjemy zbioru liczb losowych o gęstości , to z prawdopodobieństwem 1 jest to $S$ $Θ(n/\log n)$ $\mathrm{P}^S$ nawet dla wag binarnych: wystarczy śledzić wielomianowo wiele (zależnych od ) najniższych wag ścieżki w każdym punkcie. Jednak w przypadku wag pierwszych możemy być zmuszeni do dywersyfikacji dzielników różnic masy (zamiast po prostu śledzić najniższe wagi) i nie jest jasne, czy to wystarczy. $S$

Płynniejsza ścieżka: NP zakończona. Jeśli pozwolilibyśmy na skrzyżowania, byłoby to możliwe do rozwiązania w czasie , ale w przypadku wersji bez skrzyżowań, tutaj jest redukcja z 3-SAT z zmiennymi. Posiadaj wierzchołki , plus wierzchołek dla każdej klauzuli. Dla każdej zmiennej ( ) dodaj gładką ścieżkę (w razie potrzeby używając dodatkowych wierzchołków) od do która przechodzi przez wszystkie klauzule z dodatnim wystąpieniem , i podobną ścieżkę dla klauzul z $\tilde{O}(|E|)$ $n$ $s=v_0,v_1,...,t=v_n$ $x_i$ $i<n$ $v_i$ $v_{i+1}$ $x_i$ $¬x_i$ . Ustaw pierwszą i ostatnią wagę krawędzi każdej ścieżki na 1 (lub inną stałą), ale w przeciwnym razie wybierz takie ciężary, aby żadne inne ścieżki nie były gładkie. Na koniec zduplikuj wszystkie wierzchołki klauzul i przyległe krawędzie; w ten sposób każdą klauzulę można odwiedzić maksymalnie dwa razy, co wystarcza dla 3-SAT.

— Dmytro Taranovsky
źródło

Myślę, że najbardziej płynna ścieżka jest w P, z powodu następującej transformacji. Niech będzie wierzchołkiem stopnia . Zamień na klikę o rozmiarze , tak że każda krawędź która pierwotnie sąsiadowała z kończy się teraz na innym wierzchołku kliki. Jeśli są dwiema takimi oryginalnymi krawędziami, przypisz wagędo krawędzi w . Wykonaj tę transformację dla każdego wierzchołka i przypisz 0 wagi do oryginalnych krawędzi wykresu. Następnie minimalna waga

v

$v$

d

$d$

v

$v$

d

$d$

e

$e$

v

$v$

v_{e}

$v_e$

e, f

$e,f$

| w (e) - w (f) |

$|w(e)-w(f)|$

(v_{e}, v_{f})

$(v_e,v_f)$

v \neq s, t

$v\neq s,t$

s - t

$s-t$ ścieżka na nowym wykresie daje płynniejszą ścieżkę w oryginale, po cofnięciu transformacji.

— Andras Farago,

@AndrasFarago Problem z twoim argumentem polega na tym, że niektóre proste ścieżki na rozszerzonym wykresie mają powtarzające się wierzchołki na oryginalnym wykresie. Podoba mi się, że najbardziej płynny problem ze ścieżką wydaje się zwodniczo prosty.

— Dmytro Taranovsky,

@ Dmytro Taranovsky Wygląda na to, że masz rację, może się zdarzyć, że po powrocie do oryginalnego wykresu możemy uzyskać powtarzające się wierzchołki na ścieżce (ale bez powtarzających się krawędzi). Jeśli jednak każdy stopień na oryginalnym wykresie wynosi co najwyżej 3, powtórzenie nie będzie możliwe. Oznacza to, że problem Płynnej ścieżki występuje w P przynajmniej dla wykresów o maksymalnym stopniu .

\leq 3

$\leq 3$

— Andras Farago,

Niestety, na przekształconym wykresie musimy znaleźć ścieżkę o najmniejszej maksymalnej masie (która jest również w P), a nie najmniejszej masie całkowitej. Całkowita waga prowadziłaby do ścieżki o minimalnej wysokości (na wykresach z maksymalnym stopniem , tak że wykluczone są powtarzające się wierzchołki).

\leq 3

$\leq 3$

— Andras Farago,