To understand the functionality of search algorithms, we first need to understand basic searching concepts, such as the state, the ingredients of a search, and the nodes:
- State: The state is defined as the space where the search process takes place. It basically answers the question—what are we searching for? For example, in a navigation application, a state is a place. In our search application, a state is a file or folder.
- Ingredients of a search: There are three main ingredients in a search algorithm. These ingredients are as follows, using the example of a treasure hunt:
- Initial state: This answers the question—where do we begin our search? In our example, the initial state would be the location where we begin our treasure hunt.
- Successor function: This answers the question—how do we explore from the initial state? In our example, the successor function should return all of the paths from the location where we began our treasure hunt.
- Goal function: This answers the question—how will we know when we've found the solution? In our example, the goal function returns true if you've found the place marked as the treasure.
The search ingredients are illustrated in the following diagram:
Figure 15
- Node: A node is the basic unit of a tree. It may consist of data or links to other nodes.