我试图弄清楚这个算法是否是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)的最差值,当图形使每个节点只有一个邻居时,就会发生这种情况,变得像一个单链表.
