Question

If we have two admissible heuristics h1 and h2, would it be better to use min(h1, h2) or max(h1, h2) as a heuristic with A* search? Briefly explain your answer.

Answer 1

If you like the solution please give it a thumbs up. And if you have any query please let me know in the comments.

Solution :-

from the definition of admissible heuristic - In order for a heuristic to be admissible to search problem, the estimated cost must be lower than or equal to the actual cost of reaching to the goal .

Now assume, h(n) <- optimal cost from node n to goal

so clearly h1(n) <= h(n)

and. h2(n) <= h(n)

But now we are not sure about the relation between h1 and h2.

now if we choose between min(h1,h2) and max(h1,h2) then min(h1,h2) <= max(h1,h2) <= h

So clearly min(h1,h2) will deviate more from the optimal path than to max(h1,h2). So it is better to choose max(h1,h2).