What are Heuristic Functions? Discuss admissibility and examples in the 8-puzzle problem.

Answer:

Heuristic Functions (h(n)) estimate the cost from node n to the goal.

A heuristic is:

• Admissible: Never overestimates the true cost.
• Consistent: For every node n and successor n', h(n) ≤ c(n, n') + h(n').

Examples (8-puzzle):

• h₁: Misplaced tiles – counts how many tiles are not in the correct position.
• h₂: Manhattan distance – total distance tiles need to move to reach goal.

These help A* search prune bad paths and find optimal solutions faster