[Python骑士之旅-从前辈那里获取路径

Question

我正在尝试在Python中采用深度优先搜索算法来解决“骑士之旅”难题。我想我几乎成功了，为所有访问过的广场制作了前辈的字典。

但是，我坚持如何找到骑士的最终道路。当前，使用current中tour()的path()返回值会得出[(0, 0), (2, 1)]令人失望的路径。

我认为问题的症结在于确定在tour()内部的所有点均被访问，并在该点返回当前的平方，如果没有解决方案，则返回None。

任何人都可以帮助我调整代码以产生正确的解决方案吗？

offsets = (
    (-1, -2), (1, -2),
    (-2, -1), (2, -1),
    (-2, 1), (2, 1),
    (-1, 2), (1, 2),
)

def is_legal_pos(board, pos):
    i, j = pos
    rows = len(board)
    cols = len(board[0])
    return 0 <= i < rows and 0 <= j < cols


def path(predecessors, start, goal):
    current = goal
    path = []
    while current != start:
        path.append(current)
        current = predecessors[current]
    path.append(start)
    path.reverse()
    return path


def tour(board, start):
    stack = []
    stack.append(start)
    discovered = set()
    discovered.add(start)
    predecessors = dict()
    predecessors[start] = None

    while stack:
        current = stack.pop()
        for move in offsets:
            row_offset, col_offset = move
            next = (current[0] + row_offset, current[1] + col_offset)
            if is_legal_pos(board, next) and next not in discovered:
                stack.append(next)
                discovered.add(next)
                predecessors[next] = current

    return predecessors, current


board = [[" "] * 5 for row in range(5)]
start = (0, 0)
predecessors, last = tour(board, start)
print(predecessors)
print(path(predecessors, start, last))

Answer 1

您的方法有以下问题：

• 该算法仅执行遍历（实际上不是搜索），并且在访问（发现）所有节点后，堆栈将解开，直到从中弹出最后一个正方形为止。最后一个正方形是有史以来第一个被压入堆栈的正方形，因此肯定不是代表长路径末尾的节点。
• 它不包括检测游览的逻辑。
• 基于“发现的”数组，您将仅分析一个正方形，这意味着您希望找到不带回溯的游览，因为在第一个回溯之后，您将无法在某些变体中再次使用已经访问过的正方形路径。
• 前身数组是用于广度优先搜索的概念，但对于深度优先搜索而言并没有很好的用途
• 您假设有解决方案，但是您使用5x5网格调用该函数，并且在奇数大小的板上没有封闭的骑士之旅

[尝试使用堆栈而不是递归来实现它，这会使您自己变得比需要的要难。

我更改了您的代码以使用递归，并解决了上述问题。

offsets = (
    (-1, -2), (1, -2),
    (-2, -1), (2, -1),
    (-2, 1), (2, 1),
    (-1, 2), (1, 2),
)


# We don't need the board variable. Just the number of rows/cols are needed:
def is_legal_pos(rows, cols, pos):
    i, j = pos
    return 0 <= i < rows and 0 <= j < cols


def tour(rows, cols, start):
    discovered = set()
    n = rows * cols

    def dfs(current):  # Use recursion
        discovered.add(current)
        for move in offsets:
            row_offset, col_offset = move
            # Don't name your variable next, as that is the name of a native function
            neighbor = (current[0] + row_offset, current[1] + col_offset)
            # Detect whether a closed tour was found
            if neighbor == start and len(discovered) == n:
                return [start, current]  # If so, create an extendable path
            if is_legal_pos(rows, cols, neighbor) and neighbor not in discovered:
                path = dfs(neighbor)
                if path:  # Extend the reverse path while backtracking
                    path.append(current)
                    return path
        # The choice of "current" did not yield a solution. Make it available
        # for a later choice, and return without a value (None)
        discovered.discard(current)

    return dfs(start)

# No need for a board variable. Just number of rows/cols is enough.
# As 5x5 has no solution, call the function for a 6x6 board:
print(tour(6, 6, (0, 0)))

要使用显式堆栈执行此操作，还需要将for循环的状态放到堆栈上，即，您应该以某种方式知道循环何时结束。为此，您可以使堆栈成为其中的一个元素是仍然需要访问的邻居列表，其中包括“当前”列表。因此，堆栈将是列表的列表：

offsets = (
    (-1, -2), (1, -2),
    (-2, -1), (2, -1),
    (-2, 1), (2, 1),
    (-1, 2), (1, 2),
)


# We don't need the board variable. Just the number of rows/cols are needed:
def is_legal_pos(rows, cols, pos):
    i, j = pos
    return 0 <= i < rows and 0 <= j < cols


def tour(rows, cols, start):
    discovered = set()
    n = rows * cols
    stack = [[start]]

    while stack:
        neighbors = stack[-1]
        if not neighbors:  # Need to backtrack...
            stack.pop()
            # remove the node that ended this path, and unmark it
            neighbors = stack[-1]
            current = neighbors.pop(0)
            discovered.discard(current)
            continue
        while neighbors:
            current = neighbors[0]
            discovered.add(current)
            neighbors = []   # Collect the valid neighbors
            for move in offsets:
                row_offset, col_offset = move
                # Don't name your variable next, as that is the name of a native function
                neighbor = (current[0] + row_offset, current[1] + col_offset)
                # Detect whether a closed tour was found
                if neighbor == start and len(discovered) == n:
                    path = [start]  # If so, create the path from the stack
                    while stack:
                        path.append(stack.pop()[0])
                    return path
                if is_legal_pos(rows, cols, neighbor) and neighbor not in discovered:
                    neighbors.append(neighbor)
            # Push the collection of neighbors: deepening the search
            stack.append(neighbors)


# No need for a board variable. Just number of rows/cols is enough.
# As 5x5 has no solution, call the function for a 6x6 board:
print(tour(6, 6, (0, 0)))

我个人认为此代码比递归版本更令人困惑。您应该真正进行递归。

请注意，这种幼稚的方法远非高效。实际上，我们对6x6板感到幸运。如果您将偏移量以其他顺序列出，则可能需要更长的时间才能找到解决方案。

请查阅Wikipedia的文章Kinght's Tour，其中列出了一些效率更高的算法。