递归迷宫算法（在迷宫中旋转件）

我的程序的目的是用递归递归地解决迷宫问题。然而，我的迷宫是N * N格，使得每个正方形具有方向性属性：递归迷宫算法（在迷宫中旋转件）

NS，EW，NE，NW，SE，SW和X（阻塞正方形）

每个小部分可以是顺时针旋转90 *。

如果我写的传统迷宫递归解决方案，我会：

if (x,y outside maze) return false 
if (x,y is goal) return true 
if (x,y not open) return false 
mark x,y as part of solution path 
if (FIND-PATH(North of x,y) == true) return true 
if (FIND-PATH(East of x,y) == true) return true 
if (FIND-PATH(South of x,y) == true) return true 
if (FIND-PATH(West of x,y) == true) return true 
unmark x,y as part of solution path 
return false

不幸的是，我与旋转件挣扎。我的程序结构是一个二维数组，用正方形对象填充，方形对象用旋转的函数保存其当前方向值。任何建议将不胜感激。

来源

2017-03-09 Infiniti

请给出一个这样的网格的例子，以及程序应该产生的解决方案。 – trincot

为什么有6个方向，而不是4或8？他们的意思是什么？ –

你的问题很混乱。不可能告诉你单元格的方向和旋转它们的规则是什么意思。

话虽如此，所有的递归回溯算法，需要一个相当类似的形式：

solveFrom(current: State) 
    if current is complete 
     add current to solution set 
    else 
     for each possible step from state 
      solveFrom(state with step added)

的state with step added通常包括添加步骤，调用函数递归然后再删除它。

如果你只想要第一个解决方案（而不是所有潜在的解决方案），那么该函数可以像你一样返回一个布尔值。

在你的情况，我怀疑你的问题是可能的步骤包括移动到一个新的单元格和旋转单元格。目前你只是在尝试涉及移动的步骤。您需要尝试这些步骤的所有可能组合才能使算法起作用。

来源

2017-03-09 22:48:33 sprinter

递归算法是深度优先，效率低下并产生任意的解决方案（在您的案例中使用最大数量的北方运动的路径）。

一个更合适的方法是宽度优先，这将很容易产生最短路径，并且没有多少无用的迭代。尽管（NS，EW）组只有两种不同的状态，但增加旋转单元格的可能性意味着每个单元格可能具有4种状态（旋转0,90,180和270°）。由于某些原因，可能的单元格不包含4路交叉，实际上这些交叉是通过旋转不变的，但是在更普遍的情况下可能发生。

因此，您需要记住（x，y，r）而不是（x，y），其中r是访问单元的旋转状态。

现在，当您选择下一个单元格时，您需要枚举其所有可能的方向（NE，ES，SW，WN组为4，NS，EW组为2），然后检查路径是否存在每一个，如果是这样，就像以前用（x，y）一样维护你的（x，y，r）路径信息。

至于广度优先算法，虽然它是有点偏离主题，它基本上是如下：

A“候选人的举动”是此举可能导致的解决方案。它包含一个单元格的位置和方向，加上前一个移动的引用（以便产生最终结果）。
你还需要一个状态变量来跟踪已经尝试过的动作。
它可以被看作是布尔值数组，即visited[x,y,r]，虽然你可以更有效地与关联存储器或哈希表实现，如果你不幸使用原始超高效的语言，如C++ ...
你确定候选移动列表，并试戴顺序如下所示：

E = entry cell 
candidates := singleton list containing (E.x, E.y, 0° rotation, no parent) 
while candidates is not empty 
    C := get first element of candidates 
    if (C.x, C.Y) is the exit 
     // reconstruct solution path 
     path := empty list 
     do forever 
      path.add (C) 
      if C.parent == no parent 
       return path 
      C := C.parent 
    if C has not already been visited 
     mark C already visited 
     for each neighbour N of C // the 4 cells around (C.x, C.y) 
      for each rotation R of N // 0 for X, 2 for NS,EW, 4 for NE,ES,SW,WN 
       if there is a path from C to R 
        add (N.x, N.y, R, C) to candidates 
return failure

该算法将检查并行地从入口点所产生的所有路径，直到它到达出口处，遇到一个已经访问过的细胞（在相同的旋转状态）或用完原始细胞来检查（在这种情况下，牛头怪赢了）。

要重建解决方案，请按照退出移动前辈直到第一次移动（没有父项）。

来源

2017-03-09 23:03:36

递归迷宫算法（在迷宫中旋转件）

回答

相关问题