Lab 3: Alternative Searching Algorithms

This lab will give you experience with breadth-first search and iterative deepening. You will use both algorithms to search a state space. The lab builds on lab 2; if you do not have a working solution to lab 2, talk to your instructor to help you debug your current solution. Assuming you have a start, we will give you considerable help on that debugging,

Note there are two new files for this lab; you will need to download them:

• dungeon.py: this file is the same as in lab 2.
• test_dungeons_two.py: a version of test_dungeons that has been extended to include the algorithm to use. Warning: using iterative deepening on test 7 may take many hours, depending on various details about your solution!
• lab3_main.py: a revised version of lab2_main.py designed for submitting this lab.

Modify your lab 2 solution by adding the following two methods to Rat:

    bfs_directions_to(self, target_location: Room) -> List[str]
    """Return the list of rooms names from the rat's current location to
    the target location. Uses breadth-first search."""

    bfs_path_to(self, target_location: Room) -> List[Room]
    """Returns the list of rooms from the start location to the
    target location. Uses breadth-first search to find the path."""

In theory it would be possible to write a method that both path_to and bfs_path_to call to avoid repeating much code. Do not attempt this; it will result in very complex logic. Instead, copy the code for path_to and change it as follows:

• Store the list of candidate rooms using Queue from the queue package. put adds to the end of the queue, get retrieves the front.
• As for depth-first search, the frontier will consist of paths from the start to a particular node. Thus you will store paths on the queue. You will likely need to copy the path when you add new paths at the end of the queue, one for each neighbor of the given node.
• Ensure the loop adding rooms to the end of the candidate queue adds them in the right order. This typically means not reversing lists that you had to reverse for DFS.
• Ensure you are tracking the visited rooms in a set so you do not visit a room twice. This is not critical when there is a path to the target room, but it is critical when there is no path.

In addition, add the following two methods to Rat:

    id_directions_to(self, target_location: Room) -> List[str]
    """Return the list of rooms names from the rat's current location to
    the target location. Uses iterative deepening."""

    id_path_to(self, target_location: Room) -> List[Room]
    """Returns the list of rooms from the start location to the
    target location. Uses iterative deepening."""

Again, copy the code from path_to and modify it to support iterative deepening. Some hints:

• You will probably want to write a private method that uses depth-first-search to search to a given maximum depth.
• You could write your private DFS-search method so it’s recursive, taking a counter of the number of levels left to process. However, a simpler solution is to not push any paths onto the DFS stack if those paths traverse more than the maximum depth number of neighbors. For example, a path [room_a, room_b] represents a search of depth one, while a path [room_a, room_b, room_c] represents a search of depth 2. In theory you might not have to track visited rooms since the maximum depth would preclude loops, but tracking visited rooms will speed up your algorithm significantly. In any case, it is required in order to match the expected output.
• Write id_path_to to call your private DFS function, incrementing the depth by one until either you have found a solution or you have searched a depth that matches the number of rooms in the dungeon.

Note dungeon.py includes a size method giving the number of rooms in the dungeon.

Additional Notes

• As before, you can add additional protected or private methods and attributes.
• test_dungeons_two.py contains test code used by esubmit to ensure your solution works. Run those on your own machine before trying to use esubmit.
• Strongly consider using type hints to help find errors.
• If your iterative deepening solution finds solutions much faster than shown in the sample output, it is likely that you are not clearing out all data at the start of each pass. In particular, the set of visited rooms needs to be cleared so that each pass starts with fresh data.

Submission

Submit your solution using esubmit as lab3alt. You will submit at least two files, your revised version of rat.py and the unchanged version of lab3_main.py. The other two files, dungeon.py and test_dungeons_two.py, are already provided by esubmit and should not be submitted.