python - 在 Python 中运行无限循环的广度优先搜索算法

Question

我正在尝试使用 python 中的广度优先搜索算法创建一个迷宫。但是，我的程序正在进入一个无限循环。它应该检查每个空格，上、下、左和右。然后，该空间被放入访问列表中。在算法检查每个空间并将它们放入访问列表后，它应该回溯以找到到起点的最短路径。当它回溯时，它应该把 1 放在最短的路线上。

import queue
import re

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 finished_maze(maze, solution=''):
    global starting_point
    starting_point = 0
    for position in range(len(maze[0])):
        if position == 'S':
            starting_point = maze[i]
            break

    j = starting_point
    k = 0
    position = set()

    for move in solution:
        if move == 'Up':
            k -= 1
            print(move)
        elif move == 'Down':
            k += 1
            print(move)
        elif move == 'Left':
            j -= 1
            print(move)
        elif move == 'Right':
            j += 1
            print(move)

    for row in range(len(maze)):
        for column in range(len(maze[0])):
            if (maze[row], maze[column]) in position:
                print('1 ', end='')
            else:
                print(column + '', end='')
        print()


def is_valid(maze, moves):
    global starting_point
    a = True
    for position in range(len(maze[0])):
        if position == 'S':
            starting_point = maze[position]

    j = starting_point
    k = 0

    for move in re.findall('[A-Z][a-z]*', moves):
        if move == 'Up':
            k -= 1
        elif move == 'Down':
            k += 1
        elif move == 'Left':
            j -= 1
        elif move == 'Right':
            j += 1

        if not ((j >= 0 and j < len(maze[0])) and (k >= 0 and k < len(maze[0]))):
            return not a
        elif maze[k][j] == '0':
            return not a
    return a


def find_solution(maze, moves):
    global starting_point
    starting_point = 0
    global visited
    visited = []
    global move
    move = 0
    a = True

    for position in range(len(maze[0])):
        if position == 'S':
            starting_point = maze[position]

    j = starting_point
    k = 0
    if moves in visited:
        return not a
    for move in re.findall('[A-Z][a-z]*', 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(moves)
            print(finished_maze(maze, moves))
            return a
    visited.append(move)
    return not a


space = queue.Queue()
space.put('')
put = ''
maze = maze_3()


while not find_solution(maze, put):
    put = space.get()
    for i in ['Up', 'Down', 'Left', 'Right']:
        piece = put + i
        if is_valid(maze, piece):
            space.put(piece)

标签： pythonbreadth-first-search