GATE DS&AI 2024 | Question: 13

Question

​​​​​​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?

• A. $h_{1}+h_{2}$
• B. $h_{1} \times h_{2}$
• C. $h_{1} / h_{2},\left(h_{2} \neq 0\right)$
• D. $\left|h_{1}-h_{2}\right|$

Comments

• h1 + h2:

  • This sum can get very large, hence it could overestimate the actual cost. 
  • Hence - Not admissible

• h1 * h2:

  • This product can also become very large, leading to overestimations. 
  • Hence - Not admissible

• h1 / h2 (h2 ≠ 0):

  • Division by zero is undefined. 
  • Excluding that case as written in the question, the result will still depend on the signs of h1 and h2. 
  • Therefore, it can underestimate or overestimate the cost depending on the specific situation for different problems. 
  • Hence - Not admissible

• |h1 - h2|:

  • The absolute value ensures a non-negative result. Even if both h1 and h2 underestimate the actual cost, their difference will still be a non-negative value that cannot overestimate the cost.
  • If h1 & h2 both underestimate the cost, and the result of their difference is negative, the absolute value would result in a positive difference which would be lesser than the actual cost A (and also lesser than the values h1 & h2) and hence underestimate.
  • If either of h1 or h2 overestimates the value in some case, then their difference will always be a lesser value than the actual cost A because the other valye (h1 or h2) will underestimate.
  • Hence, |h1-h2| will always be an admissable heuristic.

Answer 1

To determine which expression is always an admissible heuristic, let's first review the definition of an admissible heuristic:

An admissible heuristic is one that never overestimates the cost to reach the goal from any given state. In other words, the heuristic value must always be less than or equal to the actual cost.

Given two admissible heuristics \( h_1 \) and \( h_2 \), let's evaluate each expression:

A. \( h_1 + h_2 \)

This expression represents the sum of two admissible heuristics. Since both \( h_1 \) and \( h_2 \) are admissible, their sum is also guaranteed to be admissible. Therefore, Option A is an admissible heuristic.

B. \( h_1 \times h_2 \)

This expression represents the product of two admissible heuristics. While both \( h_1 \) and \( h_2 \) individually are admissible, their product might not necessarily be admissible. If one of the heuristics overestimates the cost while the other underestimates it, their product could overestimate the actual cost. Therefore, Option B is not necessarily an admissible heuristic.

C. \( \frac{h_1}{h_2} \), \( (h_2 \neq 0) \)

This expression represents the division of two admissible heuristics. Similarly to Option B, if \( h_2 \) underestimates the cost and \( h_1 \) overestimates it, their division could overestimate the actual cost. Therefore, Option C is not necessarily an admissible heuristic.

D. \( |h_1 - h_2| \)

This expression represents the absolute difference between two admissible heuristics. Since taking the absolute difference ensures that the result is non-negative, and since both \( h_1 \) and \( h_2 \) are admissible, their absolute difference is also guaranteed to be admissible. Therefore, Option D is an admissible heuristic.

So, the correct answer is:

D. \( |h_1 - h_2| \)

Comments

But in the question itself it is gievn that both h1 and h2 heuristic are admissible then how h1 or h2 can overestimate the cost as you have considered in your explanation.