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

发布时间：2020-12-14 06:04:20 所属栏目：Java 来源：网络整理

导读：我试图弄清楚这个算法是否是A *(A-Star)算法或其他什么,但我仍然感到困惑. StackCell stack = new Stack();stack.push(maze.start());stack.peek().mark(SOLUTION_MARK);while (!stack.peek().hasMark(Cell.END)) { Cell current = stack.peek(); ArrayListC

我试图弄清楚这个算法是否是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;
    }
}

解决方法

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

递归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(n2),因为即使您只探索每个节点一次,您也必须访问矩阵的每一行和每列以了解节点X和节点Y之间是否存在路径.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!