Currently attempting the Travelling Salesman Problem with a simulated annealing solution. All points are stored in a dictionary with the point name as the key and co-ordinates as the value. Having trouble writing a for loop(path_tour function) that goes through every key in a a given path(randomly shuffled dictionary of locations), calculates distances and adds the value to a list to retrun a total length. The current function I have below returns a KeyError, I cant figure out why.
#Calculate distances between points
def point_distance(point_a, point_b):
return math.sqrt((point_a[0] - point_b[0])**2 + (point_a[1] - point_b[1])**2)
def get_distance_matrix(points):
distance_matrix = {}
for location_a in points:
distance_matrix[location_a] = {}
for location_b in points:
distance_matrix[location_a][location_b] = point_distance(
points[location_a], points[location_b])
return distance_matrix
#Calculate length of path
def path_tour(tour):
path_length = 0
distances = get_distance_matrix(tour)
for key, value in tour.items():
path_length += distances[key][key[1:]]
return path_length
As you can see from the error, it was trying to look up the key "tudent Information Desk". I assume the location name was "Student Information Desk", so key[1:] removed the first letter. That's obviously not the correct location to look up.
I guess you want the distance from the current to the next location in the tour. That would be something like
locations = list(tour.keys())
for first, second in zip(locations[:-1], locations[1:]):
path_length += distances[first][second]
I don't get why your tour is a dictionary, though. Shouldn't it be a list to begin with? I know that dictionaries in Python-3 keep their insertion order but this usage seems counter-intuitive.