Graph Suchalgorithmus

Unter der Annahme, dass Sie keine Heuristiken haben, sollte eine Variation des Algorithmus von Dijkstra ausreichen. Jedes Mal, wenn Sie einen neuen Vorteil in Betracht ziehen, speichern Sie Informationen über seine "Vorfahren". Überprüfen Sie dann die Invariante (nur eine Richtungsänderung) und die Rückverfolgung, wenn sie verletzt wird.

Die Vorfahren hier sind alle Kanten, die durchlaufen wurden, um auf dem kürzesten Weg zum aktuellen Knoten zu gelangen. Eine gute Möglichkeit, die Vorfahreninformationen zu speichern, wäre ein Zahlenpaar. Wenn U oben ist und D unten ist, könnte der Ahnen einer bestimmten Kante UUUDDDD sein, was das Paar 3, 4 wäre. Sie werden keine dritte Zahl wegen der Invariante brauchen.

Da wir den Algorithmus von Dijkstra verwendet haben, ist die Suche nach kürzesten Wegen bereits erledigt.

Vielleicht können Sie Ihren Graphen in einen normalen gerichteten Graphen umwandeln und dann vorhandene Algorithmen verwenden.

Eine Möglichkeit wäre, den Graphen in zwei Graphen aufzuteilen, einen mit allen aufsteigenden Kanten und einen mit allen abfallenden Kanten und mit gerichteten Kanten zwischen allen Knoten in Graphen eins und dem entsprechenden Knoten in Graphen zwei.

Lösen Sie zuerst, um in Diagramm eins zu beginnen und in Diagramm zwei zu enden und dann umgekehrt, dann überprüfen Sie die kürzeste Lösung.

Man sollte denken, dass Ihr Standard BFS hier funktionieren sollte. Wenn Sie der geöffneten Liste einen Knoten hinzufügen, können Sie ihn in eine Struktur umbrechen, die angibt, in welcher Richtung er verwendet wird (nach oben oder nach unten), und ein boolesches Flag, das angibt, ob die Richtung noch geändert wurde. Diese können verwendet werden, um zu bestimmen, welche ausgehenden Kanten von diesem Knoten gültig sind.

Um alle kürzesten Pfade gleicher Länge zu finden, schließen Sie die Anzahl der Kanten ein, die in Ihrer Struktur bisher durchlaufen wurden. Wenn Sie Ihren ersten kürzesten Pfad gefunden haben, notieren Sie sich die Pfadlänge und fügen Sie der geöffneten Liste keine Knoten hinzu. Durchlaufen Sie die verbleibenden Knoten in der Liste, bis Sie alle Pfade der aktuellen Länge überprüft haben, und stoppen Sie dann.

A * mit einer speziell gestalteten Kosten (G-Score) und heuristischen (H-Score) -Funktion kann damit umgehen .

Bei den Kosten könnten Sie die Anzahl der Richtungsänderungen im Pfad verfolgen und bei der zweiten Änderung unendliche Kosten hinzufügen (dh die Suche nach diesen Zweigen abbrechen).

Die Heuristik braucht etwas mehr Gedanken, vor allem, wenn Sie die Heuristik zulässig (überschätzen nie Mindestabstand zum Ziel) und monoton wollen. (Nur so kann garantiert werden, dass A * eine optimale Lösung findet.)

Vielleicht gibt es mehr Informationen über die Domäne, die zum Erstellen der Heuristik verfügbar ist? (dh x, y Koordinaten der Knoten im Graphen?)

Natürlich können Sie, abhängig von der Größe des Graphen, den Sie lösen möchten, zuerst einfachere Algorithmen wie die erste Breitensuche oder den Dijkstra-Algorithmus ausprobieren: im Grunde geht jeder Suchalgorithmus, und für jeden benötigen Sie eine Kostenfunktion ( oder ähnlich) sowieso.