коммивояжера: Получить все возможные пути с помощью рекурсии

Question

Я пытаюсь написать метод рекурсии рассчитать все возможные пути задачи коммивояжера:

def allPaths(toCover, path=""): 

    path = path + toCover[0] 
    toCover.remove(toCover[0]) 

    if len(toCover)>0: 
     for x in range (0, len(toCover)): 
      #swop cities 
      temp = toCover[0] 
      toCover[0] = toCover[x] 
      toCover[x] = temp 
      allPaths(toCover, path) 
    else : 
     print path 


cities = ["A", "B", "C", "D"] 

allPaths(cities) 

Итак, у меня есть список городов.

Я добавляю первый город в список к текущему пути. Я удаляю добавленный город из городов toCover. Для каждого оставшегося города в списке я снова вызываю функцию allPaths(). Я изменяю параметр списка, чтобы каждый город был проиндексирован один раз.

(Я хочу, чтобы вызвать allPaths со следующими экземплярами списка:

[B,C,D] 
[C,B,D] 
[D,C,B] 

)

Однако, когда я отладки это, cities- toCover список модифицируется во всех "экземпляры" allPaths , Это означает, что он возвращает первый допустимый путь «ABCD», но затем не продолжается, потому что для следующего вызова все города уже удалены.

Что я делаю неправильно?

Я надеюсь, что это объяснение некоторые, что ясно ...

Answer 1

решение легко. Это потому, что toCover (его нужно называть to_cover, если вы спросите меня, но эй, это ваш код ^^) - это список. Списки являются изменяемыми, это означает, что каждый экземпляр содержит ссылку на исходный объект, в результате чего возникает проблема, что все изменения выполняются на всех ссылках (нормально, они действительно просто выполняются с объектом, но ссылки указывают на это объект, поэтому ...).

Вы можете решить тремя способами:

• Использование кортежа вместо этого, или просто используя список, как если бы это был кортеж

  Вы заменяете cities = ["A", "B", "C", "D"] с cities = ("A", "B", "C", "D") (если вы хотите, кортеж) и используйте toCover = toCover[1:] вместо toCover.remove(toCover[0]), который должен быть (если он должен изменить базовый объект) del toCover[0] в любом случае.

  x[1:] создает кусочек списка или кортежа (хотя вы можете реализовать почти все для этого оператора в своих собственных типах), в результате чего создается новый экземпляр с любым элементом, кроме первого. См. here (в документации на python отсутствует реальное объяснение, не спрашивайте меня почему).

• Дублирование список снова и снова

  Это решение является общим способом справиться с этой проблемой, но на самом деле это не так, как ехать сюда. Это происходит вокруг ссылки, скопировав список следующим образом: toCover = toCover[:] (это должно быть в верхней части вашей функции). Он создает срез (опять: this link), содержащий весь список, эффектно копируя его.

• Использование itertools.permutations, которое делает то, что вы хотите сделать. (см. комментарий @John Coleman по вашему вопросу) См. python documentation для более подробной информации.

Я надеюсь, что я мог бы помочь,

CodenameLambda