Answer:
Informed search (heuristic search) uses additional knowledge (heuristics) to guide search more efficiently.
A heuristic function h(n) estimates the cost from node n to the goal.
Greedy Best-First Search:
- Selects node with the lowest
h(n). - Fast but not always optimal.
- Can get stuck in local minima.
A* Search:
- Uses evaluation function:
f(n) = g(n) + h(n)g(n)is cost so far,h(n)is estimated cost to goal.
- Optimal and complete if
h(n)is admissible (never overestimates).
Example Heuristics:
- For 8-puzzle:
h₁: number of misplaced tiles.h₂: Manhattan distance (sum of row and column differences).
A* search is efficient and widely used in AI applications
