在这个最短路径问题中，我如何设法获得请求的输出？

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])