In [1]:
# Run this cell first!
from helpers import Map, load_map, show_map
from student_code import shortest_path
%load_ext autoreload
%autoreload 2
In [4]:
map_10 = load_map('map-10.pickle')
show_map(map_10)
The map above (run the code cell if you don't see it) shows a disconnected network of 10 intersections. The two intersections on the left are connected to each other but they are not connected to the rest of the road network.
These Map objects have two properties you will want to use to implement A* search: intersections and roads
Intersections
The intersections are represented as a dictionary.
In this example, there are 10 intersections, each identified by an x,y coordinate. The coordinates are listed below. You can hover over each dot in the map above to see the intersection number.
In [5]:
map_10.intersections
Out[5]:
Roads
The roads property is a list where roads[i] contains a list of the intersections that intersection i connects to.
In [8]:
# this shows that intersection 0 connects to intersections 7, 6, and 5
map_10.roads[8]
Out[8]:
In [9]:
# This shows the full connectivity of the map
map_10.roads
Out[9]:
In [2]:
# map_40 is a bigger map than map_10
map_40 = load_map('map-40.pickle')
show_map(map_40)
In [20]:
map_40.roads[24]
Out[20]:
The map above shows a network of roads which spans 40 different intersections (labeled 0 through 39).
The show_map function which generated this map also takes a few optional parameters which might be useful for visualizaing the output of the search algorithm you will write.
start - The "start" node for the search algorithm.goal - The "goal" node.path - An array of integers which corresponds to a valid sequence of intersection visits on the map.
In [3]:
# run this code, note the effect of including the optional
# parameters in the function call.
show_map(map_40, start=5, goal=34, path=[5,16,37,12,34])
You should open the file student_code.py in another tab and work on your algorithm there. Do that by selecting File > Open and then selecting the appropriate file.
The algorithm you write will be responsible for generating a path like the one passed into show_map above. In fact, when called with the same map, start and goal, as above you algorithm should produce the path [5, 16, 37, 12, 34]
> shortest_path(map_40, 5, 34)
[5, 16, 37, 12, 34]
In [3]:
path = shortest_path(map_40, 5, 34)
if path == [5, 16, 37, 12, 34]:
print("great! Your code works for these inputs!")
else:
print("something is off, your code produced the following:")
print(path)
If the code below produces no errors, your algorithm is behaving correctly. You are almost ready to submit! Before you submit, go through the following submission checklist:
Submission Checklist
A* search and not some other search algorithm?When you can answer "yes" to all of these questions, submit by pressing the Submit button in the lower right!
In [5]:
from test import test
test(shortest_path)