Geek Answers Handbook

TSP using python

I was given homework to come up with a python program to solve the Travelers sellers problem. In the class, they explained how it should work and showed one example.

path_map = [[0,10,15,20], [5,0,9,10], [6,13,0,12], [8,8,9,0]]

This is an example map. I thought it was a popular problem, and I can find algorithms to solve this problem on the Internet. But I could not. I tried my own version. But I failed. Any help would be appreciated. That's what i still have

 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 `

What do I get when I try to run it:

 >>> 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 42, in min_path m[i]=self.cost + self.min_path(v) 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
+4
source share
2 answers
  • Generate loads of random decisions.
  • Sort these solutions by length.
  • Remove the worst 50%
  • Align the top 50% with each other in some way (splicing them together)
  • Go to 2.

Repeat this until you get a stable solution. This (almost certainly) will not be optimal, but it will be much better than random.

+1
source

IndexError: index pop out of range - cases when the iteration index does not exist, for example list = [1,2,3], have 3 elements, and you are trying to get the list [10], you will get this error

0
source

More articles:


All Articles