Step 2. Breadth-first search

Video

World

Breadth-first se...
Breadth-first search for "Six Degrees of Kevin Bacon".

Notes

• The program uses some movie data to show how an algorithm would search through a search tree, looking for a path to the goal (here, a path to Kevin Bacon).
• It uses this movie data (JSON format). Note Kevin Bacon is in the first 3 movies but not in the last 2.
• View console to see what is happening.

Credits

• This is a modified port of P2_six_degrees_kevin_bacon from AI course by Daniel Shiffman.
• See his videos parts one and two.

Look at the code

• As with all Worlds on Ancient Brain, you can see the source code and clone it and edit it.
• In the code you can see that the search starts with the start node, searches all neighbours, before those 2 steps away, before those 3 steps away, and so on. When it exits with goal node, it will have found a (joint) shortest route.
• The FIFO queue is done with a JavaScript array and push and shift.

Exercise

1. Clone the World and Edit the code.
2. Fix a bug: The search adds new nodes to the queue if they are not searched. But they might be on the queue already, just not searched. A node can be added multiple times to the queue. Search for "Michael Cyril Creighton" to see this. Edit the code and fix the bug.

3. Another exercise: It would be faster if it checked for the goal node when adding new nodes to the queue. Do not add goal to queue. Just exit.
4. Highlight the movie titles different to the actor names.
5. What if no path found?