from queue import PriorityQueue from pprint import pprint class SearchAlgorithms: class graph:

# Graph of cities with connections to each city. Similar to our class exercises, you can draw it on a piece of paper # with step-by-step node inspection for better understanding graph = { 'San Bernardino': ['Riverside', 'Rancho Cucamonga'], 'Riverside': ['San Bernardino', 'Ontario', 'Pomona'], 'Rancho Cucamonga': ['San Bernardino', 'Azusa', 'Los Angeles'], 'Ontario': ['Riverside', 'Whittier', 'Los Angeles'], 'Pomona': ['Riverside', 'Whittier', 'Azusa', 'Los Angeles'], 'Whittier': ['Ontario','Pomona', 'Los Angeles'], 'Azusa': ['Rancho Cucamonga', 'Pomona', 'Arcadia'], 'Arcadia': ['Azusa', 'Los Angeles'], 'Los Angeles': ['Rancho Cucamonga', 'Ontario', 'Pomona', 'Whittier', 'Arcadia'] }

# Weights are treated as g(n) function as we studied in our class lecture which represents the backward cost. # In the data structure below, the key represents the cost from a source to target node. For example, the first # entry shows that there is a cost of 2 for going from San Bernardino to Riverside. weights = { ('San Bernardino', 'Riverside'): 2, ('San Bernardino', 'Rancho Cucamonga'): 1, ('Riverside', 'Ontario'): 1, ('Riverside', 'Pomona'): 3, ('Rancho Cucamonga', 'Los Angeles'): 5, ('Pomona', 'Los Angeles'): 2, ('Ontario', 'Whittier'): 2, ('Ontario', 'Los Angeles'): 3, ('Rancho Cucamonga', 'Azusa'): 3, ('Pomona', 'Azusa'): 2, ('Pomona', 'Whittier'): 2, ('Azusa', 'Arcadia'): 1, ('Whittier', 'Los Angeles'): 2, ('Arcadia', 'Los Angeles'): 2 }

# heurist is the h(n) function as we studied in our class lecture which represents the forward cost. # In the data structure below, each entry represents the h(n) value. For example, the second entry # shows that h(Riverside) is 2 (i.e., h value as forward cost for eaching at Riverside assuming that # your current/start city is San Bernardino)

heuristic = { 'San Bernardino': 4, 'Riverside': 2, 'Rancho Cucamonga': 1, 'Ontario': 1, 'Pomona': 3, 'Whittier': 4, 'Azusa': 3, 'Arcadia': 2, 'Los Angeles': 0 }

def AStar(self, start, goal, graph, weights, heuristic): """Search the node that has the lowest combined cost and heuristic first. Important things to remember 1 - Use PriorityQueue with .put() and .get() functions 2 - In addition to putting the start or current node in the queue, and the g(n), also put the combined cost (i.e., g(n) + h(n)) using weights and heuristic data structure 3 - When you're expanding the neighbor of the current you're standing at, get its g(neighbor) by weights[(node, neighbor)] 4 - Calling weights[(node, neighbor)] may throw KeyError exception which is due to the fact that the weights data structure only has one directional weights. In the class, we mentioned that there is a path from Arad to Sibiu and back. If the exception occurs, you will need to get the weight of the nodes in reverse direction (weights[(neighbor, node)]) """ "*** YOUR CODE HERE ***"