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.
Instructions
To start the search:
- Implement a
while
loop that continues whilepath_queue
has at least one element. - Inside the loop, define
current_path
and assign it the next element inpath_queue
using.pop()
.
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:
- Define
current_node
and assign it to the last element ofcurrent_path
. - Output the message,
"Searching node with value: [current_node.value]"
.
Now let’s add some functionality to see if the search found goal_value
:
- Inside the
while
loop create anif
statement that checks ifvalue
incurrent_node
is equal togoal_value
. - Inside the
if
statement, returncurrent_path
.
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 "Home"
.
To fix this, change the second argument in the bfs()
call from "Z"
to "Home"
.
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 "Home"
.