Verwirrende Objekt Referenzverhalten in Rekursion

Question

ich eine Tiefensuche geschrieben habe, die den Weg in einem Labyrinth sucht, basierend auf this Frage:

# 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!") 

Es funktioniert wie ich erwarten würde, mit der Ausnahme, dass die letzten beiden Koordinaten tun nicht in der Liste result hinzugefügt werden. Aus diesem Grund habe ich die Zeile print(result == current_path) eingefügt, die in meiner Erwartung immer wahr sein sollte - es ist das gleiche Objekt, das als Referenz übergeben wird. Wie könnte es jemals nicht gleich sein? Der Code sollte ausführbar sein wie es ist, aber nur für den Fall, das ist die Ausgabe erhalte ich:

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

Wie aus dem Ausgang klar sein, kann die Funktion nur verankert, wenn der letzte Zustand (7, 7) ist, die ist zusammen mit (6, 7) in der Variablen result nicht vorhanden. Ich bin verblüfft, warum.

edit: Die Koordinate (5, 6), die in der result Liste vorhanden ist, sollte nicht da sein. Es ist die letzte Position, von der aus der Algorithmus rückwärts läuft, die Sackgasse kurz vor Erreichen des Zielzustands. Ich habe wiederum keine Ahnung, warum es während des Backtracking-Schritts nicht ordnungsgemäß aus beiden Listen entfernt wurde.

Answer 1

erstellt eine neue Liste und bindet den Namen current_path an diese neu erstellte Liste. Zu diesem Zeitpunkt ist es nicht mehr die gleiche Liste wie result. Sehen Sie sich stattdessen die Listenmethode pop() an.