CODEWITHSUNDEEP
pythontraveling-salesman
user1322731
user1322731

Reputation: 71

TSP using python

I'm given homework to come up with the python program to solve Travellers salesman 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]]

It is an example map I thought it is popular problem and I can find algorithms to solve this problem in the internet. But I couldn't. I tried my own version. But I failed. Any help will be appreciated. Here is what I have so far

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

Upvotes: 4

Views: 9793

Answers (2)

Arturas Lapinskas
Arturas Lapinskas

Reputation: 336

IndexError: pop index out of range - cases when the iteration index doesn't exist the list, for example list = [1,2,3], have 3 elements, and you try to get list[10], you'll get that error

Upvotes: 0

Paul Collingwood
Paul Collingwood

Reputation: 9116

  1. Generate loads of random solutions.
  2. Sort those solutions by length.
  3. Delete the worst 50%
  4. Combine the best 50% with each other in some way (splice them together)
  5. Goto 2.

Repeat this until you have a stable solution. It (almost certainly) won't be optimal, but it'll be much much better than random.

Upvotes: 1

Related Questions