Python 使用回溯法逃离二元迷宫时的最短距离

Question

需要帮助寻找二元迷宫中的最短距离，二元迷宫是列表矩阵的列表，其中 0 是空单元格，1 是墙。迷宫的 x,y 起始坐标默认为 0,0，终点始终位于右下角。最短距离始终包括起点（即，如果从起点需要四步，则最短距离将为 5）

我需要使用回溯算法。到目前为止，我可以想出一个函数来确定是否存在转义路径。效果很好：

def is_solution(maze, x=0, y=0):

    n = len(maze)
    m = len(maze[0])

    if x == n - 1 and y == m - 1:
        return True
    
    maze[x][y] = 1
    result = False

    for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
        if 0 <= a < n and 0 <= b < m and maze[a][b] == 0:
            result = result or is_solution(maze, a, b)
            
    maze[x][y] = 0
    return result


maze = [
      [0, 0, 1, 1],
      [1, 0, 0, 0],
      [1, 1, 1, 0]
    ]

is_solution(maze)

以上结果为真。

现在我真的很难找到最短的距离。我认为更新上面的代码应该相对容易，因此如果有路径则显示距离，如果没有路径则显示 inf。但是我卡住了。在上面的示例中，最短距离为 6（包括起点）我还需要添加代码，以便能够以 [[(0, 0), (0, 1), (1, 1), ( 1, 2), (1, 3), (2, 3)]] 。在这种情况下，只有一条路径，但如果有两条距离为 6，则该列表也将包括第二短路径的列表。

谢谢。

Answer 1

对代码进行简单更改以跟踪最短路径

最短路径

def min_solution(maze, x = 0, y = 0, path = None):
    def try_next(x, y):
        ' Next position we can try '
        return [(a, b) for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)] if 0 <= a < n and 0 <= b < m]

    n = len(maze)
    m = len(maze[0])
    
    if path is None:
        path = [(x, y)]         # Init path to current position

    # Reached destionation
    if x == n - 1 and y == m - 1:
        return path
    
    maze[x][y] = 1              # Mark current position so we won't use this cell in recursion
    
    # Recursively find shortest path
    shortest_path = None            
    for a, b in try_next(x, y):
        if not maze[a][b]:
            last_path = min_solution(maze, a, b, path + [(a, b)])  # Solution going to a, b next
            
            if not shortest_path:
                shortest_path = last_path        # Use since haven't found a path yet
            elif last_path and len(last_path) < len(shortest_path):
                shortest_path = last_path       # Use since path is shorter
     
    
    maze[x][y] = 0           # Unmark so we can use this cell
    
    return shortest_path


maze = [
      [0, 0, 1, 1],
      [1, 0, 0, 0],
      [1, 1, 1, 0]
    ]

t = min_solution(maze)
if t:
    print(f'Shortest path {t} has length {len(t)}')
else:
    print('Path not found')

输出：

Shortest path [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3)] has length 6

所有路径

def all_paths(maze, x = 0, y = 0, path = None):
    '''
        All paths through Maze as a generator
    '''
    def try_next(x, y):
        ' Next position we can try '
        return [(a, b) for a, b in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)] if 0 <= a < n and 0 <= b < m]

    n = len(maze)
    m = len(maze[0])
    
    if path is None:
        path = [(x, y)]

    # Reached destionation
    if x == n - 1 and y == m - 1:
        yield path
    else:
        maze[x][y] = 1              # Mark current position so we won't use this cell in recursion

        # Recursively find  pat          
        for a, b in try_next(x, y):
            if not maze[a][b]:
                yield from all_paths(maze, a, b, path + [(a, b)])  # Solution going to a, b next

        maze[x][y] = 0           # Unmark so we can use this cell
    

maze =  [[0, 0, 0], 
         [1, 0, 0], 
         [1, 1, 0]]

for t in all_paths(maze):
    print(f'path {t} has length {len(t)}')

输出

path [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)] has length 5
path [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)] has length 5

Python 使用回溯法逃离二元迷宫时的最短距离

Python shortest distance while escaping a binary maze using backtracking

python

algorithm

maze