Harvard Online CS50 - Degrees

Question

Just started CS50 Intro to AI and I believe I implemented the BFS queue search algorithm properly to find the shortest path between two actors. I don't know what could possible be the issue but I would appreciate it if someone could shine light on what I may be doing wrong. Also, no errors come up so that's actually making it a little more irritating to understand.

def shortest_path(source, target):
    """
    Returns the shortest list of (movie_id, person_id) pairs
    that connect the source to the target.

    If no possible path, returns None.
    """
    #initialize the frontier to be a queue frontier because BFS is a queue and will find
    #the shortest path
    frontier = QueueFrontier()
    #first node is added to the frontier
    frontier.add(Node(source, None, None))
    #Initialize the nodes explored as a empty set
    nodesExplored = set()
    if source == target:
        raise Exception("Can't choose the same actor twice!")
    # Keep looping until solution found
    while True:
        #if there are no solutions then just return None
        if frontier.empty():
            return None
        # Choose a node from the frontier and remove it
        node = frontier.remove()
        # If node is the target, then we have a reached our goal state, our solution
        if node.state == target:
            #initalize an array of solutions
            solutions = []
            # continue to search if node has a parent
            while node.parent is not None:
                solutions.append(node.action, node.state)
                node = node.parent
            solutions.reverse()
            return solutions
        # Mark node as explored
        nodesExplored.add(node.state)
        # Add neighbors to frontier
        for movie_id, person_id in neighbors_for_person(node.state):
            if not frontier.contains_state(person_id) and person_id not in nodesExplored:
                child = Node(person_id, node, movie_id)
                frontier.add(child)

This is what should happen:

$ python degrees.py large Loading data... Data loaded. Name: Emma Watson Name: Jennifer Lawrence 3 degrees of separation. 1: Emma Watson and Brendan Gleeson starred in Harry Potter and the Order of the Phoenix 2: Brendan Gleeson and Michael Fassbender starred in Trespass Against Us 3: Michael Fassbender and Jennifer Lawrence starred in X-Men: First Class

but nothing happens after I input the second actor. It just stays blank not returning anything not even an error, so this what I get:

$ python degrees.py large Loading data... Data loaded. Name: Emma Watson Name: Jennifer Lawrence

Answer 1

my guess ist that your check for frontier.contains_state(person_id) is too much, because you prevent adding nodes with the same person in a different movie from being added to the frontier and cut off a possible path to a solution

This seems to work:

def shortest_path(source, target):
    frontier = QueueFrontier()
    frontier.add(Node(source, None, None))
    nodesExplored = set()
    if source == target:
        raise Exception("Can't choose the same actor twice!")
    while True:
        if frontier.empty():
            return None
        node = frontier.remove()
        if node.state == target:
            solutions = []
            while node.parent is not None:
                solutions.append((node.action, node.state))
                node = node.parent
            solutions.reverse()
            return solutions
        nodesExplored.add(node.state)
        for movie_id, person_id in neighbors_for_person(node.state):
            if not (person_id in nodesExplored):
                child = Node(person_id, node, movie_id)
                frontier.add(child)

however, the notes to the course also say: "if you detect a goal node, no need to add it to the frontier, you can simply return the solution immediately" I think your code can still be improved by moving the goal check... and good luck with the course, I also just started the cs50 ;-)