Searching refers to finding a sequence of various actions to find the solution to the problem in such a way that this sequence of actions solves the problem optimally by some criteria. The two major types of searching are Informed and Uninformed. Informed search uses problem definition as well as additional information about the guidance related to the problem’s solution. On the other hand uninformed search as the name suggests no information on the problem’s solution is provided only a specification of the problem is given.
Informed Search
- Informed search in Artificial Intelligence is an efficient and quick search strategy where information about the final state is provided along with problem definition.
- This information is in the form of a function called heuristic.
- Heuristic function estimates the approximate closeness to the goal state for all the available paths and helps the algorithm choose the shortest or closest among all.
- It uses additional information to guide the search process, which ensures efficient problem-solving. Information can be in the form of estimation of the cost, heuristics, or other relevant data that can be used to prioritize the selection of states, expand, and explore.
- Examples of Informed Search are Greedy, A* Search, Best-First Search, etc.
Key Features
Key Features of Informed search are:
- Heuristic Function:Heuristic function provides an estimation of the cost or distance from the current state to the destination state which helps the algorithm in prioritizing nodes that are more likely to lead to the goal. It is domain-specific which implies it is tailored for the particular problem.
- More Efficient:Informed search algorithms have prior information and can estimate costs. Thus, these are designed to be more efficient by avoiding the exploration of unlikely paths and focusing more on promising ones. The efficiency results in quicker and more effective problem-solving, especially in large search spaces.
- Goad-directed:The Final destination or goal is defined and these move forward in the same direction to find a solution to the specific problem. This algorithm refines the search space and moves closer to the goal with each step.
- Cost-based:Before following a path cost is estimated for the node or entire path and then the decision is made. In this way, it chose a path with minimum cost to reach the goal.
- Prioritization:The nodes are given priorities based on additional information available such that nodes that cost the least must be expanded first leading to efficient problem-solving. Prioritization ensures that the algorithm is more likely to lead to the goal using more promising nodes, leading to efficient exploration.
- Optimality:If the heuristics are admissible i.e. estimating the lower bound of the cost and not overestimating actual cost then the informed search algorithm may succeed in providing an optimal solution.
Uninformed Search
- Unlike Informed search Uninformed search algorithms don’t contain any additional information regarding the goal state. It only contains the information provided during the definition of the problem.
- These algorithms are capable of only differentiation between goal state and non-goal state. It is not possible to estimate the closeness of any state to the goal state and thus, it is known as blind search.
- Uninformed search algorithms in AI are the ones that don’t use additional information to guide the search process of the goal but they perform a systematic search.
- Examples of uninformed search are Breadth-first search, Depth-first search, Depth limited search, etc. These can be used for small problems or as a starting point in finding solutions for complex problems.
- This algorithm may not be efficient and lead to an exponential increase in the number of explored states for complex or large problems. There is no guarantee that it will find the optimal solution as they are not cost-based or hold any relevant information about the goal.
Key Features
- Systematic Exploration:Uninformed search algorithms explore systematically in the search space either by exploring i.e. expanding the children nodes on the same breath using BFS or by exploring the nodes as deep as possible by DFS algo.
- No heuristics:Uninformed search algorithms don’t use any additional information such as cost or heuristics to guide the search process.
- Blind Search:These follow the nodes blindly without considering the cost of reaching the final node. There is no consideration of cost or likelihood of finding the solution in the specified path.
- Simple to implement:As there is no information to be processed these algorithms are usually simple to implement and understand and are perfect for initial operations.
- Inefficient in complex problems:Uninformed search algorithms are not very efficient with complex problems or large search spaces. The exponential increase in the search states is often referred to as the “exponential explosion” or “combinatorial explosion.”
Difference between Informed and Uninformed Search
| Feature | Informed Search | Uninformed Search |
|---|---|---|
| Goal | Faster convergence towards the goal by using domain-specific knowledge (heuristics). | Slower convergence as it explores the search space without any specific guidance. |
| Node Selection | Prioritizes nodes based on heuristic estimates of their desirability. | Expands nodes without considering their potential to reach the goal more quickly. |
| Examples | A* Search, Greedy Best-First Search, Hill Climbing, Best-First Minimax | Breadth-First Search, Depth-First Search, Iterative Deepening, Bidirectional Search |
| Completeness | Depends on the heuristic; may not find a solution if an inappropriate heuristic is used. | Completeness depends on the algorithm; BFS is complete if the branching factor is finite. DFS is not complete for infinite state spaces. |
| Optimality | A* is optimal if the heuristic is admissible and consistent. | BFS is optimal if the path cost is uniform and non-negative. DFS is not optimal. |
| Memory Requirements | Often requires more memory to store states and their associated heuristics. | Typically requires less memory compared to informed search. |
| Exploration Strategy | Balances between path cost and heuristic estimate to make informed decisions. | Explores based on fixed strategies (e.g., FIFO queue for BFS, LIFO stack for DFS). |
| Convergence Rate | Generally converges faster due to targeted exploration. | Converges more slowly, especially in larger search spaces. |
| Knowledge Dependency | Relies on domain-specific knowledge for heuristics. | Does not require domain-specific knowledge. |
| Problem Complexity | Well-suited for complex problems with large state spaces. | Better for simpler problems or when no domain knowledge is available. |
FAQs
Q. In what scenarios is uninformed search most suitable?
A. Uninformed search is most suitable for simpler problems where domain-specific knowledge or heuristics are not available or not useful.
Q. What is a heuristic function in informed search?
A. Heuristic function is a domain-specific cost estimation from the start state to the goal state. In informed search algorithms, heuristic information is used to prioritize nodes for exploration.
Q. What makes informed search more efficient than uninformed search?
A. Informed search in AI can intelligently prioritize paths that are likely to lead to the goal node and avoid irrelevant branches potentially leading to the goal.
Explore Scaler Topics Data Structures Tutorial and enhance your DSA skills with Reading Tracks and Challenges.
Conclusion
- Informed search uses heuristic search, cost estimation, and domain-specific knowledge to guide the search space. A*, Hill Climbing, etc. are examples.
- Informed search is effective for complex problems or large search spaces. However, the quality of the heuristic plays a crucial role, and if it is not designed properly finding a solution can be challenging.
- Uninformed search in AI also called blind search doesn’t use domain-specific information but rather uses a systematic approach to find the goal.
- It is suitable for finding the starting state or for simpler problems. BFS and DFS are examples.
