July 13, 2022
What is a search algorithm?
- Search algorithms are algorithms that help in solving search problems.
- A search problem consists of a search space, start state, and goal state.
- Search algorithms help the AI agents to attain the goal state through the assessment of scenarios and alternatives.
- The algorithms provide search solutions through a sequence of actions that transform the initial state to the goal state.
- Without these algorithms, AI machines and applications cannot implement search functions and find viable solutions.
Importance of search algorithms
The following points explain how and why the search algorithms are important in artificial intelligence:
- Solving problems: Search algorithms enhance the solving of problems in artificial intelligence through logical search mechanisms such as problem definition, actions, and search space.
- Search programming: Many AI tasks can be programmed in terms of search, which enhances the formulation of the solution to a given problem.
- Goal-based agents: Search algorithms enhance the effective operation of goal-based agents. These agents solve problems by searching for the most ideal series of actions that can provide the best solution to a problem.
- Support production systems: Search algorithms support the operation of production systems in AI. These are systems that support AI applications through the use of rules and the procedures for implementing them. Production systems use search algorithms to search for the sequence of rules that can result in the desired action.
- Neural network systems: These algorithms are also important in neural network systems. These are computing systems that consist of interconnected nodes, a hidden layer, an input layer, and an output layer. Neural networks are used to perform various tasks in artificial intelligence. Search algorithms enhance the searching of connection weights that will lead to the desired input-output mapping.
Properties of search algorithms
Search algorithms have the following main properties:
- Completeness: A search algorithm can be said to be complete if it provides a solution for a given input when there exists at least one solution for this input.
- Optimality: Search algorithms are also characterized by optimal solutions. These are the best solutions given by the search algorithms at the lowest path cost.
- Time Complexity: These algorithms have a maximum time needed to accomplish a task or provide a solution. The time taken is usually based on the complexity of the task.
- Space Complexity: They have a maximum memory or storage space needed when conducting a search operation. This memory is also based on the complexity of the task.
State Spaces Search
State: AI problem can be represented as a well formed set of possible states. State can be Initial State i.e. starting point, Goal State i.e. destination point and various other possible states between them which are formed by applying certain set of rules.
Space: In an AI problem the exhaustive set of all possible states is called space.
Search: In simple words search is a technique which takes the initial state to goal state by applying certain set of valid rules while moving through space of all possible states.
So we can say that to do a search process we need the following.
- Initial State
- Set of valid Rules
- Goal State
Types of search algorithms
Since the state spaces are very large in general, we employ search algorithms to navigate through the state-space effectively and efficiently. A search algorithm defines how to find the path (solution) from the initial state to the goal state. Different algorithms define different methods to move from the current state (node) to the next state (node). Some algorithms provide just the systematic ways to explore the state space while others tell how to explore effectively and efficiently.
The search algorithms are of two types as uninformed and informed search algorithms. Informed search algorithms provide just a systematic way to explore the state space and no additional information are provided to support the search process. Breadth-first search, Uniform search, Depth-first search, Depth limited search, Iterative deepening search, and Bi-direction search are the 06 main uninformed search algorithms.
On the other hand, informed search algorithms such as Greedy search and A* search algorithms are based on additional information which makes the searching procedure both systematic and effective.
