Imagine yourself in Romania, without a map, trying to get to Budapest by car. You have a distance table between cities in the country and you have a plane. How do you find a good route to your destination that will get you to the capital before your flight leaves?

Search

It is an accepted fact in Computer Science that most problems eventually come down to a search problem in some abstract or concrete domain. A search problem is usually expressed as a collection of unexplored nodes¹, a set of operators that can be applied to a node to get a list of successor nodes and a goal test that can examine a node to see if it is an acceptable solution.

Many strategies for searching a solution space exist but most can be divided into three broad categories:

1. Uninformed
2. Informed
3. Local

Uninformed search strategies

The category of uninformed search strategies contains two basic types of search; breadth-first search and depth-first search. In a breadth-first search, all the nodes at one level of the tree are expanded first. This leads to a space/time complexity of b^d where b is the average branching factor⁴ and d is the depth of the search from the start node. For all but the smallest searches, this is an unfeasible complexity leading to storage requirements of terabytes and search times of hundreds of years.

Most of the problem with a breadth-first search comes from the space complexity. The space requirements go into the realm of the unfeasible far faster than the time requirements. The space complexity results from the need to hold all the nodes at each level of the search tree in memory at once. Depth-first search eliminates this need by exploring a path fully before moving on to the next. If a path proves fruitless, it backtracks up a level and explores another path.