The heart of the algorithm is the loop that contains the search process. The first half of this process is:
Pop the next path list off the frontier Get the frontier node from the path list Check if the node value matches the goal value If there is a match, return the path to the current node
The first iteration of this loop has a frontier with one path: a list with the root node. The node will be retrieved and have its value checked against the goal value.
To start the search:
- Implement a
whileloop that continues while
path_queuehas at least one element.
- Inside the loop, define
current_pathand assign it the next element in
Be sure this step removes an element from
path_queue or else the code will enter an infinite loop.
Now let’s retrieve the frontier node to search:
current_nodeand assign it to the last element of
- Output the message,
"Searching node with value: [current_node.value]".
Now let’s add some functionality to see if the search found
- Inside the
whileloop create an
ifstatement that checks if
current_nodeis equal to
- Inside the
When you go to main.py and run the code, the output will still be
No paths found!. Why is that?
(We’ll fix this in the next step.)
In main.py, the argument being passed to the
goal_value parameter in the
bfs() call is currently
"Z". If you look at the tree values printed to the console you’ll see that there is no
"Z". Currently, the only node added to the frontier queue is the root node whose value is
To fix this, change the second argument in the
bfs() call from
If you run the code again, you should now see a returned path to the goal node printed to the console. The path is just