TSP使用python
发布时间:2020-12-20 13:32:05 所属栏目:Python 来源:网络整理
导读:我已经做了功课,想出解决旅行者推销员问题的 python程序.在课堂上,他们解释了它应该如何工作并展示了一个例子. path_map = [[0,10,15,20],[5,9,10],[6,13,12],[8,8,0]] 这是一个示例地图 我认为这是流行的问题,我可以找到解决这个问题的算法在互联网上.但我
我已经做了功课,想出解决旅行者推销员问题的
python程序.在课堂上,他们解释了它应该如何工作并展示了一个例子.
path_map = [[0,10,15,20],[5,9,10],[6,13,12],[8,8,0]] 这是一个示例地图 class TSP: def __init__(self,init,path_map): self.init = init self.cost = 0 self.path_map = path_map self.vertices = [i for i in range(1,len(path_map)+1)] def min_path(self,start): if not self.vertices: return self.path_map[start-1][init-1] else: m = [i for i in range(len(self.vertices)+1)] i=0 for v in self.vertices: tv = self.vertices.pop(v-1) m[i]=self.cost + self.min_path(v) self.vertices.insert(v-1,tv) i = i + 1 self.cost = self.cost + min(m) return cost ` 我得到的,当我尝试运行它时: >>> t = TSP(1,path_map) >>> t.min_path(1) Traceback (most recent call last): File "<pyshell#54>",line 1,in <module> t.min_path(1) File "/home/wanhrust/python/TSP.py",line 42,in min_path m[i]=self.cost + self.min_path(v) File "/home/wanhrust/python/TSP.py",line 41,in min_path tv = self.vertices.pop(v) IndexError: pop index out of range 解决方法
>生成大量随机解决方案.
>按长度排序这些解决方案. >删除最差的50% >以某种方式将最好的50%相互结合(将它们拼接在一起) >转到2. 重复此操作,直到找到稳定的解决方案.它(几乎可以肯定)不会是最优的,但它会比随机好得多. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |