迷宫算法的问题

Question

我在设计用于解决迷宫问题的算法时遇到问题。

我使用了这里的算法。http://www.cs.bu.edu/ education/alg/maze/

FIND-PATH(x, y)

1. if (x,y 在迷宫外) return false
2. if (x,y 是目标) return true
3. if (x,y not open) return false
4. 标记 x ,y 作为解决方案路径的一部分
5. if (FIND-PATH(x,y 的北边) == true) 返回 true
6. if (FIND-PATH(x,y 的东边) == true) 返回 true
7. if (FIND-PATH(South of x,y) == true) return true
8. if (FIND-PATH(West of x,y) == true) return true
9. 取消标记 x,y 作为解决方案路径的一部分
10. 返回错误

这是一个递归解决方案，我对其进行了修改，使其即使在找到退出后仍会继续，以便它也可以找到其他解决方案。 它似乎有效，只是它似乎找到了我所知道的可能解决方案总数的一半。

2. if (x,y is goal) return true 更改为 return false。

有人知道这种算法可能存在什么问题，导致可能的解决方案总数只有一半吗？ 我也遇到了查找死胡同路径总数的问题，对此有什么建议吗？

Answer 1

这是一个示例迷宫

####################
#S #  #       #    #
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #   #  #   ###
# ### ### ## # #####
#  #      #       E#
####################

Answer 2

对于死胡同的数量，您需要这样的东西：

3.5 if (x,y 的北边不开放) 和 (x,y 的南边不开放) 和 (x,y 的西边不开放) 和 (x 的东边， y 未打开）死胡同++

Answer 3

我尝试用java简单地实现该算法。 我的结论是，您描述的算法有效，即使对于查找多条路径也是如此。 或者，您可能想出了一个比我更聪明的测试用例。 （请发布你的迷宫，以便我可以尝试我的算法）

我的死胡同计数器的实现可能不是最有效的，但它完成了工作。 对于每个当前访问的 OPEN 节点，它会检​​查 4 个周围节点：

• 如果至少有一个邻居是 OPEN，则当前节点不是死胡同
• 如果访问了多个邻居，则当前节点不是死胡同
• 如果只有一个节点是已访问（我们在上一步中来自的那个）并且没有其他邻居打开，当前节点是死胡同

这是我编写的 java 代码（注意！相当长）。 如果您愿意，另一种方法是将路径存储在堆栈上，每次将节点设置为“VISITED”时压入一个节点，每次将其设置回“OPEN”时弹出一个节点。 每次达到目标时，应复制并保存保存当前路径的堆栈。

如果删除标记为“死胡同调查步骤”的 if 块，则此实现几乎与问题中描述的完全相同。

package test;

import java.util.HashSet;
import java.util.Set;

public class MazeSolver {

final static int OPEN = 0;
final static int WALL = 1;
final static int GOAL = 2;
final static int VISITED = 3;

static int[][] field = { { 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 2 }, { 1, 0, 1, 0, 0, 0 } };

// This is what the field looks like:
//  
// 0 1 1 0 1
// 0 0 0 0 0
// 0 1 1 0 1
// 0 1 0 0 0
// 0 0 0 1 0
// 1 1 0 2 0

static int width = field.length;
static int height = field[0].length;
static int xStart = 0;
static int yStart = 0; // Initiated to start position: (x = 0, y = 0)
static int nrSolutions = 0; // Records number of solutions

// Used for storing id:s of dead end nodes.
// The integer id is (x + y * width)
static Set<Integer> deadEnds = new HashSet<Integer>();

public static void main(String[] arg) {
    System.out.println("Initial maze:");
    printField();

    findPath(xStart, yStart);

    System.out.println("Number of solutions: " + nrSolutions);
    System.out.println("Number of dead ends: " + deadEnds.size());
}

private static void findPath(int x, int y) {

    if (x < 0 || y < 0 || x >= width || y >= height) { // Step 1
        return;
    } else if (field[x][y] == GOAL) { // Step 2
        nrSolutions++;
        System.out.println("Solution nr " + nrSolutions + ":");
        printField();
        return;
    } else if (field[x][y] != OPEN) { // Step 3
        return;
    } else if (isDeadEnd(x, y)) { // Extra dead-end-investigation-step
        int uniqueNodeId = x + y * width;
        deadEnds.add(uniqueNodeId); // Report as dead end
        return;
    }

    field[x][y] = VISITED; // Step 4

    findPath(x, y - 1); // Step 5, go north
    findPath(x + 1, y); // Step 6, go east
    findPath(x, y + 1); // Step 7, go south
    findPath(x - 1, y); // Step 8, go west

    field[x][y] = OPEN; // Step 9

    // Step 10 is not really needed, since the boolean is intended to
    // display only whether or not a solution was found. This implementation
    // uses an int to record the number of solutions instead.
    // The boolean return value would be (nrSolutions != 0)
}

private static boolean isDeadEnd(int x, int y) {
    int nrVisitedNeighbours = 0;

    if (y > 0) { // If northern neighbour exists
        if (field[x][y - 1] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x][y - 1] != WALL) {
            return false;
        }
    }
    if (x < width - 1) { // If eastern neighbour exists
        if (field[x + 1][y] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x + 1][y] != WALL) {
            return false;
        }
    }
    if (y < height - 1) { // If southern neighbour exists
        if (field[x][y + 1] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x][y + 1] != WALL) {
            return false;
        }
    }
    if (x > 0) { // If western neighbour exists
        if (field[x - 1][y] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x - 1][y] != WALL) {
            return false;
        }
    }

    if (nrVisitedNeighbours > 1) { // Circular path scenario
        return false;
    }

    return true; // The exhaustive result of this check: this is a dead
    // end
}

