Graphsuchalgorithmus

Question

Ich suche einen Graphalgorithmus mit einigen ungewöhnlichen Eigenschaften.

Jede Kante im Diagramm ist entweder eine „Aufwärts“-Kante oder eine „Abwärts“-Kante.

Ein gültiger Pfad kann über eine unbegrenzte Anzahl von „Aufwärts“-Schritten gefolgt von einer unbegrenzten Anzahl von „Abwärts“-Schritten führen oder umgekehrt.Es kann jedoch nicht mehr als einmal die Richtung ändern.

ZB ein gültiger Weg könnte ein "Up" B "Up" C "Down" e "down" f Ein ungültiger Pfad könnte ein "Up" B "Down" C "Up" d sein d sein

Was ist ein guter Algorithmus, um den kürzesten gültigen Pfad zwischen zwei Knoten zu finden?Wie wäre es, alle kürzesten Wege gleicher Länge zu finden?

Answer 1

Vorausgesetzt, Sie haben keine Heuristik, eine Variation davon Dijkstras Algorithmus sollte ziemlich gut ausreichen.Speichern Sie jedes Mal, wenn Sie eine neue Kante in Betracht ziehen, Informationen über ihre „Vorfahren“.Überprüfen Sie dann die Invariante (nur eine Richtungsänderung) und gehen Sie zurück, wenn sie verletzt wird.

Die Vorfahren sind hier 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 und D unten ist, könnten es die Vorfahren einer bestimmten Kante sein UUUDDDD, das wäre das Paar 3, 4.Aufgrund der Invariante benötigen Sie keine dritte Zahl.

Da wir den Dijkstra-Algorithmus verwendet haben, ist die Suche nach mehreren kürzesten Pfaden bereits erledigt.

Answer 2

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 Aufwärtskanten und einen mit allen Abwärtskanten und mit gerichteten Kanten zwischen allen Knoten in Graph eins und dem entsprechenden Knoten in Graph zwei.

Lösen Sie zuerst, ob die Gleichung in Diagramm eins beginnt und in Diagramm zwei endet, und dann umgekehrt, und überprüfen Sie dann die kürzeste Lösung.

Answer 3

Man würde meinen, Ihr Standard BFS sollte hier funktionieren.Wann immer Sie der offenen Liste einen Knoten hinzufügen, können Sie ihn in eine Struktur einschließen, die festlegt, welche Richtung er verwendet (nach oben oder unten), und ein boolesches Flag, das angibt, ob er die Richtung bereits geändert hat.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, beziehen Sie die Anzahl der bisher durchlaufenen Kanten in Ihre Struktur ein.Wenn Sie Ihren ersten kürzesten Pfad gefunden haben, notieren Sie sich die Pfadlänge und fügen Sie der offenen Liste keine Knoten mehr hinzu.Gehen Sie die verbleibenden Knoten in der Liste weiter durch, bis Sie alle Pfade mit der aktuellen Länge überprüft haben, und hören Sie dann auf.

Answer 4

A* Mit einer speziell entwickelten Kosten- (G-Score) und heuristischen (H-Score) Funktion kann dies bewältigt werden.

Für die Kosten könnten Sie die Anzahl der Richtungsänderungen im Pfad verfolgen und bei der zweiten Änderung unendliche Kosten hinzufügen (d. h.unterbrechen Sie die Suche nach diesen Zweigen).

Die Heuristik erfordert etwas mehr Überlegung, insbesondere wenn Sie die Heuristik zulässig (minimaler Abstand zum Ziel wird nie überschätzt) und monoton halten möchten.(Nur so kann garantiert werden, dass A* eine optimale Lösung findet.)

Vielleicht sind weitere Informationen über die Domäne verfügbar, um die Heuristik zu erstellen?(d. h.x,y-Koordinaten der Knoten im Diagramm?)

Abhängig von der Größe des Diagramms, das Sie lösen möchten, können Sie natürlich zunächst einfachere Algorithmen wie die Breitensuche oder den Dijkstra-Algorithmus ausprobieren:Grundsätzlich reicht jeder Suchalgorithmus aus, und für jeden benötigen Sie sowieso eine Kostenfunktion (oder ähnliches).

Answer 5

Wenn Sie beispielsweise über eine Standard-Grafiksuchfunktion verfügen Graph.shortest(from, to) In einer Bibliothek können Sie in C#/Pseudocode eine Schleife ausführen und minimieren:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

Wenn Sie sich den Mindestpfad/die Mindestpfade merken müssen und Ihre Standardfunktion Ihnen die Daten zurückgibt, können Sie dies auch aussprechen

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

Wo myMin sollte zwei vergleichen [fst, nxt, C, AC, BD] Tupel und verlassen Sie dasjenige mit der geringeren Distanz oder beides und nehmen Sie an reduce ist eine intelligente Funktion.

Dies führt zu einem gewissen Speicheraufwand, wenn unsere Diagramme groß sind und überhaupt keinen Speicher verbrauchen (was möglich ist, wenn sie dynamisch generiert werden), aber meiner Meinung nach nicht wirklich zu einem Geschwindigkeitsaufwand.