Python广度优先搜索迷宫求解器陷入无限循环问题求助

看起来你的BFS迷宫求解器陷入无限循环的核心原因是没有追踪已访问的位置，加上几个逻辑细节错误，导致队列被重复的路径填满，永远处理不完。咱们一步步拆解问题，然后给出修复后的代码：

主要问题分析 #

1. 未记录已访问位置（无限循环的根源） #

BFS的关键是避免重复访问同一个坐标，否则同一个位置会被反复加入队列，队列永远不会为空，while循环就会无限运行。你的代码里完全没有这个逻辑，所以会一直生成重复的移动路径。

2. 边界判断错误 #

在is_valid函数里，判断行索引k的范围时用了len(maze[0])，但行的总数应该是len(maze)，而且每行的长度可能不一样（你定义的maze里每行长度就不一致），所以列索引j应该用len(maze[k])来判断，而不是统一用len(maze[0])。

3. 路径坐标未存入position集合 #

finished_maze里的position集合是空的，你没有把路径上的每个坐标添加进去，所以最后替换路径为1的逻辑根本不会生效。

4. 全局变量与函数逻辑混乱 #

你用了global starting_point，但其实完全没必要，应该在每个需要起点的函数内部查找并保存起点坐标，避免全局变量带来的意外问题。另外find_solution的返回值逻辑很混乱，找到终点时应该明确返回True，否则返回False。

5. 队列循环逻辑顺序问题 #

原代码的while循环里，先判断find_solution(maze, put)，然后才从队列get新的路径，这会导致初始的空路径被重复判断，而且队列处理的顺序有问题。

修复后的完整代码 #

import queue

def maze_3():
    maze3 = [
        '00000S000000000000000000000000000000000000000000000000000000000',
        '00000 000000000 ',
        '00000 000000000 000000000000000000 000000000000000 00000000',
        '000000 00000000 000000 00000',
        ' 00000000 000000000000 000000000000000000 000000',
        '00000000 000000000000000000000000000000 0000 000000',
        '000000 000 000000000 000 000000 0000',
        '000000 000 000000000 00000000 000000 00',
        '00 000 0 0000000000 000 000 0000 00 00 00000 000',
        '000000 000000 000000000 000 0000 00000',
        '0000000000000000 0000000 0000000 000 00000000000',
        '000000 000 0000000 0000 00000000000000 00000000',
        '0000000000000000E 0000000',
    ]
    return maze3

def find_start(maze):
    # 单独提取找起点的逻辑，避免重复代码
    for k, row in enumerate(maze):
        for j, col in enumerate(row):
            if col == 'S':
                return (k, j)
    return None  # 没找到起点的情况

def finished_maze(maze, moves):
    start_k, start_j = find_start(maze)
    k, j = start_k, start_j
    position = set()
    position.add((k, j))  # 加入起点
    for move in moves:
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1
        position.add((k, j))  # 把路径上的每个坐标加入集合
    # 打印迷宫，替换路径为1
    for row_idx, row in enumerate(maze):
        for col_idx, col in enumerate(row):
            if (row_idx, col_idx) in position:
                print('1', end='')
            else:
                print(col, end='')
        print()

def is_valid(maze, moves, visited):
    start_k, start_j = find_start(maze)
    k, j = start_k, start_j
    for move in moves:
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1
    # 检查边界：行不能超出0到len(maze)-1，列不能超出0到当前行长度-1
    if k < 0 or k >= len(maze):
        return False
    if j < 0 or j >= len(maze[k]):
        return False
    # 检查是否是墙（0）或者已经访问过
    if maze[k][j] == '0' or (k, j) in visited:
        return False
    return True

def find_solution(maze, moves):
    start_k, start_j = find_start(maze)
    k, j = start_k, start_j
    for move in moves:
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1
    # 检查是否到达终点
    if maze[k][j] == 'E':
        print("找到最短路径：")
        finished_maze(maze, moves)
        return True
    return False

def main():
    maze = maze_3()
    space = queue.Queue()
    space.put('')
    visited = set()  # 记录已访问的坐标
    start_k, start_j = find_start(maze)
    visited.add((start_k, start_j))  # 起点标记为已访问

    while True:
        current_moves = space.get()
        # 先检查当前路径是否到达终点
        if find_solution(maze, current_moves):
            break
        # 生成四个方向的新路径
        for direction in ['Up', 'Down', 'Left', 'Right']:
            new_moves = current_moves + direction
            if is_valid(maze, new_moves, visited):
                # 获取新路径对应的坐标，加入已访问集合
                k, j = start_k, start_j
                for move in new_moves:
                    if move == 'Up':
                        k -= 1
                    elif move == 'Down':
                        k += 1
                    elif move == 'Left':
                        j -= 1
                    elif move == 'Right':
                        j += 1
                visited.add((k, j))
                space.put(new_moves)

if __name__ == "__main__":
    main()

关键修改说明 #

• 新增find_start函数：统一处理起点查找，避免重复代码，去掉全局变量。
• 加入visited集合：追踪所有已访问的坐标，确保每个位置只被处理一次，彻底解决无限循环问题。
• 修复边界判断：行用len(maze)判断，列用当前行的len(maze[k])判断，适配每行长度不一致的情况。
• 完善finished_maze的position集合：把路径上的每个坐标都加入集合，确保路径能被替换为1。
• 调整循环逻辑：在main函数里先获取当前路径，检查是否到达终点，再生成新路径，逻辑更清晰。
• 修正find_solution的返回逻辑：明确找到终点返回True，终止循环。

这样修改后，你的BFS求解器就能正常找到最短路径，不会再陷入无限循环了。

内容的提问来源于stack exchange，提问作者James