Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ##############################################<START OF PROGRAM>##############################################
- def setUpCanvas(root): # These are the REQUIRED magic lines to enter graphics mode.
- root.title("THE TRAVELING SALESMAN PROBLEM by (your name here).")
- canvas = Canvas(root, width = root.winfo_screenwidth(), height = root.winfo_screenheight(), bg = 'black')
- canvas.pack(expand = YES, fill = BOTH)
- return canvas
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def script(x, y, msg = '', kolor = 'WHITE'):
- canvas.create_text(x, y, text = msg, fill = kolor, font = ('Helvetica', 10, 'bold'))
- #---------------------------------------------------------------------------------Traveling Salesman Problem-
- def plot(city): # Plots 5x5 "points" on video screen
- x = city[1]+5; y = city[2]+5 # The +5 is to push away from the side bars.
- if city[0] == -1:
- kolor = 'WHITE'
- else: kolor = 'YELLOW'
- canvas.create_rectangle(x-2, y-2, x+2, y+2, width = 1, fill = kolor)
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def line(city1, city2, kolor = 'RED'):
- canvas.create_line(city1[1]+5, city1[2]+5, city2[1]+5, city2[2]+5, width = 1, fill = kolor)
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def displayDataInConsole(AlgorithmResults, baseCity, city):
- print('===<Traveling Salesman Path Statistics>===')
- print (' algorithm path length ')
- for element in AlgorithmResults:
- print ('---%-20s'%element[0], int(element[2]))
- city.sort()
- baseCity.sort()
- if city == baseCity:
- print("---Data verified as unchanged.")
- else:
- print ('ERROR: City data has been corrupted!')
- print(' Run time =', round(clock()-START_TIME, 2), ' seconds.')
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def printCity(city): # Used for debugging.
- count = 0
- for (id,x,y) in city:
- print( '%3d: id =%2d, (%5d, %5d)'%(count,id, int(x), int(y)))
- count += 1
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def displayPathOnScreen(city, statistics):
- #=---Normalize data
- (minX, maxX, minY, maxY, meanX, meanY, medianX, medianY, size, m, b) = statistics
- canvas.delete('all')
- cityNorm, (p,q,r,s) = normalizeCityDataToFitScreen(city[:], statistics)
- #---Plot points and lines
- cityNorm.append(cityNorm[0])
- plot(cityNorm[0])
- for n in range(1, len(cityNorm)):
- plot(cityNorm[n])
- line(cityNorm[n], cityNorm[n-1])
- script(650, 20, 'path length = ' + str(pathLength(city)))
- canvas.create_rectangle(530,10, 770, 30, width = 1, outline = 'WHITE')
- canvas.update()
- root.mainloop() # Required for graphics.
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def normalizeCityDataToFitScreen(city, statistics):
- """ Coordinates are all assumed to be non-negative."""
- (minX, maxX, minY, maxY, meanX, meanY, medianX, medianY, size, m, b) = statistics
- newCity = []
- #---Step 1a. Shift city points to the x- and y-axes.
- for (id, x,y) in city:
- newCity.append ( (id, x-minX, y-minY))
- #---Step 1b. Shift line-of-best-fit to the x- and y-axes.
- (x0,y0) = (maxX-minX, m*maxX+b - minY) # = x-intercept of line-of-best-fit.
- (x1,y1) = (minX-minX, m*minX+b - minY) # = y-intercept of line-of-best-fit.
- #---Step 1c. Shift max-values to x- and y-axes.
- maxX = maxX-minX
- maxY = maxY-minY
- #---Step 2a. # Re-scale city points to fit the screen.
- cityNorm = []
- for (id, x, y) in newCity:
- cityNorm.append ((id, x*SCREEN_WIDTH/maxX, y*SCREEN_HEIGHT/maxY))
- #---Step 2b. # Re-scale the x-axis and y-axis intercepts for the line-of-best-fit.
- (x0,y0) = x0/maxX*SCREEN_WIDTH, y0/maxY*SCREEN_HEIGHT # a point on the x-axis
- (x1,y1) = x1/maxX*SCREEN_WIDTH, y1/maxY*SCREEN_HEIGHT # a point on the y-axis
- return cityNorm, (x1,y1,x0,y0) # = the adjusted city xy-values and 2 points on the line-of-best-fit.
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def readDataFromFileAndAppendId(fileName):
- file1 = open(fileName, 'r')
- fileLength = int(file1.readline()) # removes heading
- city = []
- for elt in range(fileLength):
- x, y = file1.readline().split()
- city.append( [0, float(x), float(y)] ) # A place for an id (0, here) is appended.
- file1.close()
- return city
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def getFileLength(fileName):
- file1 = open(fileName, 'r')
- fileLength = int(file1.readline()) # removes heading
- return fileLength
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def pathLength(city):
- totalPath = 0
- for n in range(1, len(city)):
- totalPath += dist( city[n-1], city[n] )
- totalPath += dist( city[n], city[0] )
- return int(totalPath)
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def dataStatistics(city):
- xValues = []
- yValues = []
- size = len(city)
- for (id, x,y) in city:
- xValues.append(x)
- yValues.append(y)
- minX = min(xValues)
- maxX = max(xValues)
- minY = min(yValues)
- maxY = max(yValues)
- assert (minX >= 0 or maxX >= 0 or minY >= 0 or maxY >= 0)
- meanX = sum(xValues)/size
- meanY = sum(yValues)/size
- medianX = city[len(city)//2][0]
- medianY = city[len(city)//2][1]
- #---Derive the line of best fit: y = mx+b
- xyDiff = 0
- xDiffSqr = 0
- for (id, x,y) in city:
- xyDiff += (meanX - x)*(meanY - y)
- xDiffSqr+= (meanX - x)**2
- m = xyDiff/xDiffSqr
- b = meanY - m*meanX
- return minX, maxX, minY, maxY, meanX, meanY, medianX, medianY, size, m, b
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def dist(cityA, cityB):
- return hypot(cityA[1]-cityB[1], cityA[2] - cityB[2])
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def chunks(l, n):
- n = max(1, n)
- l.pop()
- return [l[i:i + n] for i in range(0, len(l), n)]
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def printToFile(distances, myfile):
- for item in distances:
- myfile.write("%s\n" % item)
- myfile.write("\n")
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def myAlgorithm(distances,city,fileLength):
- for x in range(len(city)):
- for y in range(len(city)):
- if x+y+1<len(city):
- distances.append(dist(city[x],city[x+y+1]))
- elif city[x] !=city[(x+y)%(fileLength-1)]:
- distances.append(dist(city[x],city[(x+y)%(fileLength-1)]))
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def ySort(city):
- for item in city:
- item[1],item[2]=item[2],item[1]
- city.sort()
- for item in city:
- item[1],item[2]=item[2],item[1]
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- def xSort(city):
- city.sort()
- #====================================<GLOBAL CONSTANTS and GLOBAL IMPORTS>========Traveling Salesman Problem==
- from tkinter import Tk, Canvas, YES, BOTH
- from operator import itemgetter
- from itertools import permutations
- from copy import deepcopy
- from random import shuffle
- from time import clock
- from math import hypot
- from operator import itemgetter
- from collections import OrderedDict
- root = Tk()
- canvas = setUpCanvas(root)
- START_TIME = clock()
- SCREEN_WIDTH = root.winfo_screenwidth() //5*5 - 15 # adjusted to exclude task bars on my PC.
- SCREEN_HEIGHT = root.winfo_screenheight()//5*5 - 90 # adjusted to exclude task bars on my PC.
- fileName = "tsp0038.txt" # My file name will be different from yours
- #==================================================< MAIN >=======================Traveling Salesman Problem==
- def main():
- #---0. Read in data, append an id to every pair, and store results in a variable called "city".
- fileLength = getFileLength(fileName)
- city = readDataFromFileAndAppendId(fileName)
- #---1. Extract statistics.
- statistics = (minX, maxX, minY, maxY, meanX, meanY, medianX, medianY, size, m, b) = dataStatistics(city)
- #---2. Create a random path.
- shuffle(city)
- #---3. Sort on y-coordinate and connect sequentially by y.
- ySort(city)
- #---4. Sort on x-coordinate and connect sequentially by x.
- xSort(city)
- #---5. Greedy Algorithm
- z=[]
- for x in range(len(city)-1):
- print(x)
- if x==0:
- z.append(city[x])
- temp=dist(city[x],city[x+1])
- for y in range(len(city)-1):
- if dist(city[x],city[y+1])<temp:
- z.append(city[y+1])
- break
- city=z
- #---6. Display results.
- displayPathOnScreen(city, statistics)
- #---------------------------------------------------------------------------------Traveling Salesman Problem--
- if __name__ == '__main__': main()
- ###############################################<END OF PROGRAM>###############################################
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement