找到迷宫的最短或最长解决方案

Question

我正在处理一项任务，我已经解决了主要问题并正在研究扩展练习。目前给出了一张地图，迷宫的所有可能解决方案都在打印如下的网格上标识：

    1 1 3 1 0 2 
    3 3 3 3 1 3 
    3 3 1 3 3 3 
    3 3 3 1 3 0 
    3 1 3 1 3 1 
    3 1 3 3 3 0

其中 0 是空的 spaces，1 是墙，2 是目标，3 是已访问的 space。扩展任务是在给定起点的情况下给出迷宫的最短可能解。如果起点是一堵墙，那么迷宫是没法解的。这也很好。它应该能够适用于任何给定的迷宫。

我真的不知道从哪里开始解决这个问题。一个想法是对所有路径求和并找到其中最小的路径，但我不确定如何实现它。

目前这是我的代码：

EMPTY = 0
WALL = 1
GOAL = 2
VISITED = 3


def solve(grid, x, y):
    if grid[x][y] == GOAL:
        show_grid(grid)
        return True
    elif grid[x][y] == WALL:
        return False
    elif grid[x][y] == VISITED:
        return False
    else:
       # mark as visited
       grid[x][y] = VISITED

       # explore neighbors clockwise starting by going up
       if      ((x < len(grid)-1  and solve(grid, x + 1, y))
             or (y > 0            and solve(grid, x, y-1))
             or (x > 0            and solve(grid, x-1, y))
             or (y < len(grid)-1  and solve(grid, x, y+1))):
           return True
       else:
           return False


def show_grid (grid):
    for i in range(len(grid), 0, -1):
        # print("i: ", i)
        for element in grid[i-1]:
            print (element, end=" ")
        print()


def main ():
    grid =    [[EMPTY, WALL, EMPTY, EMPTY, EMPTY, EMPTY],
               [EMPTY, WALL, EMPTY, WALL, EMPTY, WALL],
               [EMPTY, EMPTY, EMPTY, WALL, EMPTY, EMPTY],
               [EMPTY, EMPTY, WALL, EMPTY, EMPTY, EMPTY],
               [EMPTY, EMPTY, EMPTY, EMPTY, WALL, EMPTY],
               [WALL, WALL, EMPTY, WALL, EMPTY, GOAL]]

    solve(grid, 0, 0)

扩展要求打印最短路径的长度，其中遍历1个方格为1次移动。感谢任何对此问题的帮助。

Answer 1

您正在使用递归探索网格，其中基本情况是找到 GOAL。 solve 的每个实例仅 return 是一个布尔值，因此您丢失了信息 - 实例所采用的路径。

重构，以便函数 return 在可行的情况下提供网格位置，并且累积来自实例的后代的 return 值。

您的条件需要重新考虑，并且您要确保探索所有路径（上、下、左、右）。在条件 bool((0,0)) -> True.

中使用 a tuple is evaluated True 这一事实可能会有所帮助

最后你可以：

累积所有成功的路径然后在过程完成时确定最小和最大长度或
评估成功的路径长度正在处理并使用占位符(?)变量保持当前的最大值和最小值 - 此选项丢弃路径信息，但如果您不需要，那没关系。

我试图根据您当前的代码来制定它，因为我假设您了解您当前的流程是如何工作的，并且从那里开始可能更容易。

您还可以将网格视为图形，每个点都是一个节点，其周围的节点有边。您可以先将网格解析为图表，然后使用任意数量的定义明确的算法遍历图表并找到您的答案。对于树解决方案，根将是搜索的起点。我没有太多使用使用图表的经验，所以我觉得我无法对此给出详细的答案 - 也许有人会用更好的解释.

Answer 2

我同意@wwii 的回答，如果你正在探索所有的解决方案，只需 return 每条成功路径的长度，然后找到最短的路径。这可以通过以下更改来实现：

将您求解的函数更改为 return 路径，而不是 true 或 false。
在每个节点上而不是将 3 用于访问，您可以将从该节点到解决方案（或原点）的最小长度设置为 -1 用于墙和无法到达解决方案的节点。无法到达解决方案的节点本质上是墙。

例如，

GOAL = 'G'
WALL = 'W'
EMPTY = 'E'


def solve(grid, x, y):
    if grid[x][y] == WALL or grid[x][y].endswith(GOAL):
        return grid[x][y]

    candidates = []
    # explore neighbors clockwise starting by going down
    if x < len(grid)-1:
        candidates.append('d' + solve(grid, x + 1, y))
    if y > 0:
        candidates.append('l' + solve(grid, x, y - 1))
    if x > 0:
        candidates.append('u' + solve(grid, x - 1, y))
    if y < len(grid)-1:
        candidates.append('r' + solve(grid, x, y + 1))

    # get rid of none solutions from candidates
    candidates = [x for x in candidates if not x.endswith(GOAL)]
    if not candidates: # if no solution, it's essentially a wall
        grid[x][y] = 'W'
    else: 
        # getting shortest path
        grid[x][y] = sorted(candidates, key=lambda x: len(x))[0]

        # for longest path use code below instead of above
        # grid[x][y] = sorted(candidates, key=lambda x: len(x))[-1]
    return grid[x][y]

如果访问了一个节点并到达了目标，则该节点的值可能类似于 'drrurG'。这意味着最短路径是向下，向右*2，向上，向右，目标。方向约定向下意味着向下一行，即 x+1。

当然，您可能需要更改代码的其他部分才能使其正常工作。

深思

上面的代码遍历了所有可能的路径。但你可能不需要。可能有更快的方法到达最短路径，因为这个问题不像其他一般寻路问题那么复杂。

例如，绝对最短路径显然是从起点到终点的直线。先检查一下。如果那不是解决方案，则开始检查下一个最短路径。看看这些是否有效。如果没有，请继续前进，直到找到为止。

找到迷宫的最短或最长解决方案

Finding the shortest or longest solution to a maze

python

algorithm

maze

graph-algorithm

深思