我怎样才能设法在这个最短路径问题中获得请求的输出？

Question

我编写了这段代码，应该可以解决骑士的最短路径问题。问题是我不知道如何计算它在图表上达到的深度级别。

#    n = size of the board
#    start = starting position for example [0,0]
#    end = ending position 


def shortest_path(start , end , n ):
    dx = [2, 2, -2, -2, 1, 1, -1, -1] 
    dy = [1, -1, 1, -1, 2, -2, 2, -2] 
    graph = [[False for x in range(n)]for x in range(n)]
    graph[start[0]][start[1]] = True
    queue = []
    queue.append(start)
    while len(queue)> 0 :
        k = queue[0]
        queue.pop(0)
        for s in range(8):
            x = k[0] + dx[s]
            y = k[1] + dy[s]
            if x == end[0] and y == end[1] :
                return ????
            if valid(x , y ,n) and not graph[x][y] :
                graph[x][y] = True
                queue.append([x,y])



def valid(x , y ,n):
    if 0 <= x <= n-1 :
        if 0 <= y <= n-1 :
            return True
    return False

我应该在代码中添加什么？

Answer 1

不是将 True 放在 graph 矩阵中，而是将反向引用放在图表中的前一个位置（你从哪里来到这里）。有了这些信息，您就可以找到您到达当前位置所经过的完整路径。

这是要放入 if 的内容。确保还更改 shortest_path 方法的最后一行：

def shortest_path(start , end , n ):
    dx = [2, 2, -2, -2, 1, 1, -1, -1] 
    dy = [1, -1, 1, -1, 2, -2, 2, -2] 
    graph = [[False for x in range(n)]for x in range(n)]
    graph[start[0]][start[1]] = True
    queue = []
    queue.append(start)
    while len(queue)> 0 :
        k = queue[0]
        queue.pop(0)
        for s in range(8):
            x = k[0] + dx[s]
            y = k[1] + dy[s]
            if x == end[0] and y == end[1]:
                # Unwind graph information to build the path backwards to the start
                path = [[x,y], k]
                while k != start:
                    k = graph[k[0]][k[1]]
                    path.append(k)
                return path[::-1] # reverse
            if valid(x, y, n) and not graph[x][y]:
                graph[x][y] = k # store a back-reference here!
                queue.append([x,y])

我怎样才能设法在这个最短路径问题中获得请求的输出？

How can I manage to get the requested output in this shortest path problem?

python

algorithm

breadth-first-search

shortest-path