Welche Art von Labyrinth Solving-Algorithmus ist das?

Question

Ich versuche, wenn dieser Algorithmus A * ist, um herauszufinden, (A-Star) Algorithmus oder was auch immer, aber ich bin immer noch verwirrt.

Stack<Cell> stack = new Stack<>(); 

stack.push(maze.start()); 
stack.peek().mark(SOLUTION_MARK); 

while (!stack.peek().hasMark(Cell.END)) { 

    Cell current = stack.peek(); 
    ArrayList<Cell> dirs = current.neighbors(); 

    boolean found = false; 
    for (Cell next : dirs) { 
     if (next.hasMark(ERROR_MARK) || next.hasMark(SOLUTION_MARK)) { 
      continue; 
     } 
     stack.push(next); 
     next.mark(SOLUTION_MARK); 
     found = true; 
     break; 
    } 
    if (!found) { 
     stack.pop().mark(ERROR_MARK); 
    } 
    for (MazeBody listener : listeners) { 
     listener.repaint(); 
    } 
} 

Mark.java

public final class Mark { 

    private static Map<String, Mark> TABLE = new HashMap<>(); 

    private String name; 

    private Mark(String markName) { 
     name = markName; 
    } 

    public static Mark get(String name) { 
     Mark mark = TABLE.get(name); 
     if (mark == null) { 
      mark = new Mark(name); 
      TABLE.put(name, mark); 
     } 
     return mark; 
    } 
} 

Answer 1

Nach dem, was Sie zeigen, ich würde sagen, es Tiefensuche ist, aber mit einem Scheck, ob der Ort bereits für den Besuch geplant. Da es einen Stapel verwendet, wird es immer zuerst die Orte tiefer im Suchbaum besuchen. Aber von dem Moment es ein Ort, an dem Stapel hinzufügt, den Platz als Lösung Zeichen markiert es zu verhindern, dass neubewerteter wenn ein anderer Weg den gleichen Platz erreichen würde.

ist jedoch zu beachten, dass es jede Fliese ein SOLUTION_MARK markieren wird, wenn es nicht mit Knoten anderen kommen kann, als mit einem SOLUTION_MARK markiert oder einem ERROR_MARK. Es markiert somit mehr Fliesen als die Fliesen, die zur (kürzesten) Lösung beitragen. In diesem Sinne ist es nicht wirklich ein Labyrinth Lösungsalgorithmus: es einfach markiert Fliesen als SOLUTION_MARK, wenn mindestens eine andere Fliese noch nicht geplant ist, dass zu einer Lösung beitragen kann. Der Algorithmus wird beendet, wenn alle erreichbaren Kacheln markiert wurden.

Answer 2

Dies ist Tiefe erste Suche geschrieben iterativ anstatt rekursiv.

rekursive DFS (Preorder) Pseudo-Code wie folgt aussieht:

visit (current node) 
for each child node of current node 
    if node is not explored 
     dfs (node) 

Iterative Version von DFS wie folgt aussieht:

Put current node on stack 
In a while loop pop the stack if not empty 
    visit (popped node) 
    push all Unvisited and NotVisiting neighbors of popped node on the stack 
End while 

Unvisited und NotVisiting in der Iterative Version bedeutet, dass der Knoten weder besucht vorher, noch ist es im Stapel für den Besuch.

---

Die Zeitkomplexität dieses Algorithmus hängt davon ab, ob der Graph hat als Adjazenzliste oder Adjazenzmatrix gespeichert. Für die Liste wäre es O (n). Für Matrix, würde es werden O (n), denn auch wenn Sie nur einmal pro Knoten erkunden, müssen Sie jede Zeile und Spalte der Matrix besuchen zu wissen, ob es einen Weg zwischen einem Knoten X und dem Knoten Y. ist

Die Raumkomplexität dieses Algorithmus kann zum schlechtesten von O (n) gehen, wenn der Graph jeden Knoten mit nur einem Nachbarn hätte, der wie eine einfach verknüpfte Liste wird.