旅行商：获得所有可能的路径使用递归

我想写一个递归方法来计算旅行商问题的所有可能的路径：旅行商：获得所有可能的路径使用递归

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()函数。我修改了列表参数，即每个城市都在索引0上。

（我想称之为allPaths下面这个列表实例：

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

）

然而，当我调试这一点，cities- toCover列表被跨越allPaths的所有 “实例” 修改。也就是说，它返回第一个有效路径“ABCD”，但之后不会继续，因为下次呼叫时，所有城市都已被移除。

我在做什么错？

我希望这个解释有些什么清楚...

来源

2016-04-23 blckbird

这是一个有趣的练习来工作的细节 - 但如果你想要的是一个解决方案'itertools'具有排列已经内置的。 –

解决方案很简单。这是因为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

来源

2016-04-23 19:14:34 CodenameLambda

旅行商：获得所有可能的路径使用递归

回答

相关问题