旅行商:通过递归获取所有可能的路径
Traveling Salesman: Get all possible Paths with recursion
我正在尝试编写一个递归方法来计算旅行商问题的所有可能路径:
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
列表在所有 "instances" 的 allPaths 中被修改。这意味着,它 returns 第一个有效路径 "ABCD",但随后不会继续,因为对于下一次调用,所有城市都已被删除。
我做错了什么?
我希望这个解释是清楚的...
解决方法很简单。这是因为 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[:]
(这应该在你的函数的顶部)。它创建一个包含整个列表的切片(再次:this link),有效地复制它。
使用 itertools.permutations
即可完成您想做的事情。 (请参阅@John Coleman 对您的问题的评论)有关详细信息,请参阅 python documentation。
希望能帮到你,
代号Lambda
我正在尝试编写一个递归方法来计算旅行商问题的所有可能路径:
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
列表在所有 "instances" 的 allPaths 中被修改。这意味着,它 returns 第一个有效路径 "ABCD",但随后不会继续,因为对于下一次调用,所有城市都已被删除。
我做错了什么?
我希望这个解释是清楚的...
解决方法很简单。这是因为 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[:]
(这应该在你的函数的顶部)。它创建一个包含整个列表的切片(再次:this link),有效地复制它。使用
itertools.permutations
即可完成您想做的事情。 (请参阅@John Coleman 对您的问题的评论)有关详细信息,请参阅 python documentation。
希望能帮到你,
代号Lambda