Overview

Uninformed searches,
Traverse through the tree without,
Specific knowledge

Uninformed searches generate the search tree without specific information relating to the task.

Breadth-First

In a breadth-first search, the tree is evaluated by examining the outcome of every branch of a single node. Only once all branches have been explored is the next node examined. Because of this, the search traverses each level of the tree completely before moving to a deeper level.

Breadth-first searches are fairly easy to implement and are also considered complete, as (in a tree with finite breadth) the search will eventually reach its goal since each level of the tree has to be generated before the next level is explored. This prevents the search from becoming trapped in a single deep branch that does not lead to the goal. However, the memory requirements for a breadth-first search are high as each level of the tree has to be saved as it is generated. It can also take a large amount of time if the goal is far from the root of the tree.

Depth-First

Conversely, a depth-first search starts at one node and explores to the end of that branch. When the search cannot go any deeper, it examines previously explored nodes to find any unexplored branches that connect to them. In this way, the search moves back up the tree, completely traversing any nodes it finds on the way.

Depth-First searches have much smaller memory requirements than breadth-first, as only the path to the current node needs to be stored. The search may also be much faster than a breadth-first search if the goal is found without many traversals needed. Despite this, the biggest problem with a depth-first search is the potential for it to become trapped in areas of the tree. An infinite tree can be generated (even with finite data) and because this search does not generate each level of the tree before moving deeper, it can constantly explore deeper into a branch that will never hold the goal.

Because of this, depth-first searches are not complete, and may never find a solution. Unlike breadth-first, it is also not guaranteed to be a minimal solution.

Depth-Limited

The most obvious solution to the problem of becoming trapped in infinitely deep branches is to limit the depth of the search. This will end the search at a certain depth, forcing it to explore the rest of the tree. The main limitation with this approach is that it is usually very difficult to predict the depth needed in order to find the goal. It is therefore easy to make the goal impossible to find, by setting the maximum depth too low, preventing the search from ever reaching it.

Iterative-Deepening

Iterative deepening is an improved implementation of the depth-limited version of this search. In this method, a depth-limited search is performed until the whole tree has been generated. At this point, if the goal has not been found, the maximum depth is increased and the search continues to this new depth. This will continue until the goal is found.

Because each stage of the search is still depth-limited, the whole tree is generated up to the maximum depth. This ensures that a solution will eventually be found. This search still uses relatively little memory and can still be considerably fast while not running the risk of infinite searching.

Bi-Directional

References

[1] G. N. Yannakakis and J. Togelius, "Artificial Intelligence and Games". Springer, 2018.
[2] Author unknown, "Uninformed Search". Available: http://cs.lmu.edu/~ray/notes/usearch/ [Accessed: 06-Feb-2019]
[4] Robin, "Breadth First Search", December 16, 2009. Available: http://intelligence.worldofcomputing.net/ai-search/breadth-first-search.html#.XFrVtFz7SCo [Accessed: 06-Feb-2019]