1

I am working on Project 0 for the CS50 AI Course and after finishing my function for shortest_path, I am getting an infinite loop(I added a counter that increments with print statements to be able to see the infinite loop in the output). I made sure that I only add neighbors to the frontier if they are not already in the frontier and have not been explored already, so I am not sure where this infinite loop is occurring from. Any help debugging would be appreciated. Here is the code:

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.
    """
    path = []

    # Keep track of number of states explored
    num_explored = 0

    # Initialize frontier to just the starting position
    start = Node(state=source, parent=None, action=None)
    frontier = QueueFrontier()
    frontier.add(start)

    # Initialize an empty explored set
    explored = set()

    # Keep looping until solution found
    counter = 0
    while True:
        print(counter)
        counter += counter + 1
        # If nothing left in frontier, then no path
        if frontier.empty():
                return None

        # Choose a node from the frontier
        node = frontier.remove()
        num_explored += 1

        # If node is the goal, then we have a solution
        if node.state == target:
            actions = []
            cells = []
            path=[]
            while node.parent is not None:
                #actions.append(node.action)
                #cells.append(node.state)
                path.append(node.action,node.state)
                node = node.parent
            #actions.reverse()
            #cells.reverse()
            path.reverse()
            #solution = (actions, cells)
            return path

        # Mark node as explored
        explored.add(node.state)

        # Add neighbors to frontier
        for action, state in neighbors_for_person(node.state):
            if not frontier.contains_state(state) and state not in explored:
                child = Node(state=state, parent=node, action=action)
                frontier.add(child)

Thanks

0

You must log in to answer this question.

Browse other questions tagged .