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

Question

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

    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 是空白空间，1 是墙，2 是目标，3 是已访问空间。扩展任务是在给定起点的情况下给出迷宫的最短可能解。如果起点是一堵墙，那么迷宫是没法解的。这也很好。它应该能够适用于任何给定的迷宫。

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

目前这是我的代码:

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

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

1. 更改已解决的函数以返回路径而不是 true 或 false。
2. 在每个节点而不是将 3 用于访问，您可以将从该节点到解决方案(或原点)的最小长度设置为 -1，将墙和无法到达解决方案的节点设置为 -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。

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

---

深思

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

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