保持 BFS 搜索的路径

Question

给定一个迷宫、起点坐标和终点坐标，

maze = [
    [BLACK, BLACK, WHITE, WHITE],
    [BLACK, WHITE, WHITE, WHITE],
    [WHITE, WHITE, BLACK, WHITE],
    [WHITE, WHITE, BLACK, WHITE],
]
s = Coordinate(3, 0)
e = Coordinate(0, 3)

我正在尝试使用 BFS 查找从头到尾的路径。找到路径很简单，但我正在努力保持通往目的地的路径。我试过的是

directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
queue = collections.deque()
queue.append(s)
path = []
while queue:
    curr = queue.popleft()
    if curr == e:
        path.append(curr)
        return path
    path.append(curr)
    maze[curr.x][curr.y] = BLACK
    for x, y in directions:
        new_x, new_y = curr.x + x, curr.y + y
        if new_x < 0 or new_y < 0 or new_x >= len(maze) or new_y >= len(maze[0]) or maze[new_x][new_y] == BLACK:
            continue
        queue.append(Coordinate(new_x, new_y))

类似这样，但结果打印出我访问过的所有节点，而不是最终路径。关于保持正确路径和删除不属于最终路径的节点有什么技巧吗？

Answer 1

for x, y in directions:
    new_x, new_y = curr.x + x, curr.y + y
    if new_x < 0 or new_y < 0 or new_x >= len(maze) or new_y >= len(maze[0]) or maze[new_x][new_y] == BLACK:
        continue
    queue.append(Coordinate(new_x, new_y))

你的 queue.append(Coordinate(new_x, new_y)) 是运行每次你的 for 循环迭代。

我们希望这个条件只在我们的 if 条件运行时发生，所以让我们尝试这样的事情：

for x, y in directions:
    new_x, new_y = curr.x + x, curr.y + y
    if new_x < 0 or new_y < 0 or new_x >= len(maze) or new_y >= len(maze[0]) or maze[new_x][new_y] == BLACK:
        queue.append(Coordinate(new_x, new_y))
        continue

当满足我们的 if 条件时，附加它，然后继续。让我知道这是否有帮助。

Answer 2

您可以维护一个 edge_to 字典，而不是维护一个 path 列表，该字典跟踪哪个先前的顶点导致访问某个顶点。每当您向队列中添加内容时，您都可以更新 edge_to。使用此方法修改后的函数版本如下：

Coordinate = collections.namedtuple('Coordinate', ['x', 'y'])

def find_path(s, e):
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    queue = collections.deque()
    queue.append(s)
    edge_to = {s: None}

    while queue:
        curr = queue.popleft()
        if curr == e:
            return path(edge_to, curr)
        maze[curr.x][curr.y] = BLACK
        for x, y in directions:
            new_x, new_y = curr.x + x, curr.y + y
            if new_x < 0 or new_y < 0 or new_x >= len(maze) or new_y >= len(maze[0]) or maze[new_x][new_y] == BLACK:
                continue
            c = Coordinate(new_x, new_y)
            edge_to[c] = curr
            queue.append(c)

当您找到结束顶点时，请注意对 path(...) 的调用。该函数只是从 edge_to 字典中构建一个列表：

def path(edge_to, end):
    curr = end
    res = []
    while curr != None:
        res.append(curr)
        curr = edge_to[curr]
    return list(reversed(res))

对于给定的迷宫、起点和终点坐标，我们得到以下输出：

s = Coordinate(3, 0)
e = Coordinate(0, 3)
print(find_path(s, e))

输出

[Coordinate(x=3, y=0), Coordinate(x=2, y=0), Coordinate(x=2, y=1), Coordinate(x=1, y=1), Coordinate(x=1, y=2), Coordinate(x=0, y=2), Coordinate(x=0, y=3)]

保持 BFS 搜索的路径

Keeping the path of BFS search

python

breadth-first-search