# Centre of mass based TSP solution

This is the code that I tried to approach to the traveling salesman problem in a new way. As you can see, it does not give such great results. Can I get this idea further, or should I quit to approach this problem from this way?

So the thing that I tried there is using centre of mass to calculate where the cities are the most dense. But in my imagination I think that using just centre of mass would create a mess so I also added the current cities distance and with this two things added together I made a list of points to find the lowest value I have. The lowest value is where to go.

Can you help me to improve my code and give me your thoughts on this?

from tkinter import *
import math
import random

#Setting a class to write down the destination points
class City:
def __init__(self, coordinates, name):
self.coordinates = coordinates
self.name = name

#Setting up the lists that we will need
fake_origin_list = []
list_origin = []
distance_to_weight_center = []
closests_to_weight_center = []
last_list = []
sorted_sum_distance = []
sum_one = 0
sum_two = 0

for i in range(50):
a = City((random.randint(0, 700), random.randint(0, 800)), str(i))
list_origin.append(a)

def calculate(av_x, av_y):
distance_to_weight_center.clear()
for aa in list_origin:
distance_to_weight_center.append([int(math.sqrt((av_x-aa.coordinates[0])**2 + (av_y-aa.coordinates[1])**2)), aa.name])
for b in distance_to_weight_center:
closests_to_weight_center.append(b[0])
closests_to_weight_center.sort()
return closests_to_weight_center[-1]

def city_finder(distance):
for i in distance_to_weight_center:
if i[0] == distance:
last_list.append(i)
distance_to_weight_center.remove(i)
for dd in list_origin:
if int(dd.name) == int(i[1]):
fake_origin_list.append(dd)
list_origin.remove(dd)

break
return last_list[0][0]

xx = 0

def city_finder_two():
summone = 0
summtwo = 0
for a in list_origin:
summone += a.coordinates[0]
summtwo += a.coordinates[1]
avg_x = sum_one / len(list_origin)
avg_y = sum_two / len(list_origin)
sumfd = int(city_finder(calculate(avg_x,avg_y)))
for asdf in list_origin:
if int(asdf.name) == int(last_list[0][1]):
ff = asdf
awq = int(ff.coordinates[0])
b = int(ff.coordinates[1])
for i in list_origin:
c = int(i.coordinates[0])
d = int(i.coordinates[1])
sorted_sum_distance.append([math.sqrt((awq-c)**2+(b-d)**2) +sumfd,i.name])
sorted_sum_distance.sort()
return sorted_sum_distance[0][0]

for i in range(50):
for a in list_origin:
sum_one += a.coordinates[0]
sum_two += a.coordinates[1]
avg_x = sum_one / len(list_origin)
avg_y = sum_two / len(list_origin)
if i == 0:
city_finder(calculate(avg_x,avg_y))
else:
city_finder_two()

window=Tk()
window.config(bg='White')
window.title('Hello Python')
window.geometry("1000x1000+10+20")
canvas = Canvas(width = 800, height = 900, bg = "white")

for i in fake_origin_list:
canvas.create_oval(i.coordinates[0]-3,i.coordinates[1]-3,i.coordinates[0]+3,i.coordinates[1]+3, fill="Black")
for i in range(len(fake_origin_list)):
if i == len(fake_origin_list)-1:
total_road += math.sqrt((fake_origin_list[i].coordinates[0]-fake_origin_list[0].coordinates[0])**2 + (fake_origin_list[i].coordinates[1] - fake_origin_list[0].coordinates[1])**2)
canvas.create_line(fake_origin_list[i].coordinates[0], fake_origin_list[i].coordinates[1], fake_origin_list[0].coordinates[0],fake_origin_list[0].coordinates[1], width=2, fill='Blue')
else:
total_road += math.sqrt((fake_origin_list[i].coordinates[0]-fake_origin_list[i+1].coordinates[0])**2 + (fake_origin_list[i].coordinates[1] - fake_origin_list[i+1].coordinates[1])**2)
canvas.create_line(fake_origin_list[i].coordinates[0],fake_origin_list[i].coordinates[1],fake_origin_list[i+1].coordinates[0],fake_origin_list[i+1].coordinates[1],width=2,fill='Blue')
window.mainloop()


## Overview

You've done an good job:

• Encapsulating code into a class and functions
• You leveraged code written by others with the imports
• Used meaningful names for the class, functions and many of the variables

Here are some adjustments for you to consider, mainly for coding style.

## Unused code

This line is not used and can be removed:

xx = 0


## Layout

I recommend moving the functions to the top, after the class. Having them in the middle of the code interrupts the natural flow of the code (from a human readability standpoint).

## Lint check

pylint identified a few issues.

Only import what you need. Change:

from tkinter import *


to:

from tkinter import Tk, Canvas, Label


## Documentation

Add a docstring to the top of the file to summarize the purpose of the code.

The PEP 8 style guide recommends adding docstrings to functions, classes and methods. For the the functions. Describe their inputs and the returned values. The guide also discusses when to use comments.

## Naming

Some variables names are not descriptive enough. For example, dd. If it refers to some kind of distance, name it like dist.

Mostly look at the short ones: a, ff, asdf, etc.

## Long lines

Very long lines are hard to understand, especially ones without sufficient whitespace around operators, commas, etc.

canvas.create_oval(i.coordinates[0]-3,i.coordinates[1]-3,i.coordinates[0]+3,i.coordinates[1]+3, fill="Black")


You can use the black program to automatically modify the code for you for better readability.

The above suggestions will be the first step towards making the code easier to understand and modify to achieve your performance goal.

• Thank you so much for your comment on the code! While writing the code I didn't think about the variable names on the for loops becaıse they will be used for a short period of time. About long lines I did have a dilemma actually because I knew that the lines will be very long and if there was a mistake it would be harder to fix but at the same time I guessed that if I am using a thing only twice there was no meaning to create a variable to do that job. But you are right, if I am posting there a question I should be more clear on the code. Can you tell me should I use comment lines too?
– tumr
Mar 27 at 22:29
• @tumr: You're welcome. I updated my answer to include a link the the PEP-8 style guide where it discusses when to use docstrings and comments. Mar 27 at 22:48
• @tumr Long lines can be fixed in many ways.
– Mast
Mar 28 at 16:26