When the answer is not straight foreword, you must search for a solution. But because of the sheer magnitude of some situations, it is hard to incorporate into AI. Combination explosions cause the sheer magnitude of these problems. Combination explosions are when the possibilities for a solution explode (increase very rapidly) The math field of combinatorics study how these combination explosions occur. The commonly accepted theorem states that the number of ways N objects can be combined equals N! (N factorial). Because of the enormous number of possibilities, it is almost never a good idea to try every single possibility.

To clarify the pages on searching, the following definitions are useful:
• Node: A discrete point and possible goal
• Terminal Node: A node that ends a path
• Search Space: The set off all nodes
• Goal: The node that is the object of the search
• Heuristic: Information about the likelihood that any specific node is a better choice to try next, rather than another node
• Solution Path: A directed graph of the nodes visited that lead to the solution
(all definitions taken from Artificial Intelligence Using C by Herbert Schildt)

Most search spaces are in the form of a tree. A tree looks like an upside down tree that contains nodes. The following is an example of a tree:

Evaluating a search technique can sometimes be very difficult. But the most basic measuring techniques are:
1. Speed in which the solution is found
2. The quality of the solution
Both criterions are basically equally important, but in some case one might take priority over the other.
Now you are ready to continue to examine each search in-depth. Either click on a link below or from the menu at the top of the page to view more information about each search.
• Depth-First
• Breadth-First
• Hill-Climbing
• Least-Cost

Depth-First search

The Depth-First search explores each possible path to find the path’s conclusion or the goal. If the path does not contain the goal the search tries another path by backtracking. The following image shows the path the search takes when trying to find the goal ‘f’:
IMAGE_DFS
As you can see, the search almost had to check every node in order to find the answer, but it did find the right answer. This search is very reliable but sometimes can take a long time or even turn into an exhaustive search (a search that looks a every point until it reaches the goal). The Depth-First search can also be modified to go from the right to the left.
Advantages:
• Always finds the goal
Disadvantages:
• Often can be slow
• Can result in an exhaustive search
• Can get stuck in long paths that don’t the goal