CS50 AI -Degrees. Logical problem

Question

I kind of finished the CS50 AI degree problem but I have an issue with the logical part of it. Instead of returning the shortest path, my code has unintentionally been designed to return the whole path, even when following certain nodes leads to programmatical dead ends. I'll attach it below to show what I'm talking about. This is the depth first search method, and I can clearly see and understand what its doing, which is definitely not a short path, especially when given large volumes of data. Anyone, please help!

stack = StackFrontier()
stack.add(Node(state=source, parent=None, action=None))
neighbs = neighbors_for_person(target)
tfilms = set()
for neighbm, _ in neighbs:
    tfilms.add(Node(state=target, parent=None, action=neighbm))
explored = set()
route = []
while True:
    try:
        if stack.contains_state(None):
            return None
        last = stack.remove()
        if last not in explored:
            explored.add(last)
            neighs = neighbors_for_person(last.state)
        explored.add(last)
        neighs = neighbors_for_person(last.state)
        for newmovie, newperson in neighs:
            node_next = Node(state=newperson, parent=last.state, action=newmovie)
            route.append((node_next.action, node_next.state))
            if node_next.state not in explored and not stack.contains_state(node_next.state):
                stack.add(node_next)
            elif node_next.state == target:
                return route
            explored.add(node_next)
            nxxt = neighbors_for_person(node_next.state)
            for nwmvie, nwprsn in nxxt:
                tnxxt = Node(state=nwprsn, parent=node_next.state, action=nwmvie)
                if tnxxt.state not in explored and not stack.contains_state(tnxxt.state):
                    stack.add(tnxxt)
        else:
            raise NotImplementedError
    except NotImplementedError:
        return None

\\

Answer 1

Why are you using DFS? To get the shortest path, you need to use breadth first search (BFS). Remember this from the lecture? (so use QueueFrontier, not StackFrontier)

This is a lot of code to debug. Have you checked any of the logic? I ask because there are a lot of errors. Initial observations:

• After you create the source node and add to the frontier, you get the neighbors of the target and add them to tfilms. What is the purpose of tfilms? I don't think you use this value or need this code.
• When you create new nodes, you are using the wrong value for parent= . You use the state (person) and it needs to be the parent Node (e.g., previous node).
• Next, you are creating your path (route ) by adding nodes while you search. You don't create the path until you have found the target, then work backward using each node's parent to build the path.
• I had a hard time following your search logic. A search is done by finding neighbors to a node and checking for the target. If it's the target, your search is done. If not, add the node to the frontier and continue popping nodes, checking for target then looking for neighbors. You have 2 calls to neighbors_for_person() inside your search loop. Not sure what you are trying to do.
• At some point you need to remove logic that gets you to NotImplementedError. You never want to hit that.