分支限界法求迷宫问题

Question

走迷宫得出最短路径，迷宫自己设置一个n×m的矩阵，输入n,m和迷宫初态，输出最短路径，若无解就输出no way

Answer 1

引自免费微信小程序：皆我百晓生

在Python中，我们可以使用分支限界法结合广度优先搜索（BFS）来解决这个迷宫问题。首先，我们需要定义一个表示迷宫的二维数组，并为每个位置标记出墙壁、起点和终点。接下来，我们将实现一个算法来找到从起点到终点的最短路径。

这里是一个详细的步骤指南以及相应的Python代码示例：

1. 定义迷宫： 假设我们有一个5x5的迷宫，其中0表示空地，1表示墙壁，S表示起点，E表示终点。

2. 初始化数据结构：创建一个队列用于广度优先搜索，一个集合用于存储已访问过的节点，一个字典用于存储从起点到各节点的最短距离，初始时只有起点的距离为0，其他所有节点的距离为无穷大。

3. 主循环：当队列不为空且未找到终点时，执行以下操作： a. 从队列中取出一个节点。 b. 检查该节点是否是终点，如果是，则找到了一条路径，返回结果。 c. 否则，将该节点的所有相邻节点加入队列，但要确保它们不是墙壁并且尚未被访问过。 d. 更新相邻节点的最短距离，取当前节点的距离加1作为新距离。

4. 如果主循环结束仍未找到终点，说明没有通路，返回"No Way"。

下面是完整的Python代码实现：

def bfs_maze(maze, start, end):
    n, m = len(maze), len(maze[0])
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # 上、下、左、右四个方向

    queue = [(start[0], start[1])]
    visited = set()
    distances = {start: 0}
    for i in range(n):
        for j in range(m):
            if maze[i][j] == 1:
                distances[(i, j)] = float('inf')

    while queue:
        x, y = queue.pop(0)
        if (x, y) == end:
            return distances[end]
        
        visited.add((x, y))
        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < n and 0 <= new_y < m and maze[new_x][new_y] != 1 and (new_x, new_y) not in visited:
                new_distance = distances[(x, y)] + 1
                if new_distance < distances.get((new_x, new_y), float('inf')):
                    distances[(new_x, new_y)] = new_distance
                    queue.append((new_x, new_y))

    return "No Way"

# 示例迷宫
maze = [
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 1]
]

# 起点和终点
start = (0, 0)
end = (4, 4)

# 输出最短路径长度
print(bfs_maze(maze, start, end))

这段代码会根据给定的迷宫、起点和终点计算并返回最短路径的步数。如果没有路径，它会返回"No Way"。请注意，这个实现并没有绘制图形，因为这是一个文本环境，如果你需要可视化，可以考虑使用第三方库如matplotlib来展示迷宫和路径。