This is the simplest form of uninformed search.
In this case, operators are applied to the start node to expand it and generate all its successors. If we call the start node level 0, then these child nodes are at level 1. Next, each child node is in turn expanded in some arbitrary order, creating the children of each at level 2. This process continues until a goal node appears as one of the children.
The process pro cedes level by level. All nodes at each level are expanded until a goal node is reached.
The breadth first search for this 8-puzzle,
| Start | Goal | ||||||||||||||||||
|
|
produces the following part of the state graph,
The solution is 5 moves deep. The search for the solution pro cedes level by level. Every node at each level is expanded and must be stored. Breadth first search can be very memory intensive. On the upside, it guarantees the shortest solution.
The above diagram is a tree. not a graph. What has been left out is the possibility of cycles in a graph. In human terms a cycle is often described as "going around in circles".
If you were programming the 8-puzzle you would need to take steps to avoid cycles. The simplest cycle is just reversing the previous move. But, you might also fall into longer cycles and the program could loop forever. Note that in a game such as Tic Tac Toe, where no move can be reversed (taken back) cycles are not possible.
