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

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 в обратном порядке. Такие как:

['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)

Результаты в

["Нямц", "Яссы", "Васлуй", "Урзичени", "Бухарест", "Фагарас", "Сибиу", "Арад", "Тимишоара", "Лугож", "Мехадия", "Дробета", " Крайова "," Питешти "," Рымнику Вилея "," Питешти "," Крайова "," Дробета "," Мехадия "," Лугож "," Тимишоара "," Зеринд "," Орадя "," Зеринд "," Арад " ',' Сибиу ',' Фэгэраш ',' Джурджу ',' Бухарест ',' Хирсова ',' Эфорие ',' Хирсова ',' Урзичени ',' Васлуй ',' Яссы ',' Нямц ']

Answer 2

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