Search is the foundation of many techniques in the field of Artificial Intelligence. Examples of the application of search include planning, (board) game playing and automated deduction. Any problem that can be represented by discrete states and transitions between such states can be formulated as a search problem. For the purpose of this write up, these discrete states will be called search nodes. Solving a search problem involves finding a path of transitions from one search node to another.
A typical search problem is composed of a root node, a goal node, a successor function and an open list. The goal node is the state you want to reach through search. The root node is where you start your search from. The successor function defines which states are reachable from a given search node. The open list stores nodes which have yet to be examined. Some search problems also used a closed list to store nodes which have been previously seen by the search process (to prevent the search process from entering into loops).
To solve a search problem, the following algorithm can be used. First the root node is placed on the open list. Then, whilst the open list still contains nodes, the node at the head of the list is removed. If this node is equal to the goal node, then the node is returned (along with the path of transitions if this is necessary to solve the problem). If the node is not equal to the goal node, then the successor function is applied to it to generate any successor nodes that are reachable from it. These nodes are placed on the open list and, if necessary, the previously selected node is placed on the closed list. Then the head of the open list is selected again and the process continues.
Many different variation on this theme have been developed. Most variations sort the open list to alter the way in which the search process encounters new nodes. See best-first search, depth-first search, and A* for some common examples.