python - 混淆递归中的对象引用行为

Question

我写了一个深度优先搜索，它基于 this 搜索迷宫中的路径。问题:

# for convenience
matrix = [
    ["0", "0", "0", "0", "1", "0", "0", "0"],
    ["0", "1", "1", "0", "1", "0", "1", "0"],
    ["0", "1", "0", "0", "1", "0", "1", "0"],
    ["0", "0", "0", "1", "0", "0", "1", "0"],
    ["0", "1", "0", "1", "0", "1", "1", "0"],
    ["0", "0", "1", "1", "0", "1", "0", "0"],
    ["1", "0", "0", "0", "0", "1", "1", "0"],
    ["0", "0", "1", "1", "1", "1", "0", "0"]
]
num_rows = len(matrix)
num_cols = len(matrix[0])
goal_state = (num_rows - 1, num_cols - 1)
print(goal_state)


def dfs(current_path):
    # anchor
    row, col = current_path[-1]
    if (row, col) == goal_state:
        print("Anchored!")
        return True

    # try all directions one after the other
    for direction in [(row, col + 1), (row, col - 1), (row + 1, col), (row - 1, col)]:
        new_row, new_col = direction
        if (0 <= new_row < num_rows and 0 <= new_col < num_cols and  # stay in matrix borders
                matrix[new_row][new_col] == "0" and                  # don't run in walls
                (new_row, new_col) not in current_path):             # don't run in circles
            current_path.append((new_row, new_col))  # try new direction
            print(result == current_path)
            if dfs(current_path):  # recursive call
                return True
            else:
                current_path = current_path[:-1]  # backtrack


# the result is a list of coordinates which should be stepped through in order to reach the goal
result = [(0, 0)]
if dfs(result):
    print("Success!")
    print(result)
else:
    print("Failure!")

它的工作方式与我预期的一样，只是最后两个坐标没有添加到名为 result 的列表中。 .这就是我加入 print(result == current_path) 这一行的原因，在我的期望中，它应该总是为真——它是同一个对象，作为引用传递。它怎么可能不相等呢？代码应该是可执行的，但为了以防万一，这是我得到的输出:

True
True
...
True
False
False
Anchored!
Success!
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (6, 1), (6, 2), (6, 3), (6, 4), (5, 4), (4, 4), (3, 4), (3, 5), (2, 5), (1, 5), (0, 5), (0, 6), (0, 7), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (5, 6)]

从输出中应该清楚，如果最后一个状态是(7, 7)，函数只能锚定。 , 即与 (6, 7) 一起, 不存在于 result 中多变的。我很惊讶为什么。

编辑:坐标(5, 6) ，它存在于 result 中列表，不应该在那里。它是算法回溯的最后位置，即到达目标状态之前的死胡同。我再次不知道为什么在回溯步骤中它没有从两个列表中正确删除。

Answer 1

current_path = current_path[:-1] 创建一个新列表，并将名称 current_path 绑定(bind)到这个新创建的列表。在那个阶段，它不再是与 result 相同的列表。请查看列表方法 pop()。