GATE 2024 DA – Question 23

Artificial Intelligence · Search: informed, uninformed and adversarial · 1 mark · Multiple choice

Let $h_1$ and $h_2$ be two admissible heuristics used in $A^*$ search. Which ONE of the following expressions is always an admissible heuristic?

$h_1 + h_2$
$h_1 \times h_2$
$h_1/h_2$, ($h_2 \neq 0$)
$|h_1 - h_2|$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $|h_1 - h_2|$

Explanation

A heuristic is admissible if it never exceeds the true cost $h^*$. The difference $|h_1 - h_2|$ is at most $\max(h_1, h_2) \le h^*$, so it is always admissible. The sum can reach $2h^*$, the product can be larger than $h^*$ when the heuristics are large, and the ratio can be larger than $h^*$ when $h_2$ is small.