Math: Travelling Salesman Problem in Python?

http://pp.kpnet.fi/jhii/galerio/pics/tsmprob002.png
I have the following problem: There are points (P0…P6) on the plane, and I have a need to find the shortest cyclic path connecting them. What I have found, this is the classical Travelling Salesman Problem. But how do I solve it in Python? (The amount of points is supposed to be something about [3…12])

By now I have got it this far:


import math

def dist(a,b):
  (x1,y1) = a
  (x2,y2) = b
  return math.sqrt((x2-x1)**2+(y2-y1)**2)

points=[(0.0,0.0),(2.0,4.0),(4.0,1.0),(3.0,6.0),(7.0,4.0),(6.0,0.0)]

w={}
for i in range(len(points)):
  for j in range(i,len(points)):
    w[i,j]=w[j,i]=dist(points[i],points[j])

print w

Maybe something like this:

from math import sqrt
    
def getNext(point):
    best = points[0] # default
    x = point.x - p.x
    y = point.y - p.y
    best_dis = sqrt(x**2 + y**2)
    for p in points[1:]:
        x = point.x - p.x
        y = point.y - p.y
        dis = sqrt(x**2 + y**2)
        if dis < best_dis: best = p; best_dis = dis
    return best

points = [b,c,d,e,f] # **a is not here**
path = [a]
start = a
current = a
next = None
while len(points) != 0:
    next = getNext(current)
    path.append(next)
    points.remove(next)
    current = next
    
print path

That should work I guess, it just takes the next closest point to the current point and repeats until its done.

i tried to run this little script but

got an error on line

points = [b,c,d,e,f]

name b is not defined ?

can you tell how to correct this

Thanks

I think the algorithm doesn’t work on situations of this kind:
http://pp.kpnet.fi/jhii/galerio/pics/P0123.jpg
It gets the cycle [ P0 P1 P3 P4 ], and leaves P2 last.

My original problem is this:
http://pp.kpnet.fi/jhii/galerio/pics/roads001.jpg

The yellow dots are known. Let’s say we select the road 5 and try to follow the red dotted line to 2. Intuitively we see 2 comes after 5, but how could computer calculate it? I don’t know if the “Travelling Salesman Problem” gives the same answer ( 5 2 4 1 6 3 ), but I guess usually it does.

I got some kind of solution to the last problem using this polygon library: http://pypi.python.org/pypi/Polygon/1.17

The idea is to make rectangles to represent the roads, then take union of them, and lastly walk around the contour until the distances to the yellow dots are close to zero.
http://pp.kpnet.fi/jhii/galerio/pics/roadsU001.jpg
The polygon library gives the routines for union operation and contour.