Wie kürzesten Weg in dieser Art von Labyrinth

Question

Red Dot - Represents the initial location 
Black Dot - Already occupied 
Green - Free to occupy 
Destination - Boundry of the matrix [which means either x = 0 or y = 0 or x = 8 or y = 8] 

Beispiel zu finden:

Die red dot kann sie setzen nur ein Schritt zu einer Zeit, und sechs in eines der grünen bewegen kann Kreise, die daran befestigt sind. Was wird die schnellste Methode sein, um den kürzesten Weg in dieser Art von Labyrinth zu berechnen.

Answer 1

Zuerst brauchen Sie Dijkstra nicht, weil alle Werte der Kanten gleich sind. Sie können einen einfachen BFS oder DFS Algorithmus verwenden. Worst Case-Komplexitäten sind die gleichen, aber ich würde BFS verwenden, da es eine bessere durchschnittliche Komplexität hat. O (| V | + | E |) ist jedoch das schnellste, das Sie hier finden können, und es ist bewiesen.

Wie wird Ihr Diagramm dargestellt? Der beste Weg ist, eine Liste der Nachbarn für jede Node zu halten. Schwarze Punkte aus Ihrem Beispiel werden nicht als Nachbarn gezählt. In Ihrem Beispiel würde jeder Knoten 0 (vollständig von schwarzen Punkten bedeckt) zu 6 Nachbarn haben. Dann können Sie über diese Listen alles erreichen, was Sie von jedem Knotenpunkt aus erreichen können.

Der BFS-Algorithmus verfügt über eine Eigenschaft, die jedem Knoten eine Ebene zuweist, was bedeutet, wie weit er von einem Startknoten entfernt ist. Du beginnst an deinem Startpunkt und dein aktueller Layer ist 0. Dann folgst du einfach allen Knoten von einem aktuellen Layer (normalerweise in der Warteschlange) und versuchst, seine Nachbarn zu finden (aus ihrer Liste von Nachbarn), die keinen Layer haben zugewiesen und Sie weisen ihnen +1 höhere Ebene zu.Sobald Sie Ihren Knoten gefunden haben (der immer noch x, y als Attribute für die Grenzprüfung (oder den Eigenschaftsboolrand) haben kann), wissen Sie am Rand Ihres Labyrinths, dass es so weit wie der Layer-Wert ist. Wenn Sie den genauen Weg drucken möchten, müssen Sie nur zurück (über Ihre Listen von Nachbarn) finden, die die Bedingung erfüllt, dass jeder Schritt bei -1 Schicht niedriger ist. Dies wird den Weg von Ende zu Anfang drucken, aber ich bin sicher, dass Sie Ihr Ergebnis mit ein wenig Hilfe von Stack Datenstruktur bekommen werden :)

Answer 2

Was Sie haben, ist ein "einfaches" Grafikproblem. Die Graph-Konnektivität ist die legale Bewegung, die Sie haben. Der Startknoten ist Ihr roter Punkt. Um einen einzelnen Terminalknoten zu erhalten, erfinde einen weiteren Kreis außerhalb des gegebenen Labyrinths; Verbinden Sie alle echten Ausgangsknoten mit einer Nullkostenbewegung in den neuen Kreis.

Wenden Sie nun den Dijkstra-Algorithmus an. Erledigt.

---

Eine andere Möglichkeit, das Problem zu untersuchen, ist die Rekursion. Bewege den roten Punkt und markiere den alten Ort schwarz. Von der neuen Position zurückkehren. Kehren Sie beim Beenden (Rückweglänge 1) oder ohne legale Züge (Rückweglänge unendlich) zurück. Behalten Sie den kürzesten bekannten Pfad bei.

Haben Sie diese Probleme?

Answer 3

A * -Algorithmus

(aus: https://en.wikipedia.org/wiki/A*_search_algorithm)

Der folgende Pseudo-Code des Algorithmus beschreibt [zweifelhaft - besprechen]:

function A*(start,goal) 
    ClosedSet := {}  // The set of nodes already evaluated. 
    OpenSet := {start} // The set of tentative nodes to be evaluated, initially containing the start node 
    Came_From := the empty map // The map of navigated nodes. 


    g_score := map with default value of Infinity 
    g_score[start] := 0 // Cost from start along best known path. 
    // Estimated total cost from start to goal through y. 
    f_score := map with default value of Infinity 
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal) 

    while OpenSet is not empty 
     current := the node in OpenSet having the lowest f_score[] value 
     if current = goal 
      return reconstruct_path(Came_From, goal) 

     OpenSet.Remove(current) 
     ClosedSet.Add(current) 
     for each neighbor of current 
      if neighbor in ClosedSet 
       continue  // Ignore the neighbor which is already evaluated. 
     tentative_g_score := g_score[current] + dist_between(current,neighbor) // length of this path. 
     if neighbor not in OpenSet // Discover a new node 
      OpenSet.Add(neighbor) 
     else if tentative_g_score >= g_score[neighbor] 
      continue  // This is not a better path. 

     // This path is the best until now. Record it! 
     Came_From[neighbor] := current 
     g_score[neighbor] := tentative_g_score 
     f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal) 

return failure 

function reconstruct_path(Came_From,current) 
    total_path := [current] 
    while current in Came_From.Keys: 
     current := Came_From[current] 
     total_path.append(current) 
    return total_path 

so, soweit Ich verstehe - Sie können Ihren Startknoten an der Position des roten Punkts positionieren, und den Zielknoten als x = 0 oder y = 0 oder x = 8 oder y = 8 (Sie können 4 Funktionsaufrufe machen und das Minimum nehmen)

wie für die heuristischen Werte für den Knoten - setzen Sie einfach die schwarz blockierten Knoten sehr hohe heuristische Werte, die sie unerreichbar machen, also wird der Algorithmus um sie herumgehen.