Informed search algorithms in AI are search algorithms that use additional information (heuristics) to guide the search process towards a goal more efficiently, compared to uninformed search algorithms, which do not have such information. The key idea is to utilize some knowledge about the problem domain to make decisions on which path to explore next, potentially reducing the number of states that need to be explored.
Here are some common informed search algorithms:
1. Greedy Best-First Search
- How it works: It selects the node that appears to be closest to the goal based on a heuristic function, typically denoted as
h(n)(estimated cost from the current node to the goal). - Heuristic: The heuristic
h(n)is used to evaluate nodes. It doesn’t consider the cost to reach the node but rather how promising it is to lead to the goal. - Pros: It can find a solution quickly if the heuristic is good.
- Cons: It is not guaranteed to find the optimal solution and can get stuck in local minima.
2. A Search*
- How it works: A* combines both the cost to reach the current node (
g(n), the path cost) and the estimated cost to the goal (h(n)). - Formula: It evaluates nodes based on the function
f(n) = g(n) + h(n), where:g(n)is the cost to reach the current node from the start.h(n)is the heuristic estimated cost to reach the goal from the current node.
- Pros: It is complete (guaranteed to find a solution if one exists) and optimal if the heuristic is admissible (never overestimates the true cost).
- Cons: Can be computationally expensive, especially if the search space is large.
3. Iterative Deepening A (IDA)**
- How it works: It is similar to A*, but it combines the depth-first search approach with A*’s evaluation function. Instead of keeping all nodes in memory, it limits the search depth by iteratively increasing a threshold based on the cost function
f(n). - Pros: It reduces memory usage compared to A* by using depth-first search.
- Cons: The time complexity can still be high.
4. Beam Search
- How it works: It is a heuristic search algorithm that explores a graph by expanding the most promising nodes within a limited beam width. Rather than exploring all possible nodes, beam search only keeps a fixed number of the most promising nodes at each level.
- Pros: It reduces the number of nodes that need to be explored, making it more efficient than exhaustive search.
- Cons: It does not guarantee finding the optimal solution and may miss better solutions outside of the beam width.
Heuristics in Informed Search
- A heuristic is a function that provides an estimate of how close a state is to the goal. A good heuristic can significantly improve the efficiency of the search algorithm.
- Heuristics are problem-specific, and their quality can affect the performance of informed search algorithms. Some heuristics might overestimate the true cost to the goal, which can lead to suboptimal solutions (in the case of AI).
Summary
Informed search algorithms use domain-specific knowledge (heuristics) to guide the search process and make it more efficient, often at the expense of increased complexity in calculating the heuristic or managing the search space. These algorithms are crucial in AI tasks such as pathfinding, puzzle solving, and decision-making in complex environments.