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

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

函数。我修改列表参数，每个城市在索引 0 上一次。

（我想使用以下列表实例调用 allPaths：

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

）

但是，当我调试这个时，城市-

toCover

列表在allPaths的所有“实例”中被修改。这意味着，它返回第一个有效路径“ABCD”，但随后不会继续，因为对于下一次调用，所有城市都已被删除。

我做错了什么？

我希望这个解释是清楚的......

Answer 1

解决方案很简单。这是因为

toCover

（如果你问我的话，应该命名为

to_cover

，但是嘿，这是你的代码 ^^）是一个列表。 列表是可变的，这意味着每个实例都拥有对原始对象的reference，从而导致所有更改都在所有引用上完成的问题（好吧，它们实际上只是针对对象完成的，但引用指向该对象，所以...)。

您可以通过三种方式解决：

• 使用元组代替，或者仅使用列表，就好像它是元组一样

  您将

  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[:]

  （这应该位于函数的顶部）。它创建一个包含整个列表的切片（再次：此链接），并有效地复制它。

• 使用

  itertools.permutations

  可以完成你想做的事情。 （请参阅@John Coleman 对您问题的评论）有关更多详细信息，请参阅python 文档。