Problem kanadyjskiego podróżnika

W informatyce i teorii grafów kanadyjski problem podróżnika ( CTP ) jest uogólnieniem problemu najkrótszej ścieżki na grafy, które są częściowo obserwowalne . Innymi słowy, wykres jest ujawniany podczas jego eksploracji, a eksploracyjne krawędzie są obciążane, nawet jeśli nie mają udziału w ostatecznej ścieżce.

Ten problem optymalizacji został wprowadzony przez Christosa Papadimitriou i Mihalisa Yannakakisa w 1989 roku i od tego czasu zbadano wiele wariantów tego problemu. Nazwa wywodzi się rzekomo z rozmów autorów, którzy dowiedzieli się o trudnościach, z jakimi kanadyjscy kierowcy: podróżowaniu po sieci miast z przypadkowymi opadami śniegu blokującymi drogi. Wersji stochastycznej, w której każda krawędź jest powiązana z prawdopodobieństwem niezależnego przebywania na wykresie, poświęcono wiele uwagi w badaniach operacyjnych pod nazwą „Stochastic Shortest Path Problem with Recourse” (SSPPR).

Opis problemu

Dla danej instancji istnieje wiele możliwości lub realizacji tego, jak może wyglądać ukryty wykres. Biorąc pod uwagę instancję, opis tego, jak postępować zgodnie z instancją w najlepszy sposób, nazywa się polityką . Zadaniem CTP jest obliczenie oczekiwanego kosztu polis optymalnych. Obliczenie rzeczywistego opisu optymalnej polityki może być trudniejszym problemem.

Biorąc pod uwagę instancję i politykę dla instancji, każda realizacja tworzy swój własny (deterministyczny) spacer po grafie. Zauważ, że spacer niekoniecznie jest ścieżką , ponieważ najlepszą strategią może być np. odwiedzenie każdego wierzchołka cyklu i powrót do początku. Różni się to od problemu najkrótszej ścieżki (z ściśle dodatnimi wagami), w którym powtórzenia w marszu oznaczają, że istnieje lepsze rozwiązanie.

Warianty

Istnieje przede wszystkim pięć parametrów wyróżniających liczbę wariantów problemu kanadyjskiego podróżnika. Pierwszym parametrem jest sposób wyceny spaceru generowanego przez politykę dla danej instancji i realizacji. W stochastycznym problemie najkrótszej ścieżki z regresem celem jest po prostu zminimalizowanie kosztu spaceru (zdefiniowanego jako suma kosztu krawędzi po wszystkich krawędziach pomnożona przez liczbę pokonania tej krawędzi). W przypadku kanadyjskiego problemu podróżnika zadaniem jest zminimalizowanie konkurencyjnego stosunku spaceru; tj. w celu zminimalizowania liczby razy dłuższych spacerów do najkrótszej ścieżki w realizacji.

Drugim parametrem jest sposób oceny polityki w odniesieniu do różnych realizacji zgodnych z rozważaną instancją. W kanadyjskim problemie podróżnika chce się zbadać najgorszy przypadek , aw przypadku SSPPR średni przypadek . W przypadku analizy przypadku średniego należy ponadto określić a priori na realizacje.

Trzeci parametr jest ograniczony do wersji stochastycznych i dotyczy tego, jakie założenia możemy przyjąć na temat rozkładu realizacji i jak rozkład jest reprezentowany na wejściu. W stochastycznym kanadyjskim problemie podróżnika i niezależnym od krawędzi stochastycznym problemie najkrótszej ścieżki (i-SSPPR) każda niepewna krawędź (lub koszt) ma powiązane prawdopodobieństwo realizacji, a zdarzenie, w którym krawędź jest na wykresie, jest niezależne których inne krawędzie są w realizacji. Mimo, że jest to znaczne uproszczenie, problem jest nadal #P -trudny. Innym wariantem jest nie przyjmowanie żadnych założeń dotyczących rozkładu, ale wymaganie, aby każda realizacja z niezerowym prawdopodobieństwem była wyraźnie określona (np. ..”). Nazywa się to Stochastycznym Problemem Najkrótszej Ścieżki Dystrybucji (d-SSPPR lub R-SSPPR) i jest NP-zupełne. Pierwszy wariant jest trudniejszy niż drugi, ponieważ pierwszy może reprezentować w przestrzeni logarytmicznej pewne rozkłady, które drugi reprezentuje w przestrzeni liniowej.

