迷宫解决BFS算法不起作用，多次检查相同的数字

Question

我正在尝试创建一个迷宫求解算法。我在网上看了一些教程，遇到了BFS算法。我尝试自己实现它。这是我写的：

import queue, numpy, time
from PIL import Image
def maze(mazename, start=True, end=True):
q = queue.Queue()
img = Image.open(mazename)
array = numpy.array(img).tolist()
for x, y in enumerate(array):
for i, h in enumerate(y):
if h == 0:
array[x][i] = (0, 0, 0)
else:
array[x][i] = (255, 255, 255)
if start and end:
for x, y in enumerate(array[0]):
if y == (255, 255, 255):
start = [x+1, 1]
for x, y in enumerate(array[-1]):
if y == (255, 255, 255):
end = [x+1, len(array)]
start[0] = start[0]-1
start[1] = start[1]-1
end[0] = end[0]-1
end[1] = end[1]-1
start = tuple(start)
q.put("")
while True:
#Checking for end
parse = q.get()
m = list(start)
for i in parse:
if i == "D":
m[1] = m[1]+1
if i == "U":
m[1] = m[1]-1
if i == "L":
m[0] = m[0]-1
if i == "R":
m[0] = m[0]+1
print(m, end)
if m == end:
m = list(start)
array[m[1]][m[0]] = (255, 0, 0)
for i in parse:
if i == "D":
m[1] = m[1]+1
array[m[1]][m[0]] = (255, 0, 0)
if i == "U":
m[1] = m[1]-1
array[m[1]][m[0]] = (255, 0, 0)
if i == "L":
m[0] = m[0]-1
array[m[1]][m[0]] = (255, 0, 0)
if i == "R":
m[0] = m[0]+1
array[m[1]][m[0]] = (255, 0, 0)
return array
#Find new trails
directions = ["U", "D", "L", "R"]
if m[0] == 0:
directions.remove("L")
elif array[m[1]][m[0]-1] == (0, 0, 0):
directions.remove("L")
if m[0]+1 == len(array[0]):
directions.remove("R")
elif array[m[1]][m[0]+1] == (0, 0, 0):
directions.remove("R")
if m[1] == 0:
directions.remove('U')
elif array[m[1]-1][m[0]] == (0, 0, 0):
directions.remove('U')
if m[1]+1 == len(array):
directions.remove("D")
elif array[m[1]+1][m[0]] == (0, 0, 0):
directions.remove("D")
for direction in directions:
q.put(parse+direction)
t1 = time.time()
arr = maze(input("Enter maze file name: "))
print(time.time()-t1)
Image.fromarray(numpy.array(arr).astype(numpy.uint8)).show()

我在这张图片上试过了：https://raw.githubusercontent.com/mikepound/mazesolving/master/examples/tiny.png 它工作得很好。花了 3 到 7 秒。

然后我在这个图像上尝试了一下： https://raw.githubusercontent.com/mikepound/mazesolving/master/examples/normal.png

它已经运行了 15 分钟，但仍然没有通过 40x40 图像的 10 行一次。它检查了数百次相同的数字，我不知道为什么。有人可以指出我的算法中的缺陷并帮助我修复它吗？我尝试实现访问列表，它只会减慢程序的速度。谢谢

Answer 1

您缺少visited的列表。您应该跟踪到目前为止您去过的位置，以免重复相同的位置。

当您有一个访问过的列表时，您可以使用它来检查您是否已经在该像素上，然后再进行移动。

def maze(mazename, start=True, end=True):
q = queue.Queue()
visited = []
img = Image.open(mazename)
array = numpy.array(img).tolist()
for x, y in enumerate(array):
for i, h in enumerate(y):
if h == 0:
array[x][i] = (0, 0, 0)
else:
array[x][i] = (255, 255, 255)
if start and end:
for x, y in enumerate(array[0]):
if y == (255, 255, 255):
start = [x+1, 1]
for x, y in enumerate(array[-1]):
if y == (255, 255, 255):
end = [x+1, len(array)]
start[0] = start[0]-1
start[1] = start[1]-1
end[0] = end[0]-1
end[1] = end[1]-1
start = tuple(start)
q.put("")
while True:
#Checking for end
parse = q.get()
m = list(start)
for i in parse:
if i == "D":
m[1] = m[1]+1
if i == "U":
m[1] = m[1]-1
if i == "L":
m[0] = m[0]-1
if i == "R":
m[0] = m[0]+1
if m not in visited:
visited.append(m)
print(m, end)
if m == end:
m = list(start)
array[m[1]][m[0]] = (255, 0, 0)
for i in parse:
if i == "D":
m[1] = m[1]+1
array[m[1]][m[0]] = (255, 0, 0)
if i == "U":
m[1] = m[1]-1
array[m[1]][m[0]] = (255, 0, 0)
if i == "L":
m[0] = m[0]-1
array[m[1]][m[0]] = (255, 0, 0)
if i == "R":
m[0] = m[0]+1
array[m[1]][m[0]] = (255, 0, 0)
return array
#Find new trails
directions = ["U", "D", "L", "R"]
if m[0] == 0:
directions.remove("L")
elif array[m[1]][m[0]-1] == (0, 0, 0):
directions.remove("L")
if m[0]+1 == len(array[0]):
directions.remove("R")
elif array[m[1]][m[0]+1] == (0, 0, 0):
directions.remove("R")
if m[1] == 0:
directions.remove('U')
elif array[m[1]-1][m[0]] == (0, 0, 0):
directions.remove('U')
if m[1]+1 == len(array):
directions.remove("D")
elif array[m[1]+1][m[0]] == (0, 0, 0):
directions.remove("D")
for direction in directions:
q.put(parse+direction)