用bfs在迷宫中找到路径

Question

我有一个迷宫，由一个字典(路径)组成，迷宫的维度为(8,8)。在字典中声明是否可以上下左右移动

现在我想用BFS算法找到路径。在一些视频和文章的帮助下，我可以找到从起点到终点的方法。但我不知道怎么打印。这是我到目前为止的代码:

#--- Clear Terminal
import os
clear = lambda: os.system('cls')
clear()
import collections
paths = {   (0, 0): {'U': False, 'D': True, 'L': False, 'R': True}, 
(0, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
(0, 2): {'U': False, 'D': True, 'L': True, 'R': False}, 
(0, 3): {'U': False, 'D': False, 'L': False, 'R': True}, 
(0, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
(0, 5): {'U': False, 'D': False, 'L': True, 'R': True}, 
(0, 6): {'U': False, 'D': False, 'L': True, 'R': True}, 
(0, 7): {'U': False, 'D': True, 'L': True, 'R': False}, 
(1, 0): {'U': True, 'D': True, 'L': False, 'R': False}, 
(1, 1): {'U': False, 'D': False, 'L': False, 'R': False}, 
(1, 2): {'U': True, 'D': True, 'L': False, 'R': False}, 
(1, 3): {'U': False, 'D': True, 'L': False, 'R': True}, 
(1, 4): {'U': False, 'D': True, 'L': True, 'R': False}, 
(1, 5): {'U': False, 'D': False, 'L': False, 'R': True}, 
(1, 6): {'U': False, 'D': True, 'L': True, 'R': False}, 
(1, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
(2, 0): {'U': True, 'D': False, 'L': False, 'R': True}, 
(2, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
(2, 2): {'U': True, 'D': True, 'L': True, 'R': True}, 
(2, 3): {'U': True, 'D': False, 'L': True, 'R': False}, 
(2, 4): {'U': True, 'D': True, 'L': False, 'R': False}, 
(2, 5): {'U': False, 'D': True, 'L': False, 'R': True}, 
(2, 6): {'U': True, 'D': True, 'L': True, 'R': True}, 
(2, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
(3, 0): {'U': False, 'D': True, 'L': False, 'R': True}, 
(3, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
(3, 2): {'U': True, 'D': False, 'L': True, 'R': False}, 
(3, 3): {'U': False, 'D': True, 'L': False, 'R': True}, 
(3, 4): {'U': True, 'D': False, 'L': True, 'R': False}, 
(3, 5): {'U': True, 'D': True, 'L': False, 'R': False}, 
(3, 6): {'U': True, 'D': True, 'L': False, 'R': False}, 
(3, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
(4, 0): {'U': True, 'D': True, 'L': False, 'R': False}, 
(4, 1): {'U': False, 'D': True, 'L': False, 'R': True}, 
(4, 2): {'U': False, 'D': False, 'L': True, 'R': True}, 
(4, 3): {'U': True, 'D': False, 'L': True, 'R': False}, 
(4, 4): {'U': False, 'D': False, 'L': False, 'R': True},
(4, 5): {'U': True, 'D': True, 'L': True, 'R': False}, 
(4, 6): {'U': True, 'D': False, 'L': False, 'R': False}, 
(4, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
(5, 0): {'U': True, 'D': False, 'L': False, 'R': False}, 
(5, 1): {'U': True, 'D': True, 'L': False, 'R': False}, 
(5, 2): {'U': False, 'D': True, 'L': False, 'R': True}, 
(5, 3): {'U': False, 'D': True, 'L': True, 'R': False}, 
(5, 4): {'U': False, 'D': False, 'L': False, 'R': True}, 
(5, 5): {'U': True, 'D': True, 'L': True, 'R': True}, 
(5, 6): {'U': False, 'D': True, 'L': True, 'R': True}, 
(5, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
(6, 0): {'U': False, 'D': True, 'L': False, 'R': False}, 
(6, 1): {'U': True, 'D': False, 'L': False, 'R': True}, 
(6, 2): {'U': True, 'D': False, 'L': True, 'R': False}, 
(6, 3): {'U': True, 'D': True, 'L': False, 'R': True}, 
(6, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
(6, 5): {'U': True, 'D': False, 'L': True, 'R': False}, 
(6, 6): {'U': True, 'D': True, 'L': False, 'R': True}, 
(6, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
(7, 0): {'U': True, 'D': False, 'L': False, 'R': True}, 
(7, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
(7, 2): {'U': False, 'D': False, 'L': True, 'R': True}, 
(7, 3): {'U': True, 'D': False, 'L': True, 'R': True}, 
(7, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
(7, 5): {'U': False, 'D': False, 'L': True, 'R': True}, 
(7, 6): {'U': True, 'D': False, 'L': True, 'R': False}, 
(7, 7): {'U': True, 'D': False, 'L': False, 'R': False}}
start = (5, 5)
end = (2, 2)
queue = collections.deque()
queue.append(start)
seen = set([start])
while queue:
path = queue.popleft()
i, j = path
print(path)
if (i,j) == end:
print("We found the end")
break
#--- check up
if (paths.get((i, j)).get("U") == True) and ((i - 1, j) not in seen):
queue.append((i - 1, j))
seen.add((i - 1, j))
#--- check Down
if (paths.get((i, j)).get("D") == True) and ((i + 1, j) not in seen):
queue.append((i + 1, j))
seen.add((i + 1, j))
#--- check Left
if (paths.get((i, j)).get("L") == True) and ((i, j - 1) not in seen):
queue.append((i, j - 1))
seen.add((i, j - 1))
#--- check Left
if (paths.get((i, j)).get("R") == True) and ((i, j + 1) not in seen):
queue.append((i, j + 1))
seen.add((i, j + 1))

有谁知道如何跟踪正确的路径吗?

这就是我得到关于bfs的信息的地方:bfs

Answer 1

可以通过维护存储前一个元素的字典来找到路径。

import collections
def print_path(start,goal):
print("Path :")
current = goal
print(current)
while current != start:
current = parent[current]
print(current)
paths = {   (0, 0): {'U': False, 'D': True, 'L': False, 'R': True}, 
(0, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
(0, 2): {'U': False, 'D': True, 'L': True, 'R': False}, 
(0, 3): {'U': False, 'D': False, 'L': False, 'R': True}, 
(0, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
(0, 5): {'U': False, 'D': False, 'L': True, 'R': True}, 
(0, 6): {'U': False, 'D': False, 'L': True, 'R': True}, 
(0, 7): {'U': False, 'D': True, 'L': True, 'R': False}, 
(1, 0): {'U': True, 'D': True, 'L': False, 'R': False}, 
(1, 1): {'U': False, 'D': False, 'L': False, 'R': False}, 
(1, 2): {'U': True, 'D': True, 'L': False, 'R': False}, 
(1, 3): {'U': False, 'D': True, 'L': False, 'R': True}, 
(1, 4): {'U': False, 'D': True, 'L': True, 'R': False}, 
(1, 5): {'U': False, 'D': False, 'L': False, 'R': True}, 
(1, 6): {'U': False, 'D': True, 'L': True, 'R': False}, 
(1, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
(2, 0): {'U': True, 'D': False, 'L': False, 'R': True}, 
(2, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
(2, 2): {'U': True, 'D': True, 'L': True, 'R': True}, 
(2, 3): {'U': True, 'D': False, 'L': True, 'R': False}, 
(2, 4): {'U': True, 'D': True, 'L': False, 'R': False}, 
(2, 5): {'U': False, 'D': True, 'L': False, 'R': True}, 
(2, 6): {'U': True, 'D': True, 'L': True, 'R': True}, 
(2, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
(3, 0): {'U': False, 'D': True, 'L': False, 'R': True}, 
(3, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
(3, 2): {'U': True, 'D': False, 'L': True, 'R': False}, 
(3, 3): {'U': False, 'D': True, 'L': False, 'R': True}, 
(3, 4): {'U': True, 'D': False, 'L': True, 'R': False}, 
(3, 5): {'U': True, 'D': True, 'L': False, 'R': False}, 
(3, 6): {'U': True, 'D': True, 'L': False, 'R': False}, 
(3, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
(4, 0): {'U': True, 'D': True, 'L': False, 'R': False}, 
(4, 1): {'U': False, 'D': True, 'L': False, 'R': True}, 
(4, 2): {'U': False, 'D': False, 'L': True, 'R': True}, 
(4, 3): {'U': True, 'D': False, 'L': True, 'R': False}, 
(4, 4): {'U': False, 'D': False, 'L': False, 'R': True},
(4, 5): {'U': True, 'D': True, 'L': True, 'R': False}, 
(4, 6): {'U': True, 'D': False, 'L': False, 'R': False}, 
(4, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
(5, 0): {'U': True, 'D': False, 'L': False, 'R': False}, 
(5, 1): {'U': True, 'D': True, 'L': False, 'R': False}, 
(5, 2): {'U': False, 'D': True, 'L': False, 'R': True}, 
(5, 3): {'U': False, 'D': True, 'L': True, 'R': False}, 
(5, 4): {'U': False, 'D': False, 'L': False, 'R': True}, 
(5, 5): {'U': True, 'D': True, 'L': True, 'R': True}, 
(5, 6): {'U': False, 'D': True, 'L': True, 'R': True}, 
(5, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
(6, 0): {'U': False, 'D': True, 'L': False, 'R': False}, 
(6, 1): {'U': True, 'D': False, 'L': False, 'R': True}, 
(6, 2): {'U': True, 'D': False, 'L': True, 'R': False}, 
(6, 3): {'U': True, 'D': True, 'L': False, 'R': True}, 
(6, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
(6, 5): {'U': True, 'D': False, 'L': True, 'R': False}, 
(6, 6): {'U': True, 'D': True, 'L': False, 'R': True}, 
(6, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
(7, 0): {'U': True, 'D': False, 'L': False, 'R': True}, 
(7, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
(7, 2): {'U': False, 'D': False, 'L': True, 'R': True}, 
(7, 3): {'U': True, 'D': False, 'L': True, 'R': True}, 
(7, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
(7, 5): {'U': False, 'D': False, 'L': True, 'R': True}, 
(7, 6): {'U': True, 'D': False, 'L': True, 'R': False}, 
(7, 7): {'U': True, 'D': False, 'L': False, 'R': False}}
start = (5, 5)
end = (2, 2)
queue = collections.deque()
queue.append(start)
seen = set([start])
parent = {}
while queue:
path = queue.popleft()
i, j = path
print(path)
if (i,j) == end:
print("We found the end")
print_path(start,end)
break
#--- check up
if (paths.get((i, j)).get("U") == True) and ((i - 1, j) not in seen):
queue.append((i - 1, j))
seen.add((i - 1, j))
parent[(i - 1 ,j)] = (i, j)
#--- check Down
if (paths.get((i, j)).get("D") == True) and ((i + 1, j) not in seen):
queue.append((i + 1, j))
seen.add((i + 1, j))
parent[(i + 1,j)] = (i, j)
#--- check Left
if (paths.get((i, j)).get("L") == True) and ((i, j - 1) not in seen):
queue.append((i, j - 1))
seen.add((i, j - 1))
parent[(i,j - 1)] = (i, j)
#--- check Left
if (paths.get((i, j)).get("R") == True) and ((i, j + 1) not in seen):
queue.append((i, j + 1))
seen.add((i, j + 1))
parent[(i,j + 1)] = (i, j)