Czwartym i ostatnim parametrem jest zmiana wykresu w czasie. W CTP i SSPPR realizacja jest ustalona, ale nieznana. W stochastycznym problemie najkrótszej ścieżki z regresem i resetami lub w problemie oczekiwanej najkrótszej ścieżki po każdym kroku podejmowanym przez politykę wybierana jest nowa realizacja z rozkładu. Problem ten można rozwiązać w czasie wielomianowym, redukując go do procesu decyzyjnego Markowa z horyzontem wielomianowym. Wiadomo, że uogólnienie Markowa, w którym realizacja grafu może wpłynąć na następną realizację, jest znacznie trudniejsze.

Dodatkowym parametrem jest sposób odkrywania nowej wiedzy na temat realizacji. W tradycyjnych wariantach CTP agent odkrywa dokładną wagę (lub status) krawędzi po dotarciu do sąsiedniego wierzchołka. Niedawno zaproponowano nowy wariant, w którym agent ma również możliwość wykonywania teledetekcji z dowolnego miejsca na realizacji. W tym wariancie zadaniem jest zminimalizowanie kosztów podróży plus koszt operacji detekcji.

Definicja formalna

Badany wariant definiujemy w artykule z 1989 roku. Oznacza to, że celem jest zminimalizowanie współczynnika konkurencyjności w najgorszym przypadku. Konieczne jest, abyśmy zaczęli od wprowadzenia pewnych terminów.

Rozważ dany graf i rodzinę grafów nieskierowanych, które można zbudować, dodając jedną lub więcej krawędzi z danego zbioru. Formalnie niech ${\ Displaystyle {\ mathcal {G}} (V, E, F) = \ {(V, E + F ') | F' \ subseteq F \}, E \ cap F=\emptyset }$ gdzie myślimy o E jako o krawędziach, które muszą znajdować się w grafie, a o F jako o krawędziach, które mogą być w grafie. Mówimy, że jest realizacją rodziny wykresów ${\ Displaystyle G \ in {\ mathcal {G}} (V, E, F)} .$ Ponadto niech W będzie powiązaną macierzą kosztów, gdzie $i$ kosztem przejścia z wierzchołka do , zakładając , że ta krawędź jest w realizacji.

Dla dowolnego $względem$ v w V nazywamy jego krawędzie B . $)$ $_ B}(s,t)}$ realizacji re będzie kosztem najkrótszej ścieżki na wykresie od s do t . Nazywa się to problemem offline, ponieważ algorytm dla takiego problemu miałby pełne informacje o grafie.

Mówimy, że strategia $wykresie$ to mapowanie z $(F), V)}$ ${\ Displaystyle ({\ mathcal {P}} (E), { \mathcal {P}$ } do ${\ Displaystyle V}$ , gdzie ${\ Displaystyle {\ mathcal {P}} (X)}$ oznacza potęgę X . Definiujemy koszt $w$ $V,B)}$ konkretnej $Displaystyle$ V $\$ w następujący sposób.

Niech ${\ Displaystyle v_ {0} = s, E_ {0} = E}$ i ${\ displaystyle F_ {0} = F}$ .
Dla ${\ Displaystyle i = 0,1,2,...}$ $i = 0, 1, 2, ...$ zdefiniuj
- ${\ Displaystyle E_ {i + 1} = E_ {i} \ kubek E_ {B} (v_ {i}, V)}$ ,
- ${\ Displaystyle F_ {i + 1} = F_ {i} -E_ {F} (v_ {i}, V)}$ i
- ${\ Displaystyle v_ {i + 1} = \ pi (E_ {i + 1}, F_ {i + 1}, v_ {i })}$ .
Jeśli istnieje T takie, że ${\ Displaystyle v_ {T} = t}$ , to ${\ Displaystyle c (\ pi ,B)=\suma _{i=0}^{T-1}w_{v_{i},v_{i+1}}}$ ; w przeciwnym razie niech do $\ Displaystyle c (\ pi, B) = \ infty}$ .

