UGC NET CSE | December 2013 | Part 3 | Question: 25

Question

If h* represents an estimate from the cost of getting from the current node N to the goal node and h represents actual cost of getting from the current node to the goal node, then A* algorithm gives an optimal solution if 

• A. h* is equal to h
• B. h* overestimates h
• C. h* underestimates h
• D. none of these

Answer 1

ans should be C   h* underestimates h .

Rule is A∗A∗ algorithm gives an optimal solution if  h* never  overestimates h (admissible heuristics  so b is out

underestimating  h means algo  is looking for better soln which may be found if it is there(optimal soln)