java - 这是什么迷宫求解算法？

Question

我想弄清楚这个算法是 A*(A 星)算法还是其他什么，但我仍然很困惑。

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

Unvisited and NotVisiting在Iterative版本中表示该节点之前没有被访问过，也不在栈中等待访问。

---

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

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