停留在最小骑士的移动以到达终点位置

Question

我正在解决这个问题：

Find the minimum number of steps required by the knight to move from the starting position to the end position in a nXn chess board. If the path does not exists, then return -1

我写了下面的代码：

def is_position_safe(n, cur_row, cur_col):
    if 0 <= cur_row < n and 0 <= cur_col < n:
        return True
    else:
        return False


def min_moves(n, cur_row, cur_col, end_row, end_col, visited):
    if cur_row == end_row and cur_col == end_col:
        return 0

    key = tuple([cur_row, cur_col])

    visited_temp = visited.copy()
    if is_position_safe(n, cur_row, cur_col) and key not in visited:
        visited_temp.append(key)
        d1 = min_moves(n, cur_row - 2, cur_col - 1, end_row, end_col, visited_temp)
        d2 = min_moves(n, cur_row - 2, cur_col + 1, end_row, end_col, visited_temp)
        d3 = min_moves(n, cur_row - 1, cur_col - 2, end_row, end_col, visited_temp)
        d4 = min_moves(n, cur_row - 1, cur_col + 2, end_row, end_col, visited_temp)
        d5 = min_moves(n, cur_row + 1, cur_col - 2, end_row, end_col, visited_temp)
        d6 = min_moves(n, cur_row + 1, cur_col + 2, end_row, end_col, visited_temp)
        d7 = min_moves(n, cur_row + 2, cur_col - 1, end_row, end_col, visited_temp)
        d8 = min_moves(n, cur_row + 2, cur_col + 1, end_row, end_col, visited_temp)

        return  min(d1, d2, d3, d4, d5, d6, d6, d7, d8) + 1
    else:
        return float('inf')


def min_knight_moves(n, cur_row, cur_col, end_row, end_col):
    result = min_moves(n, cur_row, cur_col, end_row, end_col, [])

    if result != float('inf'):
        return result
    else:
        return -1

print(min_knight_moves(10, 9, 9, 6, 3))

在某些情况下它不起作用。例如，对于上面的那个，它返回我 5，但实际答案是 3.

我不明白我哪里做错了。谁能帮帮我。

P.S.: 我知道有现有的解决方案，通过使用 BFS，但我正在尝试递归解决这个问题。我不太确定，我哪里错了。感谢你的帮助。谢谢！

Answer 1

记忆可能不是最好的情况，因为骑士可以从不同的路径到达某个地点，并且对于每条路径都有不同的访问集。因此我建议创建一个 visited_temp = visited.copy() 并将其转发到递归中而不使用记忆。

visited_temp = visited.copy()
    if is_position_safe(n, cur_row, cur_col) and key not in visited:
        visited_temp.append(key)
        d1 = min_moves(n, cur_row - 2, cur_col - 1, end_row, end_col, visited_temp)
        d2 = min_moves(n, cur_row - 2, cur_col + 1, end_row, end_col, visited_temp)
        d3 = min_moves(n, cur_row - 1, cur_col - 2, end_row, end_col, visited_temp)
        d4 = min_moves(n, cur_row - 1, cur_col + 2, end_row, end_col, visited_temp)
        d5 = min_moves(n, cur_row + 1, cur_col - 2, end_row, end_col, visited_temp)
        d6 = min_moves(n, cur_row + 1, cur_col + 2, end_row, end_col, visited_temp)
        d7 = min_moves(n, cur_row + 2, cur_col - 1, end_row, end_col, visited_temp)
        d8 = min_moves(n, cur_row + 2, cur_col + 1, end_row, end_col, visited_temp)

        return  min(d1, d2, d3, d4, d5, d6, d6, d7, d8) + 1
    else:
        return float('inf')

这个问题也被称为 self avoiding walk problem. I have posted a DFS solution without memoization to the self avoiding walk 但我选择 DFS 只是因为所有可能的路径都是 objective。自我回避行走不能有记忆，因为正如我所说，每条路径都有自己的访问集。

请注意，由于您希望通过递归而不是 BFS 使用 DFS，因此您的运行时间将呈指数增长，因为您必须在决定之前计算所有路径。我选择了 BFS 方法，由于 BFS 的性质，您可以停止到达目的地。

运行建议的解决方案

在 10X10 网格上需要很长时间，因为运行时间呈指数级增长，因此对于较低网格上的以下类似示例，我们得到：

print(min_knight_moves(5, 4,  4, 2, 0))  # 2

对于 6 或更大的网格大小，我在它结束之前杀死了运行，因为它需要很长时间，递归在这个问题上不是一个好的方法

停留在最小骑士的移动以到达终点位置

Stuck at minimum knight's move to reach the end position

python

algorithm

recursion

运行建议的解决方案

停留在最小骑士的移动以到达终点位置

Stuck at minimum knight's move to reach the end position

python

algorithm

recursion

运行 建议的解决方案

运行建议的解决方案