Innymi słowy, oceniamy politykę na podstawie krawędzi, o których wiemy, że obecnie znajdują się na wykresie ( ), $a$ , o których wiemy, że mogą znajdować się na wykresie ( $}}$ ${\ displaystyle F_ {i}$ ). Kiedy robimy krok na wykresie, krawędzie padające na nasze nowe położenie stają się nam znane. Te krawędzie, które są na wykresie, są dodawane do $tego, czy krawędzie znajdują się na wykresie$ zbioru nieznanych krawędzi. ${\ displaystyle F_ {i}}$ . Jeśli cel nigdy nie zostanie osiągnięty, mówimy, że mamy nieskończony koszt. Jeśli cel zostanie osiągnięty, koszt przejścia definiujemy jako sumę kosztów wszystkich pokonanych krawędzi z kardynalnością.

Na koniec definiujemy problem kanadyjskiego podróżnika.

uwagę

instancję CTP

{\ Displaystyle (V, E, F, s, t, r)}

zdecyduj, czy istnieje taka polityka że dla każdej realizacji

{\ Displaystyle (V, B) \ in {\ mathcal {G}} (V, E, F)}

, koszt

{\ Displaystyle c (\ pi, B)}

zasady jest nie więcej niż r razy optymalna w trybie offline,

{\ Displaystyle d_ {B} (s, t)}

.

Papadimitriou i Yannakakis zauważyli, że definiuje to grę dla dwóch graczy , w której gracze rywalizują o koszt swoich odpowiednich ścieżek, a zestaw krawędzi jest wybierany przez drugiego gracza (naturę).

Złożoność

W oryginalnym artykule przeanalizowano złożoność problemu i zgłoszono, że jest on PSPACE-complete . Pokazano również, że znalezienie optymalnej ścieżki w przypadku, gdy każda krawędź ma powiązane prawdopodobieństwo bycia w grafie (i-SSPPR) jest problemem PSPACE-łatwym, ale ♯P- trudnym . Wypełnienie tej luki stanowiło otwarty problem, ale od tego czasu okazało się, że zarówno wersja skierowana, jak i niekierowana są trudne w PSPACE.

Ukierunkowana wersja problemu stochastycznego jest znana w badaniach operacyjnych jako problem stochastycznej najkrótszej ścieżki z regresem.

Aplikacje

Mówi się, że problem ma zastosowanie w badaniach operacyjnych , planowaniu transportu, sztucznej inteligencji , uczeniu maszynowym , sieciach komunikacyjnych i wyznaczaniu tras. Zbadano wariant problemu dla nawigacji robota z probabilistycznym rozpoznawaniem punktów orientacyjnych.

Otwarte problemy

Pomimo wieku problemu i wielu potencjalnych zastosowań, wiele naturalnych pytań wciąż pozostaje otwartych. Czy istnieje przybliżenie o stałym współczynniku, czy też problem APX jest trudny? Czy i-SSPPR #P-kompletny? Jeszcze bardziej fundamentalne pytanie pozostało bez odpowiedzi: czy istnieje wielomianowy opis optymalnej polityki, odkładając na chwilę czas potrzebny do obliczenia opisu?

Zobacz też

Notatki

CH Papadimitriou; M. Yannakakis (1989). „Najkrótsze ścieżki bez mapy”. Notatki z wykładów z informatyki . proc. 16. ICALP. Tom. 372. Springer-Verlag . s. 610–620.
Dror Fried; Salomon Eyal Shimony; Amit Benbassat; Cenny Wenner (2013). „Złożoność wariantów problemów kanadyjskiego podróżnika” . Informatyka teoretyczna . 487 : 1–16. doi : 10.1016/j.tcs.2013.03.016 . S2CID 17810202 .
Davida Kargera; Evdokia Nikolova (2008). „Dokładne algorytmy dla problemu kanadyjskiego podróżnika na ścieżkach i drzewach”. {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
Zahy Bnaya; Ariela Felnera; Solomon Eyal Shimony (2009). Kanadyjski podróżnik Problem z teledetekcją . Międzynarodowa wspólna konferencja na temat sztucznej inteligencji (IJCAI).