Motywacja

Pewnego dnia podróżowałem po mieście środkami transportu publicznego i stworzyłem interesujący problem graficzny, modelujący problem znalezienia najkrótszego połączenia między dwoma miejscami.

Wszyscy znamy klasyczny „problem najkrótszej ścieżki”: biorąc pod uwagę ukierunkowany wykres o długości krawędzi i dwóch wierzchołkach , znalezienie najkrótszej ścieżki pomiędzy i (to znaczy ścieżka minimalizację całkowitej długości krawędzi). Zakładając nieujemne długości krawędzi, istnieją różne algorytmy, a problem jest łatwy.w e ∈ R + 0$G=(V,E)$s , t ∈ V s $w_e\in\mathbb{R}_0^+,\,e\in E$$s,t\in V$$s$$t$

Jest to dobry model na przykład w przypadku, gdy idziemy. Wierzchołki są skrzyżowaniem w naszej sieci dróg, a każda krawędź ma stałą długość - na przykład w metrach. Inną możliwą interpretacją wag krawędzi jest czas , jaki zajmuje nam przejście od jednego z jego wierzchołków do drugiego. Ta interpretacja mnie teraz interesuje.$w_e$

Problem

Chcę teraz modelować następującą sytuację. Chcę podróżować z punktu A do punktu B w mieście transportem publicznym i zminimalizować czas . Sieć transportu publicznego można łatwo modelować jako ukierunkowany wykres, tak jak można się spodziewać. Interesującą częścią są wagi krawędzi (ten model czasu) - transport publiczny (na przykład autobusy) odjeżdża tylko w określonych odstępach czasu, które są różne dla każdego przystanku (wierzchołek na wykresie). Innymi słowy - wagi krawędzi nie są stałe, zmieniają się w zależności od czasu, w którym chcemy użyć krawędzi.

Sposób modelowania tej sytuacji: Mamy skierowaną wykres oraz krawędzi masy funkcji , które ma czas jako argument i zwraca czas potrzebny na wykorzystanie krawędzi na naszej ścieżce. Na przykład, jeśli autobus z wierzchołka do wierzchołka odjeżdża o i zajmuje to czasu, a my osiągamy wierzchołek przy , to jest wagą krawędzi. Oczywiście .w : E × R + 0 → R + 0 v u t = 10 5 v t = 8 w ( v u , 8 ) = 7 w ( v u , 10 ) = $G=(V,E)$ $w\colon E\times \mathbb{R}_0^+\rightarrow\mathbb{R}_0^+$$v$$u$$t=10$$5$$v$$t=8$$w(vu,8)=7$$w(vu,10)=5$

Określenie całkowitej masy ścieżki jest nieco trudne, ale możemy to zrobić rekurencyjnie. Niech będzie ścieżką skierowaną. Jeśli to . W przeciwnym razie , gdzie jest ścieżką podrzędną bez . Jest to naturalna definicja odpowiadająca rzeczywistej sytuacji. k = 1 w ( P ) = 0 w ( P ) = w ( P ′ ) + w ( v k - 1 v k , w ( P ′ ) ) P ′ P v $P=v_1v_2\ldots v_{k-1} v_k$$k=1$$w(P)=0$$w(P)=w(P')+w(v_{k-1}v_k,w(P'))$$P'$$P$$v_k$

Możemy teraz przestudiować problem przy różnych założeniach dotyczących funkcji . Naturalnym założeniem jest który modeluje „oczekiwanie na time”.$w$

Jeśli funkcja „zachowuje się ładnie”, możliwe jest zredukowanie tego problemu do klasycznego problemu Najkrótszej ścieżki. Ale moglibyśmy zapytać, co się stanie, gdy szaleją funkcje wagowe. A co, jeśli porzucimy założenie oczekiwania?

pytania

Moje pytania są następujące.

• Czy wcześniej zadawano ten problem? Wydaje się to trochę naturalne.
• Czy są na to jakieś badania? Wydaje mi się, że istnieją różne podproblemy, które należy zadać i zbadać - głównie w odniesieniu do właściwości funkcji wagi.
• Czy możemy sprowadzić ten problem (być może przy pewnych założeniach) do klasycznego problemu najkrótszej ścieżki?

Jest to znane jako problem „najkrótszej ścieżki zależnej od czasu”. Rzeczywiście przeprowadzono badania nad tym problemem; patrz na przykład klasyczny papier Ordy i Roma oraz ten najnowszy papier SODA, który dowodzi, że gdy funkcja ciężaru każdej krawędzi jest wielomianowo-liniowo kawałkowa, wówczas najkrótsza ścieżka między dwoma stałymi punktami zmienia się razy .$n^{\Theta(\log n)}$

Algorytm Dijkstry można rzeczywiście zastosować w przypadku tego problemu, gdy narzucona jest zasada oczekiwania, to znaczy poczekaj w węźle, jeśli skróci to czas przybycia. Bez zasady oczekiwania sytuacja jest znacznie bardziej szalona: najkrótsza ścieżka może nie być prosta, podścieżka najkrótszej ścieżki może nie być najkrótsza między dwoma punktami końcowymi podścieżki, ścieżki przechodzące przez nieskończoną liczbę krawędzi mogą mieć skończony czas przybycia itp. Zobacz ponownie artykuł Ordy i Roma, aby uzyskać więcej dyskusji.

Czy zdajesz sobie sprawę z problemu „najkrótszych ścieżek, które nie zmniejszają się”? Zdefiniowano go do modelowania takich sytuacji. Chociaż jest to nieco mniej wyraziste w porównaniu z twoją formułą, istnieją szybkie glony.

Jeśli przyjmiesz, że czasy są integralne (co ma sens w przypadku transportu publicznego), możesz stworzyć sieć rozszerzoną w czasie, podobną do tej sugerowanej przez Forda-Fulkersona dla maksymalnego przepływu w czasie (lub najszybszego przepływu) i zamiast tego znajdź najkrótszą ścieżkę na tym wykresie.