What is the maze solution algorithm?

Question

I'm trying to figure out if this algorithm is an A * (A-Star) algorithm or something else, but still I'm confused.

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

This is the Depth of the first search written iteratively , not recursively.

The recursive DFS pseudocode (preorder) is as follows:

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

An iterative version of DFS looks like this:

 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 

Invisible and notVisiting in the iterative version means that the node is not visited before, nor is it on the stack for visiting.

---

the time complexity of this algorithm depends on whether the graph was saved as an adjacency list or adjacency matrix. For the list, this will be O (n). For a matrix, this will be O (n ² ), because although you examine each node only once, you need to visit each row and column of the matrix to find out if there is a path between a node X and node Y.

the complexity of the space of this algorithm can go to the worst of O (n), when the graph will have node only one neighbor, becoming like one list. p>

Answer 2

Based on what you show, I would say that this is a depth search, but with a check to see if this place has already been planned for a visit. Since he uses the stack, he will always first visit places deeper in the search tree. But from the moment he adds a place to the stack, he marks the place as a sign of the decision, to prevent his re-evaluation if the other way reaches the same place.

Note that he will mark every fragment of a SOLUTION_MARK if he cannot come up with nodes other than the marked SOLUTION_MARK or ERROR_MARK . Thus, this will mean more tiles than tiles that contribute to the (shortest) solution. In this sense, it is not an algorithm for solving the maze: it simply marks the tiles as SOLUTION_MARK , if there is an unplanned tile that can contribute to the solution. The algorithm will exit if it marks all available tiles.