Breadth first

The method given in Section 2.2.1 specifies ${Q}$ as a First-In First-Out (FIFO) queue, which selects states using the first-come, first-serve principle. This causes the search frontier to grow uniformly and is therefore referred to as breadth-first search. All plans that have $k$ steps are exhausted before plans with $k+1$ steps are investigated. Therefore, breadth first guarantees that the first solution found will use the smallest number of steps. On detection that a state has been revisited, there is no work to do in line 12. Since the search progresses in a series of wavefronts, breadth-first search is systematic. In fact, it even remains systematic if it does not keep track of repeated states (however, it will waste time considering irrelevant cycles).

The asymptotic running time of breadth-first search is $O(\vert V\vert+\vert E\vert)$, in which $\vert V\vert$ and $\vert E\vert$ are the numbers of vertices and edges, respectively, in the state transition graph (recall, however, that the graph is usually not the input; for example, the input may be the rules of the Rubik's cube). This assumes that all basic operations, such as determining whether a state has been visited, are performed in constant time. In practice, these operations will typically require more time and must be counted as part of the algorithm's complexity. The running time can be expressed in terms of the other representations. Recall that $\vert V\vert = \vert X\vert$ is the number of states. If the same actions $U$ are available from every state, then $\vert E\vert = \vert U\vert \vert X\vert$. If the action sets $U(x_1)$ and $U(x_2)$ are pairwise disjoint for any $x_1,x_2 \in X$, then $\vert E\vert = \vert U\vert$.