Introduction to Artificial Intelligence - Old Questions
4. What is meant by admissible heuristic? What improvement is done in A* search than greedy Search? Prove that A* search gives us optimal solution if the heuristic function is admissible.
Answer
AI is thinking...
A heuristic function is said to be admissible if it is no more than the lowest-cost path to the goal. In other words, a heuristic is admissible if it never overestimates the cost of reaching the goal.
In greedy search, the evaluation function is defined by f(n) = h(n)
Where, h(n) is an estimate of cost from node n to goal node.
But in A* search, the evaluation function is defined by f(n) = g(n) + h(n)
Where, g(n) is sum of actual costs incurred while travelling from root node (start node) to node n.
h(n) is an estimate of cost from node n to goal node
f(n) is estimated total cost of path through n to goal.
A* search gives us optimal solution if the heuristic function is admissible.
Proof:
