TSP using python

Question

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

Has your instructor mentioned about "graphs" or "graph theory" ? — Jon Clements
– Jon Clements, Commented Dec 8, 2012 at 12:33
What do you mean by "you failed"? Does it run? Does it give exceptions? Does it sometimes give the correct solution? Do you have weird bugs? What exactly is the problem you have? — phant0m
– phant0m, Commented Dec 8, 2012 at 12:50
Yeah. He mentioned Graph Theory. We gonna start it next lecture. This program gives error. Have added error in my Question — user1322731
– user1322731, Commented Dec 8, 2012 at 14:50

phant0m · Accepted Answer · 2012-12-08 12:50:17Z

1

Generate loads of random solutions.
Sort those solutions by length.
Delete the worst 50%
Combine the best 50% with each other in some way (splice them together)
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.

edited Dec 8, 2012 at 12:50

phant0m

17k6 gold badges52 silver badges84 bronze badges

answered Dec 8, 2012 at 12:29

Paul Collingwood

9,1013 gold badges27 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user1322731 Over a year ago

Thanks. But the task is to find the best one

Paul Collingwood Over a year ago

You should also mention the requirement for finding the best solution in your question, as for the TSP that means something quite significant.

Arturas Lapinskas · Accepted Answer · 2017-10-04 04:51:35Z

0

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

answered Oct 4, 2017 at 4:51

Arturas Lapinskas

3362 silver badges14 bronze badges

Collectives™ on Stack Overflow

TSP using python

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related