如何跟踪最短路径 BFS 中的级别？

Question

我正在编写一个问题，要求我仅使用马移动（L 形移动）在 8 x 8 棋盘上找到 2 个点之间的最少步数。

我很确定我的代码没问题，只是不知道我应该在代码中的哪个位置跟踪步数。

这是代码。

start = tuple(map(int, raw_input().split()))
goal = tuple(map(int, raw_input().split()))
steps = 0
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
    if vertex not in visited:
        visited.add(vertex)
        if vertex == goal:
            print steps
            break
        else:
            if vertex[0] >= 3 and vertex[1] >= 2:
                queue.append(tuple([(vertex[0] -2), (vertex[1]-1)]))

            if vertex[0] >= 2 and vertex[1] >= 3:
                queue.append(tuple([(vertex[0] -1), (vertex[1]-2)]))

            if vertex[0] >= 3 and vertex[1] <=7:
                queue.append(tuple([(vertex[0] -2), (vertex[1]+1)]))

            if vertex[0] >=2 and vertex[1] <= 6:
                queue.append(tuple([(vertex[0] -1), (vertex[1]+2)]))

            if vertex[0] <= 6 and vertex[1] >= 2:
                queue.append(tuple([(vertex[0] +2), (vertex[1]-1)]))

            if vertex[0] <= 7 and vertex[1] >=3:
                queue.append(tuple([(vertex[0] +1), (vertex[1]-2)]))

            if vertex[0] <= 7 and vertex[1] <= 6:
                queue.append(tuple([(vertex[0] +1), (vertex[1]+2)]))

            if vertex[0] <= 6 and vertex[1] <= 7:
                queue.append(tuple([(vertex[0] +2), (vertex[1]+1)]))
            queue.append(0)

Answer 1

BFS 中的一种可能性是跟踪您如何到达每个顶点 - 所以基本上每当我们移动到一个新顶点时，我们都会跟踪导致当前顶点的 "prior" 顶点。当我们到达目标顶点时，我们简单地使用 "prior" 顶点列表回溯我们的步骤，这给了我们步骤的数量和顺序。

编辑：仔细查看了您的代码，发现 mbomb007 是正确的。您的代码仅计算下一个可能的移动并将它们添加到 PQ。为了计算移动次数，您需要找到一种方法来跟踪您的骑士的移动。

Answer 2

我很确定您需要跟踪队列中的步数和顶点。换句话说，不是只排队顶点，而是包括到达该顶点所采取的步数：

queue = [(start, 0)] #[ ((x, y), steps-so-far) ]

然后，在主循环中：

(vertex, steps) = queue.pop(0)
#...
    if vertex[0] >= 3 and vertex[1] >= 2:
        newVertex = (vertex[0] -2, vertex[1]-1) # No need to explicitly call tuple()
        queue.append( (newVertex, steps+1) )
    # And so on...

编辑：下面关于重现步骤顺序的内容……并不是那么简单。被访问的地图可能有一个顶点多次出现，所以需要有一种方法来知道哪个是正确的。这可能会变得混乱。更好的解决方案可能是跟踪 整个前面的序列 而不仅仅是前面的顶点。

如果您想要实际的步骤顺序，AdmiralWen 的想法是正确的。您可以保留前一个顶点，而不是保留步数。将对 (vertex, prev-vertex) 存储在您的访问集中，以便您可以在完成后追溯序列。请注意，在这种情况下，visited 应该是一个映射，而不是一个集合，其中键是一个顶点，值是前一个顶点。

如何跟踪最短路径 BFS 中的级别？

How to track levels in shortest path BFS?

python

breadth-first-search

shortest-path