Посещение всех узлов и добавление их к пути

Question

Я пытаюсь посетить все узлы, вернуться к начальному узлу (Neamt) и добавить посещенные узлы к path, но проблема в том, что если я захожу в тупик, город удаляется из path.

Вот 1 из возможных path, которые производит код:

['Neamt', 'Iasi', 'Vaslui', 'Urziceni', 'Bucharest', 'Fagaras', 'Sibiu', 'Oradea', 'Zerind', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Pitesti', 'Rimnicu Vileea']

Как показано ввыше path, нет 'Hirsova', 'Eforie', 'Giurgiu'.Что действительно происходит, когда я отлаживаюсь на PyCharm: 'Hirsova', 'Eforie', 'Giurgiu' добавляются к path, но затем они удаляются из path.

Я хочу включить эти города в path в обратном порядкеorder. Например:

['Neamt', 'Iasi', 'Vaslui', 'Urziceni', 'Hirsova', 'Eforie', 'Hirsova', 'Urziceni', 'Bucharest', 'Giurgiu', 'Bucharest', 'Pitesti', 'Rimnicu Vileea', 'Craiova', 'Drobeta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad', 'Zerind', 'Oradea', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt',]

Почему они удаляются из path, поскольку нет никакой противоположности методу .append, например .delete?

def find_paths(node, cities, path, distance):
    # Add way point
    path.append(node)
    #print('path:', path)

# Fork paths for all possible cities not yet used
    for city in cities:
        if (city not in path) and (node in cities[city]):
            find_paths(city, dict(cities), list(path), distance)
#What has to be:
count = 0 # avoid adding end paths twice
    for city in cities[node].keys(): # only recurse on children not the whole list
        if city not in visited: 
            count += 1
            find_paths(city, cities, path, distance, visited)
    if count > 0 : # only add again if there were children
        path.append(node)
#////////////

if __name__ == '__main__':
    cities = {
    'Arad': {'Sibiu': 140, 'Timisoara': 118, 'Zerind': 75},
    'Hirsova': {'Eforie': 86, 'Urziceni': 98},
    'Bucharest': {'Fagaras': 211, 'Giurgiu': 90, 'Pitesti': 101, 'Urziceni': 85},
    'Craiova': {'Drobeta': 120, 'Pitesti': 138, 'Rimnicu Vileea': 146},
    'Drobeta': {'Craiova': 120, 'Mehadia': 75},
    'Eforie': {'Hirsova': 86},
    'Fagaras': {'Bucharest': 211, 'Sibiu': 99},
    'Giurgiu': {'Bucharest': 90},
    'Iasi': {'Neamt': 87, 'Vaslui': 92},
    'Lugoj': {'Mehadia': 70, 'Timisoara': 111},
    'Mehadia': {'Drobeta': 75, 'Lugoj': 70},
    'Neamt': {'Iasi': 87},
    'Oradea': {'Sibiu': 151, 'Zerind': 71},
    'Pitesti': {'Bucharest': 101, 'Craiova': 138, 'Rimnicu Vileea': 97},
    'Rimnicu Vileea': {'Craiova': 146, 'Pitesti': 97, 'Sibiu': 80},
    'Sibiu': {'Arad': 140, 'Fagaras': 99, 'Oradea': 151, 'Rimnicu Vileea': 80},
    'Timisoara': {'Arad': 118, 'Lugoj': 111},
    'Urziceni': {'Bucharest': 85, 'Hirsova': 98, 'Vaslui': 142},
    'Vaslui': {'Iasi': 92, 'Urziceni': 142},
    'Zerind': {'Arad': 75, 'Oradea': 71}
    }

    #print("Start: Neamt")
    find_paths('Neamt', cities, [], 0)

Answer 1

Вам просто нужно выполнить поиск в глубину и добавить узлы, прежде чем вводить рекурсию и после.Это помещает имя в список, когда вы начинаете путь, а затем снова на обратном пути, когда рекурсия раскручивается.Процесс:

1. Добавить город
2. Рекурсировать на детей (если ребенок не посещается)
3. Добавить город еще раз (если это не конец пути)

Вам необходимо добавить проверку на завершение пути, чтобы не добавлять такие города, как Эфорие, дважды подряд.Если в городе нет не посещенных детей, вы не добавите его снова.Для этого просто следите за количеством рекурсий.

Что-то вроде:

def find_paths(node, cities, path, distance, visited = set()):

    visited.add(node) # keep track of visited nodes
    path.append(node)

    # Fork paths for all possible cities not yet used
    count = 0 # avoid adding end paths twice
    for city in cities[node].keys(): # only recurse on children not the whole list
        if city not in visited: 
            count += 1
            find_paths(city, cities, path, distance, visited)
    if count > 0 : # only add again if there were children
        path.append(node)

a = []
find_paths('Neamt', cities, a, 0)
print(a)

Результат:

['Neamt', 'Iasi', «Васлуй», «Урзичени», «Бухарест», «Фэгэраш», «Сибиу», «Арад», «Тимишоара», «Лугож», «Мехадия», «Дробета», «Крайова», «Питешти», «Rimnicu Vileea ',' Pitesti ',' Craiova ',' Drobeta ',' Mehadia ',' Lugoj ',' Timisoara ',' Zerind ',' Oradea ',' Zerind ',' Arad ',' Sibiu ',' Fagaras',' Джурджу ',' Бухарест ',' Хирсова ',' Эфорие ',' Хирсова ',' Урзичени ',' Васлуй ',' Яссы ',' Нямц ']

Answer 2

Ничего не удаляется, вы просто видите разные кадры find_paths с разными значениями path.list(path) делает копии, так что каждый вызов функции получает свой собственный список, и после завершения вызова функции и перемещения обратно вверх по стеку рекурсии вы видите старое значение path, к которому не был добавлен узел.