Durchsuchen eines Multi-Zweig-Diagramms und Zurückgeben eines Pfads [C#]

Question

In meiner Situation habe ich Gebietsobjekte. Jedes Gebiet weiß über ein Array, mit welchen anderen Gebieten es verbunden ist. Hier eine Darstellung der Gebiete, wie sie auf einer Karte erscheinen würden:

Wenn Sie die Verbindungen auf einem Diagramm kartieren sind, sie würde wie folgt aussehen:

Also sagen, ich habe eine Einheit im Gebiet [b] stationiert und ich möchte es in das Gebiet bewegen [e], ich bin auf der Suche nach einer Methode der Suche durch dieses Diagramm und die Rückgabe eines endgültigen Array, das den Pfad meine Einheit im Gebiet [b] muss ta ke. In diesem Szenario würde ich suchen werden, damit es

[b, e]. 

zurückzukehren Wenn ich von Territorium [a] zu Gebiet gehen wollte [f] dann wäre es zurück:

[a, b, e, f]. 

würde ich Beispiele lieben, aber auch nur Posts, die mich in die richtige Richtung weisen, werden geschätzt. Danke im Voraus! :)

Answer 1

Haben Sie schon von Breathth-First Search (BFS) gehört?

Grundsätzlich Sie einfach Ihr erstes Gebiet setzen, „a“ in Ihrem Beispiel in eine ansonsten leere Warteschlange Q

Die zweite Datenstruktur, die Sie brauchen, ist eine Reihe von booleans mit so vielen Elementen wie Sie Territorien haben, in diesem Fall 9. Es hilft beim Erinnern, welche Gebiete wir bereits überprüft haben. Wir nennen es V (für "besucht"). Es muss wie folgt initialisiert werden: Alle Elemente sind gleich falsch mit Ausnahme desjenigen, das dem ursprünglichen Quadrat entspricht. Das heißt, für alle Gebiete t haben wir V [t] = falsch, aber V [a] = wahr, weil "a" bereits in der Warteschlange ist.

Die dritte und letzte Datenstruktur, die Sie benötigen, ist ein Array zum Speichern der Elternknoten (d. H. Welcher Knoten wir kommen). Es hat auch so viele Elemente wie Sie Territorien haben. Wir nennen es P (für "Eltern") und jedes Element zeigt anfänglich auf sich selbst, dh für alle t in P gilt P [t] = t.

Dann ist es ganz einfach:

while Q is not empty: 
    t = front element in the queue (remove it also from Q) 
    if t = f we can break from while loop //because we have found the goal 
    for all neighbors s of t for which V[s] = false: 
     add s into the back of Q //we have never explored the territory s yet as V[s] = false 
     set V[s] = true //we do not have to visit s again in the future 

     //we found s because there is a connection from t to s 
     //therefore, we need to remember that in s we are coming from the node t 
     //to do this we simply set the parent of s to t: 
     P[s] = t 

Wie beurteilen Sie die Lösung jetzt lesen?

Überprüfen Sie einfach das übergeordnete Element von f, dann das übergeordnete Element und dann das übergeordnete Element und so weiter, bis Sie den Anfang gefunden haben. Sie werden wissen, was der Anfang ist, sobald Sie ein Element gefunden haben, das sich selbst als Elternteil hat (denken Sie daran, dass wir sie anfänglich auf sich selbst zeigen lassen) oder Sie können es auch einfach mit einem vergleichen. Grundsätzlich , Sie benötigen nur eine leere Liste L, fügen f hinein und dann

while f != a: 
    f = P[f] 
    add f into L 

Beachten Sie, dass dies nicht gelingt offensichtlich, wenn es keinen Weg gibt es, weil f nie eine gleich. Daher ist diese:

while f != P[f]: 
    f = P[f] 
    add f into L 

ist ein bisschen schöner. Es nutzt die Tatsache aus, dass anfänglich alle Gebiete in P auf sich selbst verweisen.

Wenn Sie dies auf dem Papier versuchen, oben mit Ihnen beispielsweise, dann werden Sie sich mit L enden = [f, e, b, a] Wenn Sie einfach diese Liste umkehren, dann haben Sie, was Sie wollten.

Ich weiß nicht, C#, also habe ich nicht die C# -Syntax zu verwenden. Ich nehme an, dass Sie wissen, dass es am einfachsten ist, Ihre Territorien mit Ganzzahlen zu indizieren und dann ein Array zu verwenden, um auf sie zuzugreifen.

Sie werden ziemlich schnell erkennen, warum das funktioniert. Es wird Breitensuche genannt, weil Sie zuerst nur Nachbarn des Gebiets "a" betrachten, mit trivialem kürzestem Weg zu ihnen (nur 1 Rand) und erst wenn Sie alle diese bearbeitet haben, dann werden weiter entfernte Gebiete in der Warteschlange erscheinen (nur 2 Kanten von Anfang an) und so weiter. Aus diesem Grund verwenden wir eine Warteschlange für diese Aufgabe und nicht etwa einen Stapel.

Auch dies ist linear in der Anzahl der Gebiete und Kanten, weil Sie nur jedes Gebiet und Rand (höchstens) einmal (obwohl Kanten aus beiden Richtungen) betrachten müssen.

Der Algorithmus, den ich Ihnen gegeben habe, ist im Grunde der gleiche wie https://en.wikipedia.org/wiki/Breadth-first_search mit nur der P-Datenstruktur hinzugefügt, um zu verfolgen, woher Sie kommen, um in der Lage zu sein, den Pfad herauszufinden.