这是什么样的迷宫解决算法？

Question

我试图弄清楚这个算法是否是A*(A-Star)算法或其他什么,但我仍然感到困惑.

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

这是迭代而不是递归编写的深度优先搜索。

递归 DFS（预排序）伪代码如下所示：

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

DFS 的迭代版本如下所示：

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

Iterative 版本中的Unvisited 和 NotVisiting表示该节点之前既没有被访问过，也没有在栈中进行访问。

该算法的时间复杂度取决于图是存储为邻接表还是邻接矩阵。对于列表，它将是 O(n)。对于矩阵，它会变成 O(n ² ) 因为即使您只探索每个节点一次，您也必须访问矩阵的每一行和每一列才能知道节点 X 和节点 Y 之间是否存在路径。

该算法的空间复杂度可以达到 O(n) 的最坏情况，当图中每个节点只有一个邻居时就会发生，变得像一个单链表。

Answer 2

根据您所显示的内容，我会说这是深度优先搜索，但要检查该地点是否已安排参观。由于它使用堆栈，因此它总是首先访问搜索树中较深的位置。但从它向堆栈添加一个位置的那一刻起，它就会将该位置标记为解决方案标记，以防止在另一条路径到达同一位置时重新评估它。

但请注意，它将标记每个图块 a SOLUTION_MARK，除非它无法找到除标有 aSOLUTION_MARK或 an之外的其他节点ERROR_MARK。因此，它将标记比贡献（最短）解决方案的图块更多的图块。从这个意义上说，它并不是真正的迷宫求解算法：它只是标记图块，就好像SOLUTION_MARK至少还有另一个尚未安排的图块可以为解决方案做出贡献。如果算法已标记了所有可到达的图块，则该算法将完成。