Find the best travel route to visit the following 16 cities. Use the branch and bound algorithm. cities = [{"x": 38.24, "y": 20.42}, {"x": 39.57, "y": 26.15}, {"x": 40.56, "y": 25.32}, {"x": 36.26, "y": 23.12}, {"x": 33.48, "y": 10.54}, {"x": 37.56, "y": 12.19}, {"x": 38.42, "y": 13.11}, {"x": 37.52, "y": 20.44}, {"x": 41.23, "y": 9.10}, {"x": 41.17, "y": 13.05}, {"x": 36.08, "y": -5.21}, {"x": 38.47, "y": 15.13}, CS4795 Introduction to AI Lab #01, Page 4 / 4 2019-01-17 {"x": 38.15, "y": 15.35}, {"x": 37.51, "y": 15.17}, {"x": 35.49, "y": 14.32}, {"x": 39.36, "y": 19.56}] The distance between two cities are computed by the following code. def dist(p,q): dx = p[x] - q[x] dy = p[y] - q[y] return math.sqrt(dx*dx + dy*dy) print(cities[0],cities[1]) Provided that we visit all the cities and returns to the starting city, the cost can be measured by the following code. def travel_distance(path,cities): p = cities[path[0]] d = 0 for n in path[1:]: q = cities[n] d += dist(p,q) p = q d += dist(p,cities[path[0]]) return d For example, the travel distance for the the following path is given as folows: path = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] print(travel_distance(path,cities)) 104.42225210207233 Assuming that you are a travel agent, suggest a travel plan. Hint: If you are a really good agent, your customer can visit all the cities with the distance which is less than 75

#########################################

Note: Just started to learn python a week ago, Please correct any syntax error and complete the code using branch and bound algorithm

Code I have so far:

import math import queue

path = [] dic = {} UpperBound= 104.4222 current_position = '' cities = [{"x": 38.24, "y": 20.42}, {"x": 39.57, "y": 26.15}, {"x": 40.56, "y": 25.32}, {"x": 36.26, "y": 23.12}, {"x": 33.48, "y": 10.54}, {"x": 37.56, "y": 12.19}, {"x": 38.42, "y": 13.11}, {"x": 37.52, "y": 20.44}, {"x": 41.23, "y": 9.10}, {"x": 41.17, "y": 13.05}, {"x": 36.08, "y": -5.21}, {"x": 38.47, "y": 15.13}, {"x": 38.15, "y": 15.35}, {"x": 37.51, "y": 15.17}, {"x": 35.49, "y": 14.32}, {"x": 39.36, "y": 19.56}]

#opt_old = [1, 14, 13, 12, 7, 6, 15, 5, 11, 9, 10, 16, 3, 2, 4, 8] #opt = [x - 1 for x in opt_old]

#Creating node struct

class Node: def __init__(self,dataval=[],cost= None): self.dataval = dataval self.totalDistance = None self.cost = None

def dist(p,q): dx = p['x'] - q['x'] dy = p['y'] - q['y'] return math.sqrt(dx*dx + dy*dy)

def travel_distance(path,cities): p = cities[path[0]] d = 0 for n in path[1:]: q = cities[n] d += dist(p,q) p = q d += dist(p,cities[path[0]]) return d

#initializing a queue Q = queue.Queue(maxsize=0)

#running Branch and bound algorithm

dic['Node{0}'.format(0)]= Node(cities[0]) Q.put(dic['Node{0}'.format(0)]) current_position = dic['Node{0}'.format(0)] while(Q.empty!=True): for n in range(1,15):

#totalDistance += dist(current_position,citites(n)) #tempNode = Node(path.append(cities(n)),dist(current_position,citites(n))).totalDistance(totalDistance) #dic['Node'.format(n)] = tempNode

if(current_position == dic['Node{n}'.format(n=n)]): n=n+1

totalDistance = 0 totalDistance += dist(cities[current_position[4]],cities[n]) tempNode = Node(path.append(cities[n]),dist(cities[current_position[4]],cities[n])) tempNode.totalDistance(totalDistance) dic['Node{n}'.format(n=n)] = tempNode

if(tempNode.cost

#finding the optimal path

#print(dic.values())