Struggling with logic on cs50 AI search

Question

I completed CS50 intro to computer science a while back and I am starting the AI course now. I watched the lecture, and I understood how the logic worked for the maze and such, but I'm struggling on what to do for the search.

I have it working for when two actors share a movie, so it's 1 degree of separation, which is simple to do. Now, I thought about removing anyone who doesn't share a movie with the source from the frontier, but the problem with that is it limits people that would connect the source and target.

Another option would be to find the neighbors of the source, and then the neighbors for all of them, and so on until you reach the target, but I can tell that wouldn't be efficient. You could maybe search the entire list of actors, and remove people who didn't work with the target, and then work backwards from that list until you find the source.

I just need a bit of guidance with what the logic could look like, I've been thinking about it for a while and I'm just not sure. Thanks for any help!

Answer 1

You could use the standard breadth-first search algorithm. That is, you create a queue-frontier to keep track of the actors (nodes) that you should explore. The first actor (node) in the frontier should be the "source" (assuming you want to find the distance from the "source" to the "target"). The main logic in your program is to get a node from the frontier and to find all the neighbors. Check for the target. Add all the neighbors in the frontier for future exploration,etc. The advantage of the breadth-first search is that it will assure that you always find the shortest path if there is one. This is because you always explore all the neighbors at one level before going deeper. Regarding the implementation you should use the utility, i.e Node,QueueFrontier.