private static void printField() {
    for (int yy = 0; yy < field[0].length; yy++) {
        for (int xx = 0; xx < field.length; xx++) {

            System.out.print(field[xx][yy] + " ");
        }
        System.out.println();
    }
    System.out.println();
}
}

上面的算法报告了示例迷宫的四个不同的解决方案路径和两个死胡同，该迷宫被硬编码到代码中。

---

<编辑>
您获得的解决方案路径太少的原因可能是对解决方案路径的误解吗？ 例如，考虑这个迷宫：

######
##   #
## # #
#S   #
##E###
######

这个迷宫只有一条有效的解决方案路径。 这是因为您只能访问每个节点一次，因此绕圆形路径不是有效的解决方案路径，因为这将访问 S 以东和 E 以北的节点两次。 您使用的算法隐含了解决方案路径的定义。

如果允许多次访问同一个节点，就会有无限多个解决方案，因为您可以绕圈 1、2、3 ... 无限多次。

正如您所说，每次将节点设置为“VISITED”时，我都会增加路径长度，并在每次设置时减少路径长度将已访问的节点恢复为打开状态。

为了记录最短路径长度，我还有一个 ShortestPath int 值，我将其初始化为 Integer.MAX_VALUE。 然后，每次达到目标时，我都会这样做：

if(pathLength < shortestPath){
    shortestPath = pathLength;
}

至于死胡同……我尝试用手数它们，我认为 9 似乎是正确的。 这是 Sareen 发布的迷宫，但标记了死胡同（由手）与 D：

####################
#S # D#      D#D  D#
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #D  #D #   ###
# ### ### ## # #####
# D#D     #D      E#
####################

你还能找到更多吗？
还是我误解了你所说的死胡同的意思？
我认为死胡同意味着：一个只能从一个方向到达的节点。

示例 1：

######
## ###
## ### 
## ### 
#S  E#
######

上面的迷宫有一个死胡同。

例2：

######
##  ##
##  ## 
##  ## 
#S  E#
######

上面的迷宫没有死胡同。 即使您位于最北边的可访问节点之一，仍然有两个相邻的非 WALL 方块。

您对死胡同还有其他定义吗？

Answer 4

您不需要尝试找到一种穿过迷宫的方法，而是需要找到（并因此绘制）多种穿过迷宫的方法。

为此，您需要标记您去过的位置（在特定路径上）。 如果您到达已经去过的地点，则需要将该路线标记为死胡同。

递归函数仍然是可行的方法，但请确保通过递归函数传递 (placesIhaveBeen) 结构。

当到达 N、S、E、W 都被阻塞的点时，递归循环需要中断。 （你以前来过那里，你不能朝那个方向走，它在迷宫外面）
当您达到目标时，递归循环也需要中断。

如果达到目标 - 将全局变量增加一。
如果你无处可去——将你的死胡同增加一个。

我无法为此编写 pcode（这会花费太长时间），但我相信秘密就在一个函数中，如果 N、S、E 和 W 都被阻止，该函数将返回 true。

补充我最初的答案

关于为什么我将我去过的区域视为“封锁”，以及为什么我将它们视为死胡同......

      ########
      #      #  
      # #### #
####### #  # #
        #  # #
####### #  # #
      # #### #
      #      #  
      ########

我将上述迷宫部分分类为死胡同，如果不将我去过的地方视为封锁区域，我不知道如何识别它。

我意识到这会导致以下内容也出现死胡同，但我看不到解决方法。

      #######
      #     #  
      # ### #
####### #G# #
        # # #
####### #   #
      # ### #
      #     #  
      #######

Answer 5

似乎缺少的是检查 X&Y 是否已被标记为解决方案的一部分，如果是，我们将中止。 （这应该是第 3.5 点上的某个地方）

如果不是一个可能存在循环的迷宫，那么某个地方会无限期地运行并炸毁堆栈

，从我读到的内容来看，该算法基于只有 1 个解决方案

R的迷宫