gpt4 book ai didi

python - 旅行推销员: Get all possible Paths with recursion

转载 作者:太空宇宙 更新时间:2023-11-03 16:40:42 24 4
gpt4 key购买 nike

我正在尝试编写一个递归方法来计算旅行商问题的所有可能路径:

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”,但随后不会继续,因为对于下一次调用,所有城市都已被删除。

我做错了什么?

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

最佳答案

解决办法很简单。这是因为 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了解更多详情。

希望能帮到你

代号Lambda

关于python - 旅行推销员: Get all possible Paths with recursion,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36814983/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com