Implementing Search Methods [50 pts]
You will implement several search methods in Python. Modify your answers in hw1coding.py. Function headers and some graph structure is provided in the file already.
Most of the analysis will be done on an undirected graph (Figure 1) represented by an adjacency list called self.graph. Recall that an adjacency list is a specific type of graph representation where there is a dictionary of nodes, and each entry in the dictionary has a list of the neighbors of that entry’s node.
Refer back to this document for specific instructions for each method. An autograder is available on Gradescope for you to test and submit your answers. When submitting to the autograder, do not change the function headers or provided code in hw1coding.py. The autograder will test edge cases and present a final score for you. If your return values are in the wrong format or you have a logical error, the autograder will not be helpful and going to office hours is recommended. You can submit to the Gradescope as many times as you like before the deadline at no penalty.
Pseudocode for BFS and A* search is included in the appendix at the end of this document.
Question 1 [16 pts]
Implement breadth-first search in the function bfs. This function accepts the start and end labels of the graph as input. It should return the list of expanded nodes as integers. For example, if we expanded nodes 0,2,1,3 in that order, bfs should return a python list [0,2,1,3] where the first number is the start node.
Question 2 [16 pts]
A long, long time ago in a galaxy not too far away, a legend was written about a single man that would return the power of Rock and Roll and Dance back to a tiny midwestern town while doing the most stereotypical 80’s things imaginable. That man was Kevin Bacon. Well, he PLAYED the character that would do this in Footloose, a popular movie from 1984. Launched into stardom, Bacon went on to star in many movies, leading him to say in an interview that he had “worked with everyone in Hollywood or someone who’s worked with them”. This is probably an overstatement. But there is some merit to what Bacon said, and it led to the definition of a Bacon number: the number of “links” or movies you are away from Kevin Bacon.
Use breadth-first search to find how many movies separate a given actor/actress from Mr. Bacon, thus calculating their Bacon Number. As input, take a graph where the nodes are movies and actors/actresses, and there is an edge between a movie and an actor/actress if that actor/actress was in that particular movie. An example graph is shown in Figure 2. For example, Robin Williams has a Bacon number of 2 because when we perform breadth-first search on the graph in Figure 2, we find the shortest path to Kevin Bacon looks like:
[‘Robin Williams’, ‘Aladdin (1992 Disney film)’, ‘Frank Welker’, ‘Balto (film)’, ‘Kevin Bacon’]
Figure 2
Note we want to find the path of nodes here, not the expanded nodes. This is made possible by using a Node object that keeps track of parent nodes, allowing you to backtrack at the end of the function. Modify your bfs method in bfsbacon to use the Node class to perform a breadth-first search on the graph self.bacon. Return the path from the starting actor/actress to Kevin Bacon. You will have to implement the Node class. The path should be a Python list with the first entry as the starting actor/actress and the final entry being the ending actor/actress (when calculating the Bacon number, the final actor will always be Kevin Bacon).
Question 3 [18 pts]
Use the Node class along with self.adjmatrix as edge weights and self.heuristic as heuristic values to perform A* search on self.graph. Return the path found by A* search in a similar format as the previous two questions. Here, self.adjmatrix is a 2D numpy array storing the adjacency matrix representing the graph. self.heuristic is also a 2D numpy array with the heuristic values for the nodes in the graph.
Appendix
Breadth-first search pseudocode:
A* search pseudocode:
