This is the fourth project of the Udacity Data Structures & Algorithms Nanodegree. This project comes at the end of the Advanced Algorithms section, which covers:
- Greedy Algorithms
- Graph Algorithms
- Dynamics programming
- A* Search Algorithm
The primary file in this repo is the student_code.py, which contains the A* search algorithm used to
plan the route between the given intersections. Please the docstrings within that file for a detailed description of the
code.
Note only does this file contain the shortest_path function, which is the primary route planner function, but it also
contains unit tests.
The required tests within test.py also rely on the functions within helpers.py and the map defined within map-40.pickle. map-10.pickle is a simpler test used for debugging and unit testing, since the required answers are easy to determine manually. All of these 4 files were provided as-is from Udacity except for helpers.py. This file had to be updated to allow for non-notebook execution.
To start we assume that the base Python v3.6.3 interpreter is installed and is in the Path. If not, please install the v3.6.3 interpreter from here.
The reason for the very old verion of Python is the map pickle files were create with a very old version of Python and NetworkX.
If you are not familiar with Python Virtual Environments, please see the tutorial here.
The Powershell commands are executed from within the repo's root folder, and assumes Python is installed in
C:\Python3.6.3. Linux and other shell commands are very similar.
C:\Python3.6.3\python.exe -m venv venv
.\venv\Scripts\activate
python -m pip install --upgrade pip
python -m pip install -r requirements.txthttps://www.udacity.com/course/data-structures-and-algorithms-nanodegree--nd256 https://review.udacity.com/#!/rubrics/2499/view https://www.python.org/ https://docs.python.org/3/tutorial/venv.html