GATE 2024 DA Q.23: solution and answer

Official answer: DSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. A heuristic $h$ is admissible if $0\le h(n)\le h^{\ast }(n)$ for every node $n$, where $h^{\ast }(n)$ is the true cheapest cost from $n$ to a goal. We need the expression that satisfies this bound for every pair of admissible $h_1,h_2$ at every node.

2. (A) $h_1+h_2$: take $h_1=h_2=h^{\ast }$, which is admissible because $h^{\ast }$ never overestimates itself. The sum is $2h^{\ast }(n)>h^{\ast }(n)$ at any node with $h^{\ast }(n)>0$. It overestimates, so it is not always admissible.

3. (B) $h_1\times h_2$: take $h_1=h_2=h^{\ast }$ at a node where $h^{\ast }(n)=5$. The product is $25>5$. Not admissible.

4. (C) $h_1/h_2$: take $h_1=h^{\ast }=5$ and $h_2=0.1$, which is admissible since $0\le 0.1\le 5$. The ratio is $50>5$. Not admissible.

5. (D) $|h_1-h_2|$: both $h_1(n)$ and $h_2(n)$ lie in $[0,h^{\ast }(n)]$. The absolute difference of two non-negative numbers is at most the larger of them, so $0\le |h_1-h_2|\le \max (h_1,h_2)\le h^{\ast }(n)$. It never overestimates, so it is admissible for every pair of admissible heuristics.

6. Therefore only $|h_1-h_2|$ is always admissible, which is option (D).