Part $1$: Route Planning

In Part $1,$ you will compare the performance of the three uninformed search algorithms on a single instance of the Route Planning environment.

$1.$A $-$ Create Environment

Create an instance of the RoutePlanning class using the following parameters: num$\_$sites$=800,$ random$\_$state$=1,$ start$=626.$ Use the display$()$ method to display the initial state of the environment.

$1.$B $-$ Apply Search Algorithms

Apply the depth$-$first search, breadth$-$first search, and uniform$-$cost search algorithms to the environment created in $1.$A$.$ Set a time limit of $2$ minutes for each algorithm. Store the solutions and the resulting log information into variables. Leave display$\_$results with its default value of True.

$1.$C $-$ Visualizing Solutions

Complete the code in the cell below by placing the solutions find in $1.$B into the solns list. The solutions should be listed in an order that is consistent with the strings contained in the algs list. After populating the solns list with your solutions, run the cell to display the solutions found by the three algorithms.

$1.$D $-$ Comparing Frontier Sizes

Complete the code in the cell below by placing the log objects find in $1.$B into the logs list. The logs should be listed in an order that is consistent with the strings contained in the algs list. After populating the logs list, run the cell to produce a plot that shows how the frontier size changed over time for each of the three algorithms.

You should see that the frontier for depth$-$first search was significantly larger than the frontier for the other two algorithms, indicating that depth$-$first search requires substantially more memory than that other algorithms when applied to the route planning environment.