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|$

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.