Astar mit zeitabhängigem Graph

Question

Ich habe ein Diagramm, das ein Routennetzwerk darstellt - Wegpunkte sind Knoten und Routen sind Kanten. Das Problem ist, dass es Regionen zwischen den Wegpunkten geben kann, die zu bestimmten Zeiten nicht überquert werden können. Diese Regionen beeinflussen jedoch nicht notwendigerweise Eckpunkte, sondern nur Kanten.

Ich nutze Zeit als Kostenfunktion, also für jeden Eckpunkt (und damit Kante) kann ich die Ankunftszeit innerhalb der Besucher und/oder Heuristik bekommen. Da die Gewichtskarte jedoch lesbar ist, kann ich die Gewichtung einer Kante nicht ändern, um sie zu "zu lang" zu machen.

Auf der anderen Seite kann ich keine benutzerdefinierte Weightmap erstellen, da ich die Ankunftszeit nicht im Voraus weiß, da sie vom Pfad abhängt.

Was ich im Forum herausgefunden habe, ist, die Heuristik zu verwenden und sie im Falle eines "schlechten" Scheitelpunktes auf inf zu setzen. Aber was ich brauche, ist "schlechte" Kanten zu wählen.

Haben Sie eine Idee über den Zugriff auf die aktuell untersuchte Kante innerhalb der Heuristik (standardmäßig ist die einzige Eingabe der Vertexdeskriptor)?

Ich weiß, dass ich im execute_edge-Besucher Entscheidungen treffen könnte, aber was soll ich sagen, um zu wissen, dass diese Kante schlecht ist und nicht verwendet werden sollte? Vielleicht könnte ich eine externe boolesche "Bad Edge" -Eigenschaftskarte erstellen (für alle Scheitelpunkte) und wenn die aktuelle Kante "schlecht" ist, den Zielscheitel innerhalb des examine_edge-Besuchers auf true setzen? Auf diese "schlechte Kante" -Eigenschaftkarte könnte dann durch die Heuristik zugegriffen werden. Allerdings scheint mir dies nicht die beste Lösung zu sein.

Irgendeine andere Idee?

Vielen Dank im Voraus!

Answer 1

Ein gängiger Ansatz zum Lösen von Problemen wie diesen besteht darin, einen neuen Graphen zu erstellen, dessen Knoten mehr Informationen enthalten als die ursprünglichen Knoten. In diesem Fall sollten Sie in Erwägung ziehen, ein Diagramm mit mehreren Kopien jedes Knotens zu erstellen, eines für einen anderen möglichen Zeitpunkt. Dann muss jede Kante zwischen einem Knotenpaar liegen, wenn zwischen den entsprechenden Knoten zu den entsprechenden Zeitpunkten eine Kante vorhanden war. Zum Beispiel werden Kanten, die immer offen sind, Sie von einem Knoten zu einem bestimmten Zeitpunkt zum entsprechenden Knoten zu einem späteren Zeitpunkt bringen, und Kanten, die nur zu einem bestimmten Zeitpunkt aktiv sind, befinden sich nur zu diesen Zeitpunkten im Diagramm .

Dies hat den Nachteil, die Größe des Graphen in die Luft zu sprengen, aber wenn Sie die Option haben, den Graphen einfach auszuwerten, könnte dieser Ansatz durchaus sinnvoll sein.