Travelling Salesman Problem

[huhandrey]

Hello, guys!

I have a task to make a Travelling salesman problem. The code i attached bellow is only conneting the lines from 1 to 5(for example). But the task is to make the line goes through 1-2-3-4-5 and then go back to 1 again. Please, help me Asap

import random, math
import itertools
import tkinter as tk
from tkinter import simpledialog

def distance(x1,y1,x2,y2):
#distance between 2 points
#math.sqrt((x1-x2)**2+(y1-y2)**2)
return math.sqrt((x1-x2)**2+(y1-y2)**2)

def changeR (event=None):
global N
x=[]
y=[]
for i in range(N):
x.append(random.choice(range(650)))
y.append(random.choice(range(650)))
bestpath,minDistance=findBestpath(x,y)

hC.delete('all')
#display points
for i in range(N):
hC.create_oval(x[i]-2,y[i]-2,x[i]+2,y[i]+2, fill='black')

#display the best path
xy=[x[bestpath[0]],y[bestpath[0]]]
for i in bestpath[1:]:
xy.extend([x[i],y[i]])
hC.create_line(xy,fill='red')



def changeN():
global N
n=simpledialog.askinteger('Get N', 'Enter the number of points:')
if not n:return
N=n
doAlloverAgain()

def startNewJob():
doAlloverAgain()

def findBestpath(x,y):
n=len(x)
paths=list(itertools.permutations(range(n)))
bestpath=0
minDistance=9999999999999999999999999
for path in paths:
totalD=0
for i,j in zip(path[:4], path[1:]):
totalD+=distance(x[i]-2,y[i]-2,x[j]+2,y[j]+2)
if totalD<minDistance:
minDistance=totalD
bestpath=path
return bestpath, minDistance


def doAlloverAgain():
x=[]
y=[]
for i in range(N):
x.append(random.choice(range(boundary)))
y.append(random.choice(range(boundary)))
result,minDistance=findBestpath(x,y)

hC.delete('all')
#display points
for i in range(N):
hC.create_oval(x[i]-2,y[i]-2,x[i]+2,y[i]+2, fill='black')

#display the best path
xy=[x[path[0]],y[path[0]]]
for i in path[1:]:
xy.extend([x[i],y[i]])
hC.create_line(xy,fill='red')



N=5
boundary=200
x=[]
y=[]
for i in range(N):
x.append(random.choice(range(200)))
y.append(random.choice(range(200)))

paths=list(itertools.permutations(range(N)))
bestpath=0
minDistance=9999999999999999999
for path in paths:
#we are going to compute the total distance for each path
#total distance=sum of distances between points
#for example:path=(2,3,4,1,0)
#distance(x[2],y[2],x[3],y[3])
#distance(x[3],y[3],x[4],y[4])
#distance(x[4],y[4],x[1],y[1])
totalD=0
for i,j in zip(path[4:], path[1:]):
totalD+=distance(x[i],y[i],x[j],y[j])
if totalD<minDistance:
minDistance=totalD
bestpath=path
result=list(path)

hw=tk.Tk()
hw.title('G1005a Travelling Salesman problem, Khegay Andrey, 12184775')

hF=tk.Frame(hw)
hF.pack(side='left')

hB=tk.Button(hF, text='Start New Job', command=startNewJob)
hB.pack()
hB2=tk.Button(hF, text='Change N', command=changeN)
hB2.pack()
hB3=tk.Button(hF, text='Change range', command= changeR)
hB3.pack()

hC=tk.Canvas(hw,width=650, height=300)
hC.pack(side='left')

#display points
for i in range(N):
hC.create_oval(x[i]-2,y[i]-2,x[i]+2,y[i]+2, fill='black')

#display the best path
xy=[x[bestpath[0]],y[bestpath[0]]]
for i in bestpath[1:]:
xy.extend([x[i],y[i]])
hC.create_line(xy,fill='red')

[deanhystad]

Add a line from 5 to 0, or draw a polygon.

[deanhystad]

This does not calculate the path distance

totalD=0
for i,j in zip(path[:4], path[1:]):
    totalD+=distance(x[i]-2,y[i]-2,x[j]+2,y[j]+2)

This almost works if the path has 5 points, but it does not work at all for a different number of points.  It also doesn't add in the distance from the last point back to the starting point.  And why are you subtracting and adding 2?  Was this copied from the code that draws the dots?  There is no need for the offset.  You should also consider using numbers instead of dots so you can tell where the route starts and ends.

Once you change the distance calculation to be correct, you'll need to do the same thing when drawing the map.  Either add in a line segment to return to start, or you could create a polygon.

You have a lot of duplicate code and some has errors.  Clean it up so each block of code only appears once.  The code that generates the map should not be in the main body and in the changeR() and in the doOverAgain(). It should appear only once, and if you need to use it multiple places it should be a function that is called from multiple places.  To understand what you are doing and where you went wrong, I edited your code and got it to run.  With lots of comments it is still only 80 lines long and could be much shorter.[/i][/i]