广度优先搜索错误输出

Question

teren = [
    '########',
    '#s.....#',
    '###..#.#',
    '#...##.#',
    '#.#....#',
    '#.####.#',
    '#......#',
    '###e####'
    ]

def bfs(teren, start, end):
    queue = []
    visited = []
    queue.append([start])

    while queue:
        path = queue.pop()
        node = path[-1]

        x = node[0]
        y = node[1]

        if node == end:
            return path
        if node in visited or teren[x][y] == "#":
            continue

        visited.append(node)

        for adjacent in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print(bfs(teren, (1,1), (7, 3)))

这是我用来尝试导航这种迷宫类型事物的代码，这是我得到的输出 [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 6), (3, 6), (4, 6), (4, 5), (4, 4), (4, 3), (3, 3), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (6, 3), (7, 3)] 而这是我需要的输出 [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (6, 3), (7, 3)]

这似乎是在打印出所有可行走的坐标，但我不知道如何解决这个问题，所有使用网格的在线示例都非常关注绘制网格，这会扰乱实际的 bfs。

Answer 1

如果您将队列视为队列，您将获得所需的输出。这意味着您不会弹出最后一个元素，而是移出第一个元素：

替换：

 path = queue.pop()

与：

 path, queue = queue[0], queue[1:]

或：

 path = queue.pop(0)

然而 deque-objects 更适合此类操作：

from collections import deque

def bfs(teren, start, end):
    queue = deque([])
    visited = []
    queue.append([start])

    while queue:
        path = queue.popleft()
        # ...etc.

广度优先搜索错误输出

Breadth first search wrong output

python

breadth-first-search