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

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

来源

2016-04-30 Abdelrahman Wahdan

您的代码不完整;请参阅http://stackoverflow.com/help/mcve。另外，添加相关的语言标签（我知道它是Java，但我不应该猜测）。 – Jubobs

你能提供标记的定义吗？这看起来像是一个简单的深度优先搜索，但具有全局访问标记。 –

@LucasMoeskops：不，它标志着已经去过的地方。所以它最多可以运行在O（n^2）的n个单元格中。 –

基于告诉你什么，我会说这是深度优先搜索，但检查是否这个地方已经被安排参观。由于它使用堆栈，因此它总是首先访问搜索树中更深的地方。但是从现在起它增加了一个位置到堆栈，它将该位置标记为解决方案标记，以防止它被重新评估如果其他路径将到达相同的位置。

但请注意，它将标记每个瓦片SOLUTION_MARK，除非它不能提供其他标记为SOLUTION_MARK或ERROR_MARK的节点。因此，它会标记更多的贴图，而不是贴砖（最短）解决方案的贴图。从这个意义上说，它不是一个真正的迷宫求解算法：它只是将瓷砖标记为SOLUTION_MARK，如果至少还有另一个瓷砖尚未排定，那么可以为贡献一个解决方案。如果已标记所有瓦片，算法将完成。

来源

2016-04-30 16:46:28

所以复杂度是'O（n^2）'，其中'n'是被访问单元的总数，无论标记为错误还是解决方案，对吧？ –

@AbdelrahmanWahdan：如果每个邻居都可以有* n *个单元格。假设你只能在'4'方向移动，时间复杂度为O（n）。 –

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

递归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

未访问和NotVisiting在迭代版本意味着节点既不访问之前，也不在访问堆栈中。

该算法的时间复杂依赖于图是否已经被存储为邻接列表或邻接矩阵。对于列表，它将是O（n）。对于矩阵，它将变成O（因为即使你只探索每个节点一次，你也必须访问矩阵的每一行和每列，以知道节点X和节点Y之间是否存在路径。

该算法可以去花费时间O（n）的的空间复杂，当发生图将有只有一个邻居的每个节点，变得像一个单向链表。

来源

2016-04-30 17:05:05 displayName

我认为值得一提的是它进行了一次事件检查：检查节点是否已经添加到堆栈中。 –

@WillemVanOnsem：更新。 – displayName

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

回答

相关问题