Uninformed search

We learned in the Search lecture notes that search problems have the following components: an initial state, possible actions, a transition model that describes how actions change one state to another, a goal criteria, and a way of calculating the cost of a sequence of actions (a “path” cost). We do not use the path cost when executing uninformed search.

The transition model defines a state space, which can be represented as a directed graph (vertices are states, edges are actions).

For example, consider the 8-puzzle game, which requires that tokens are shifted around until a particular goal state is reached.


Each “state” is a configuration of the puzzle. Each state can be followed by at most four other states, resulting from moving a neighboring token left, right, up, or down into the space (thus shifting the space). If the space is on an edge or in a corner, fewer than four movements are possible.

Table of Contents

Generic search algorithm

All searches essentially follow the same algorithm:

1. create a list called "tocheck" of states to check
   - put the initial state in this list

2. loop:
   a. if the "tocheck" list is empty:
      - oh no! we have nothing left to check, and we never found a
        goal state! we'll have to quit with "no solution"

   b. otherwise, pull a state from the "tocheck" list, ensuring that
      we have not yet checked this state

      i. if this state is a goal state, we're done (return this state)

      ii. otherwise,
          - find the next states accessible from this state
          - put each next state in the "tocheck" list
          - repeat the loop

We see that whenever the search algorithm discovers a state is not a goal state, all accessible states are calculated and added to the “tocheck” list. This “tocheck” list typically grows quite rapidly. However, rarely do we check every state in the “tocheck” list. In fact, the different varieties of search differ almost only in how they process this “tocheck” list, as we will see.

Random search

A random search, while never practical as far as I know, is nevertheless interesting to consider as a worst case search. To program this search, modify step 2.b. so that a random “tocheck” state is chosen. Given enough time, the goal state should be found, but a random search will probably take more time (more states are checked) than any other method.

Breadth-first search

In breadth-first search (BFS), we want to check all states (which we’ll call “children states”) accessible from the previous state (the “parent state”) before we check states accessible from the children. So if some state is to be checked, say state X, and there are 15 children of state X, then we will check all of those 15 children before checking any of their children.

Breadth-first search appears to search horizontally before searching vertically.

To implement BFS, modify step 2.b. to pick out of the “tocheck” list the state that was added first. This means that earlier-discovered states are checked first. For example, the children of the initial state are checked before the their children, because the children of the initial state are discovered earlier. The “tocheck” list in BFS is essentially a queue.

Here is an example of BFS operating on the 8-puzzle:

Depth-first search

A trivial change to breadth-first search gives us depth-first search (DFS). For DFS, modify step 2.b. to pick out of the “tocheck” list the state that was added last. So in DFS, the “tocheck” list is essentially a stack. The purpose is to check the initial state’s first discovered child, and then that child’s first child, etc. before checking the initial state’s second child. DFS appears to search vertically before it searches horizontally.

Iterative-deepening depth-first search

Depending on the search problem, DFS may go off into “never-never-land,” seemingly never arriving at a goal state, while say, BFS, arrives at the solution rather quickly. We see this behavior in the 8-puzzle problem because DFS just keeps trying moves that are built off prior moves until it either repeats a state (somewhat unlikely; there are 9! = 362,880 states) or finds the goal. If the true goal is only five moves away from the initial state, then BFS will find this goal in less than 1024 checks while DFS may require, well, 362,880 checks.

To solve the problem of DFS going to “deep” into “never-never-land,” we can put a limit on the depth of DFS. Step 2.b.ii. is modified so that only states that have depth less than some constant are added to the “tocheck” list. The depth is calculated as the number of actions that have been applied to the initial state.

Because it is often difficult to know what the correct depth limit is, the iterative-deepening depth-first search (IDDFS if you like) first tries DFS with depth limit 1; if no goal state is found, DFS is run again with depth limit 2; and so on, until the goal state is found.

Breadth-first versus depth-first search

Breadth-first search is a good choice when you want to evaluate every possible choice before moving forward. BFS ensures that the shortest path to the goal will be found (shortest in terms of number of moves or number of “hops”), because no path is left unchecked. However, BFS suffers when, at each state, there is an enormous number of choices to consider.

On the other hand, depth-first search seems a bit block-headed and just pushes forward whenever it has a next possible move.

If we place a robot in a maze, a BFS robot would look around every nearby corner before choosing to move forward. A DFS robot would move forward as many times as it could (in any direction) before backing up even once. If the maze can be solved by many possible paths, perhaps the DFS robot is better.

But DFS is bad for the 8-puzzle game, because it is much more likely that DFS will get further and further from the goal by making more and more moves. BFS, on the other hand, is probably good for the 8-puzzle game because there are at most only four possible moves and the goal is often only a few moves away.

Also, it is important to note that if a robot is actually making these moves, in the physical world (like driving a car), BFS is a bad idea. BFS involves a lot of backtracking, so the robot would have to turn around quite often. DFS, on the other hand, typically minimizes backtracking.

CSE 630 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.