Informed search, also known as heuristic search, is a search strategy that uses additional information or heuristics to guide the search towards the goal more efficiently.
- These algorithms use an evaluation function to estimate the cost or distance from the current state to the goal state, helping to find optimal or near-optimal solutions faster than uninformed methods.
Types of Informed Search:
- Greedy Best first search
- A* search
- Hill Climbing
- Simulated Annealing
1.) Greedy Best first search:
Greedy Best-First Search is an informed search algorithm that expands the node closest to the goal based on a heuristic function h(n).
- It prioritizes nodes that appear to be the most promising, without considering the cost to reach them.
2.) A* search:
A* Search is an informed search algorithm that combines the cost to reach a node g(n) and the heuristic estimate of the cost to the goal h(n).
- It uses the evaluation function
f(n)=g(n)+h(n)to prioritize nodes, ensuring optimality if the heuristic is admissible (never overestimates the cost).
3.) Hill Climbing:
Hill Climbing is a local search algorithm that starts with an initial state and iteratively moves to the best neighboring state based on a heuristic.
- It stops when no better neighboring state is found, but it can get stuck in local optima.
4.) Simulated Annealing:
Simulated Annealing is a probabilistic search algorithm inspired by the annealing process in metallurgy.
- It allows moves to worse states with a certain probability to escape local optima, gradually reducing this probability over time.
