Motivation

Neulich war ich mit öffentlichen Verkehrsmitteln in der Stadt unterwegs und habe mir ein interessantes Grafikproblem ausgedacht, das das Problem modelliert, die kürzeste Verbindung zwischen zwei Orten zu finden.

Wir alle kennen das klassische "Problem des kürzesten Weges": Gegeben ist ein gerichteter Graph mit Kantenlängen und zwei Eckpunkten finden Sie den kürzesten Pfad zwischen und (dh den Pfad, der die gesamte Kantenlänge minimiert). Unter der Annahme nicht negativer Kantenlängen gibt es verschiedene Algorithmen und das Problem ist einfach.$G=(V,E)$$w_e\in\mathbb{R}_0^+,\,e\in E$$s,t\in V$$s$$t$

Dies ist ein gutes Modell für den Fall, dass wir zum Beispiel gehen. Die Eckpunkte sind Kreuzungen in unserem Straßennetz und jede Kante hat eine feste Länge - zum Beispiel in Metern. Eine andere mögliche Interpretation der Kantengewichte ist die Zeit , die wir , um von einem ihrer Eckpunkte zum anderen zu gelangen. Dies ist die Interpretation, die mich jetzt interessiert.$w_e$

Problem

Ich möchte nun die folgende Situation modellieren. Ich möchte mit öffentlichen Verkehrsmitteln von Punkt A nach Punkt B in einer Stadt fahren und die Zeit minimieren . Das öffentliche Verkehrsnetz kann wie erwartet einfach als gerichteter Graph modelliert werden. Der interessante Teil sind die Kantengewichte (diese Modellzeit) - öffentliche Verkehrsmittel (z. B. Busse) fahren nur in bestimmten Intervallen ab, die für jede Haltestelle unterschiedlich sind (Scheitelpunkt in der Grafik). Mit anderen Worten - die Kantengewichte sind nicht konstant, sie ändern sich abhängig von der Zeit, zu der wir die Kante verwenden möchten.

Wie diese Situation zu modellieren: Wir haben einen gerichteten Graphen und eine Kante Gewicht Funktion das braucht Zeit als Argument und gibt die Zeit zurück , die erforderlich ist, um die Kante in unserem Pfad zu verwenden. Wenn zum Beispiel der Bus vom Scheitelpunkt zum Scheitelpunkt bei abfährt und es Mal dauert und wir bei Scheitelpunkt gelangen , dann ist das Kantengewicht. Es ist klar, dass .$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$

Es ist etwas schwierig, das Gesamtgewicht des Pfades zu definieren, aber wir können es rekursiv tun. Sei ein gerichteter Pfad. Wenn dann ist . Andernfalls ist , wobei der Unterpfad von ohne . Dies ist eine natürliche Definition, die der realen Situation entspricht.$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$

Wir können das Problem nun unter verschiedenen Annahmen zur Funktion . Die natürliche Annahme ist was "Warten auf Zeit" modelliert .$w$

Wenn sich die Funktion "gut verhält", kann dieses Problem möglicherweise auf das klassische Problem des kürzesten Pfades reduziert werden. Aber wir könnten fragen, was passiert, wenn die Gewichtsfunktionen wild werden. Und was ist, wenn wir die Annahme des Wartens fallen lassen?

Fragen

Meine Fragen sind die folgenden.

• Wurde dieses Problem schon einmal gestellt? Es scheint irgendwie natürlich.
• Gibt es irgendwelche Forschungen darüber? Es scheint mir, dass verschiedene Teilprobleme zu stellen und zu untersuchen sind - hauptsächlich in Bezug auf die Eigenschaften der Gewichtsfunktion.
• Können wir dieses Problem (möglicherweise unter bestimmten Voraussetzungen) auf das klassische Problem des kürzesten Weges reduzieren?

Dies ist als "zeitabhängiger kürzester Weg" bekannt. In der Tat wurde für dieses Problem geforscht; siehe zum Beispiel das klassische Papier von Orda und Rom und dieses kürzlich erschienene SODA-Papier, das beweist, dass sich der kürzeste Weg zwischen zwei Fixpunkten ändert, wenn die Gewichtsfunktion jeder Kante stückweise linear von Polynomgröße ist mal.$n^{\Theta(\log n)}$

Der Dijkstra-Algorithmus kann tatsächlich für dieses Problem verwendet werden, wenn die Warterichtlinie auferlegt wird, dh an einem Knoten warten, wenn dies die endgültige Ankunftszeit verringert. Ohne die Wartepolitik ist die Situation viel wilder: Der kürzeste Pfad ist möglicherweise nicht einfach, der Unterpfad eines kürzesten Pfades ist möglicherweise nicht der kürzeste zwischen den beiden Endpunkten des Unterpfads, Pfade, die durch eine unendliche Anzahl von Kanten verlaufen, haben möglicherweise eine begrenzte Ankunftszeit usw. Siehe noch einmal das Papier von Orda und Rom für weitere Diskussionen.

Kennen Sie das Problem "kürzeste nicht abnehmende Pfade"? Es wurde definiert, um Situationen wie diese zu modellieren. Obwohl es im Vergleich zu Ihrer Formulierung etwas weniger ausdrucksstark ist, gibt es schnelle Algen dafür.

Wenn Sie davon ausgehen, dass die Zeiten ganzheitlich sind (was im Fall von öffentlichen Verkehrsmitteln sinnvoll ist), können Sie ein zeitlich erweitertes Netzwerk erstellen, ähnlich dem von Ford-Fulkerson vorgeschlagenen für den maximalen Durchfluss über die Zeit (oder den schnellsten Durchfluss) und Suchen Sie stattdessen den kürzesten Pfad in diesem Diagramm.