# coding=utf-8
This file is your main submission that will be graded against. Only copy-paste
code on the relevant classes included here. Do not add any classes or functions
to this file that are not part of the classes that we want.
import heapq
import pickle
import math
class PriorityQueue(object):
A queue structure where each element is served in order of priority.
Elements in the queue are popped based on the priority with higher priority
elements being served before lower priority elements. If two elements have
the same priority, they will be served in the order they were added to the
Traditionally priority queues are implemented with heaps, but there are any
number of implementation options.
(Hint: take a look at the module heapq)
Attributes:
queue (list): Nodes added to the priority queue.
def __init__(self):
“””Initialize a new Priority Queue.”””
self.queue = []
def pop(self):
Pop top priority node from queue.
The node with the highest priority.
# TODO: finish this function!
raise NotImplementedError
def remove(self, node):
Remove a node from the queue.
Hint: You might require this in ucs. However, you may
choose not to use it or to define your own method.
node (tuple): The node to remove from the queue.
raise NotImplementedError
def __iter__(self):
“””Queue iterator.”””
return iter(sorted(self.queue))
def __str__(self):
“””Priority Queue to string.”””
return ‘PQ:%s’ % self.queue
def append(self, node):
Append a node to the queue.
node: Comparable Object to be added to the priority queue.
# TODO: finish this function!
raise NotImplementedError
def __contains__(self, key):
Containment Check operator for ‘in’
key: The key to check for in the queue.
True if key is found in queue, False otherwise.
return key in [n[-1] for n in self.queue]
def __eq__(self, other):
Compare this Priority Queue with another Priority Queue.
other (PriorityQueue): Priority Queue to compare against.
True if the two priority queues are equivalent.
return self.queue == other.queue
def size(self):
Get the current size of the queue.
Integer of number of items in queue.
return len(self.queue)
def clear(self):
“””Reset queue to empty (no nodes).”””
self.queue = []
def top(self):
Get the top item in the queue.
The first item stored in the queue.
return self.queue[0]
def breadth_first_search(graph, start, goal):
Warm-up exercise: Implement breadth-first-search.
See README.md for exercise description.
graph (ExplorableGraph): Undirected graph to search.
start (str): Key for the start node.
goal (str): Key for the end node.
The best path as a list from the start and goal nodes (including both).
# TODO: finish this function!
raise NotImplementedError
def uniform_cost_search(graph, start, goal):
Warm-up exercise: Implement uniform_cost_search.
See README.md for exercise description.
graph (ExplorableGraph): Undirected graph to search.
start (str): Key for the start node.
goal (str): Key for the end node.
The best path as a list from the start and goal nodes (including both).
# TODO: finish this function!
raise NotImplementedError
def null_heuristic(graph, v, goal):
Null heuristic used as a base line.
graph (ExplorableGraph): Undirected graph to search.
v (str): Key for the node to calculate from.
goal (str): Key for the end node to calculate to.
def euclidean_dist_heuristic(graph, v, goal):
Warm-up exercise: Implement the euclidean distance heuristic.
See README.md for exercise description.
graph (ExplorableGraph): Undirected graph to search.
v (str): Key for the node to calculate from.
goal (str): Key for the end node to calculate to.
Euclidean distance between `v` node and `goal` node
# TODO: finish this function!
raise NotImplementedError
def a_star(graph, start, goal, heuristic=euclidean_dist_heuristic):
Warm-up exercise: Implement A* algorithm.
See README.md for exercise description.
graph (ExplorableGraph): Undirected graph to search.
start (str): Key for the start node.
goal (str): Key for the end node.
heuristic: Function to determine distance heuristic.
Default: euclidean_dist_heuristic.
The best path as a list from the start and goal nodes (including both).
# TODO: finish this function!
raise NotImplementedError
def bidirectional_ucs(graph, start, goal):
Exercise 1: Bidirectional Search.
See README.md for exercise description.
graph (ExplorableGraph): Undirected graph to search.
start (str): Key for the start node.
goal (str): Key for the end node.
The best path as a list from the start and goal nodes (including both).
# TODO: finish this function!
raise NotImplementedError
def bidirectional_a_star(graph, start, goal,
heuristic=euclidean_dist_heuristic):
Exercise 2: Bidirectional A*.
See README.md for exercise description.
graph (ExplorableGraph): Undirected graph to search.
start (str): Key for the start node.
goal (str): Key for the end node.
heuristic: Function to determine distance heuristic.
Default: euclidean_dist_heuristic.
The best path as a list from the start and goal nodes (including both).
# TODO: finish this function!
raise NotImplementedError
def tridirectional_search(graph, goals):
Exercise 3: Tridirectional UCS Search
See README.MD for exercise description.
graph (ExplorableGraph): Undirected graph to search.
goals (list): Key values for the 3 goals
The best path as a list from one of the goal nodes (including both of
the other goal nodes).
# TODO: finish this function
raise NotImplementedError
def tridirectional_upgraded(graph, goals, heuristic=euclidean_dist_heuristic, landmarks=None):
Exercise 4: Upgraded Tridirectional Search
See README.MD for exercise description.
graph (ExplorableGraph): Undirected graph to search.
goals (list): Key values for the 3 goals
heuristic: Function to determine distance heuristic.
Default: euclidean_dist_heuristic.
landmarks: Iterable containing landmarks pre-computed in compute_landmarks()
Default: None
The best path as a list from one of the goal nodes (including both of
the other goal nodes).
# TODO: finish this function
raise NotImplementedError
def return_your_name():
“””Return your name from this function”””
# TODO: finish this function
raise NotImplementedError
def compute_landmarks(graph):
Feel free to implement this method for computing landmarks. We will call
tridirectional_upgraded() with the object returned from this function.
graph (ExplorableGraph): Undirected graph to search.
List with not more than 4 computed landmarks.
return None
def custom_heuristic(graph, v, goal):
Feel free to use this method to try and work with different heuristics and come up with a better search algorithm.
graph (ExplorableGraph): Undirected graph to search.
v (str): Key for the node to calculate from.
goal (str): Key for the end node to calculate to.
Custom heuristic distance between `v` node and `goal` node
# Extra Credit: Your best search method for the race
def custom_search(graph, start, goal, data=None):
Race!: Implement your best search algorithm here to compete against the
other student agents.
If you implement this function and submit your code to Gradescope, you’ll be
registered for the Race!
See README.md for exercise description.
graph (ExplorableGraph): Undirected graph to search.
start (str): Key for the start node.
goal (str): Key for the end node.
data : Data used in the custom search.
Will be passed your data from load_data(graph).
Default: None.
The best path as a list from the start and goal nodes (including both).
# TODO: finish this function!
raise NotImplementedError
def load_data(graph, time_left):
Feel free to implement this method. We’ll call it only once
at the beginning of the Race, and we’ll pass the output to your custom_search function.
graph: a networkx graph
time_left: function you can call to keep track of your remaining time.
usage: time_left() returns the time left in milliseconds.
the max time will be 10 minutes.
* To get a list of nodes, use graph.nodes()
* To get node neighbors, use graph.neighbors(node)
* To get edge weight, use graph.get_edge_weight(node1, node2)
# nodes = graph.nodes()
return None
def haversine_dist_heuristic(graph, v, goal):
Note: This provided heuristic is for the Atlanta race.
graph (ExplorableGraph): Undirected graph to search.
v (str): Key for the node to calculate from.
goal (str): Key for the end node to calculate to.
Haversine distance between `v` node and `goal` node
#Load latitude and longitude coordinates in radians:
vLatLong = (math.radians(graph.nodes[v][“pos”][0]), math.radians(graph.nodes[v][“pos”][1]))
goalLatLong = (math.radians(graph.nodes[goal][“pos”][0]), math.radians(graph.nodes[goal][“pos”][1]))
#Now we want to execute portions of the formula:
constOutFront = 2*6371 #Radius of Earth is 6,371 kilometers
term1InSqrt = (math.sin((goalLatLong[0]-vLatLong[0])/2))**2 #First term inside sqrt
term2InSqrt = math.cos(vLatLong[0])*math.cos(goalLatLong[0])*((math.sin((goalLatLong[1]-vLatLong[1])/2))**2) #Second term
return constOutFront*math.asin(math.sqrt(term1InSqrt+term2InSqrt)) #Straight application of formula