GATE DA 2024 | Question 23

MCQ · 1 mark · −0.33

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?

  1. Option A: \(h_{1} + h_{2}\)
  2. Option B: \(h_{1} \times h_{2}\)
  3. Option C: \(h_{1}/h_{2}, (h_{2} \neq 0)\)
  4. Option D: \(|h_{1} - h_{2}|\) (correct)

Answer

(D)

Explanation

A heuristic is admissible when \(0 \leq h(n) \leq h^{*}(n)\) for every node \(n\), where \(h^{*}(n)\) is the true cost of reaching the goal. Because both values are non-negative,

\[|h_{1}(n) - h_{2}(n)| \leq \max(h_{1}(n), h_{2}(n)) \leq h^{*}(n),\]

so option D never overestimates.

The other expressions can overestimate. With \(h^{*}(n) = 5\) and \(h_{1}(n) = h_{2}(n) = 5\), both admissible, the sum is 10 and the product is 25. With \(h_{1}(n) = 5\) and \(h_{2}(n) = 0.1\), the ratio is 50.

Answer: D