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

2024-05-18 • 问答

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

#    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,1,-1,-1] 
    dy = [1,-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,n):
    if 0 <= x <= n-1 :
        if 0 <= y <= n-1 :
            return True
    return False

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

不是将True放在graph矩阵中，而是向后引用图形中的上一个位置（您从此处到达此处）。有了这些信息，您可以找到走过的完整路径，找到自己的位置。

这里是if中的内容。确保还更改了shortest_path方法的最后一行：

def shortest_path(start,end,n ):
    dx = [2,2,-2,1,-1,-1] 
    dy = [1,-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])

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

zhoujiemy 回答：在这种最短路径问题中，我如何设法获得请求的输出？

大家都在问