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

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;
    }
}

- Abdelrahman Wahdan

---

你的代码不完整，参考http://stackoverflow.com/help/mcve。并添加相关的语言标签（我知道这是Java，但我不应该去猜测）。 - jub0bs

你能提供mark的定义吗？在我看来，这似乎是一个简单的深度优先搜索，但具有全局标记已访问的功能。 - Willem Van Onsem

@LucasMoeskops：不，它标记已经访问过的位置。因此，它将在最多O（n ^ 2）中运行，其中n是单元格数。 - Willem Van Onsem

@WillemVanOnsem 添加了 Mark.java 代码。 - Abdelrahman Wahdan

@WillemVanOnsem 我发现发布后，所以我删除了评论 :-) 我的意思是，除了遍历所有节点（像A*算法一样向“最便宜”的方向移动）之外，没有其他优化。 - Lucas Moeskops

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和NotVisiting”表示该节点既没有被访问过，也不在等待访问的堆栈中。

---

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

该算法的空间复杂度可能会最坏达到O(n)，当图上的每个节点只有一个邻居时，它就像一个单链表。

- displayName

---

我认为值得一提的是它进行了出现次数检查：检查节点是否已经被添加到堆栈中。 - Willem Van Onsem

@WillemVanOnsem：已更新。 - displayName

Answer 2

根据您所提供的信息，我认为这是一种深度优先搜索，但会检查是否已经安排了访问的位置。由于它使用堆栈，它将始终首先访问搜索树中较深的位置。但自从它把一个地方添加到堆栈后，就将该地方标记为解决方案标记以防止它被重新评估，如果另一条路径到达相同的位置。

但是请注意，除非它找不到其他未标记为SOLUTION_MARK或ERROR_MARK的节点，否则它将标记每个图块为SOLUTION_MARK。因此，它标记的瓷砖数量比对（最短）解决方案有贡献的瓷砖多。从这个意义上说，它并不是真正的迷宫求解算法：如果存在至少另一个尚未安排的瓷砖可以为解决方案做出贡献，它只会将瓷砖标记为SOLUTION_MARK。如果已标记所有可到达的瓷砖，则算法将完成。

- Willem Van Onsem

---

因此，复杂度为O(n^2)，其中n是访问的单元格总数，无论其是否标记为“错误”或“解决方案”，对吗？ - Abdelrahman Wahdan

@AbdelrahmanWahdan：如果每个邻居都可以有n个单元，是的。假设你只能朝着4个方向移动，时间复杂度为O(n)。 - Willem Van Onsem