CPSC 415 - Artificial Intelligence - Fall 2023

Program #2 — Search algorithms

Possible experience: +40XP or +50XP or even +60XP

Due: Monday, Sep. 25th, midnight (see also bonus point deadline)


In this programming assignment, you will be implementing search algorithms on a synthetic road atlas to find routes from a source to a destination. You may implement the greedy search algorithm for +40XP, Dijkstra's algorithm for +50XP, or both of these plus the A* search algorithm for +60XP. Your algorithm will be equipped with an admissible heuristic function.

The Atlas class

I have provided a Python class called Atlas to represent the map you're traversing. It's in the file atlas.py in the class's github repo.

You can instantiate an Atlas in two ways:

  1. Via the constructor, to generate a random map. Give it the number of cities as an argument (10 is the default):
    tiny = Atlas()
    europe = Atlas(615)
  2. From a file. This is useful so you can verify whether your algorithms are working properly: I'll be able to provide test atlases (see "Verifying your solution is correct," below) with their solutions, and you can check your program. Call the from_filename() class method to do this:
    arrakis = Atlas.from_filename('arrakis.atlas')

There are two important Atlas methods:

Important: you are "charged" for each time you call get_road_dist() in the sense that the Atlas object keeps track of how many nodes you've expanded. This is how it "keeps score" and determines how efficient your algorithm is exploring the map. There is no charge for get_crow_flies_dist(), however; call it as many times as you like.

For what it's worth, both of the above methods are symmetric (i.e., ∀i,j get_road_dist(i,j) = get_road_dist(j,i), and similarly for get_crow_flies_dist()) although you shouldn't make any assumptions based on this. For all you know, there could be one-way streets and warped non-Euclidean realities.

Your mission

Your job is to write a Python function called find_path(). Its first line should look like this:

def find_path(atlas, alg):

The two arguments are an atlas object (instantiated in either of the above ways) and a string with one of the values greedy, Dijkstras, or astar. The function's job is to find a path (a sequence of visited cities) between city number 0 and city number atlas.num_cities-1 using that algorithm.

Your function should return a tuple of two elements: the first of which is a list of city (node) numbers, and the second of which is the (true, not estimated) total distance of that path.

For example, suppose a 5-city Atlas is passed to your function which has the following distances between cities:

0 554
983554 0 458358
358 0

The shortest path from city 0 to 4 (which you should verify) is 0→3→2→4, which has a cost of 970. Therefore, your Dijkstra's and A* functions should return this tuple:

([0,3,2,4], 970)

(Stare at that answer until you're sure you get it.)

Note that your greedy algorithm may or may not return that path — that will depend on the values the heuristic function gives for each city. It may well return a worse path. However, the path it does return as the first entry in the tuple had better have the total distance that is reflected in the second entry in the tuple.

Getting started

Refresh your repo with the latest contents by doing a git pull operation. (Make sure all your own stuff is committed first!) Then, use the file gps.py as a starting point. Change the comments at the top of your gps.py to include your own name instead of mine. Then, make sure that when you run gps.py like this:

$ python3 gps.py 5 Dijkstras

you get output that looks like this:

INFO:root:Building random atlas with 5 cities...
Best path from 0 to 4 costs 970: [0, 3, 2, 4].
You expanded 0 nodes: set()

When you get this result, commit the gps.py file to your repo. You are now ready to begin implementing the find_path() function in that file.

Verifying your solution is correct

Here are some sample atlas files, in order to verify that your A* solution is finding the optimal path (and optimally):

File# citiesOptimal pathGreedy pathOptimal
# nodes
# nodes
# nodes

To try these files, run your program with the atlas filename instead of the number of nodes, like this:

$ python3 gps.py ten.atlas Dijkstras

Carefully note that in order to get credit for either solution, the number of nodes you expand must not exceed the number listed in the table, above. If you were to exceed that number, that would indicate your algorithm is not working optimally, and will (probably) take forever to complete on any sizeable graph.

Less than full credit

My test script will assume that you have implemented all three algorithms. If you do not, please return the string "Unimplemented" from your function if it is called with an alg value you did not code.

Turning it in

You will turn this assignment in by attaching a git bundle to an email. (A "git bundle" is essentially a portable, zipped-up git repo.) The subject line of the email should be "CPSC 415 Program #2 turnin".

To do this, first make sure that all your code is checked into git. Running "git status" and ensuring your workspace is clean is a great way to do that. Then, bundle up your git repo:

$ git bundle create yourUmwUsername.git --all

and send me the yourUmwUsername.git file as an email attachment. (Please do not name it literally "yourUmwUsername.git" Substitute your actual UMW username. For instance, "jsmith3.git".)

Bonus: starting early and often

Note: the definition of "non-trivial" is "whatever Stephen deems is non-trivial."

Getting help

Come to office hours, or send me email with subject line "CPSC 415 Program #2 help!!"