Understanding Admissible Heuristics in A* Search

A heuristic function, denoted as $h(n)$, estimates the cost from a node $n$ to the goal in a search problem. For the A* search algorithm to guarantee optimality, the heuristic must be admissible. Admissibility means that the heuristic estimate never overestimates the true cost. Mathematically, if $h^*(n)$ represents the actual minimum cost from node $n$ to the goal, then an admissible heuristic satisfies $h(n) \le h^*(n)$ for all nodes $n$.

Analyzing Heuristic Combinations

The question asks which expression involving two admissible heuristics, $h_1$ and $h_2$, is always admissible. Let's analyze the given options:

• Option 1: $h_1 + h_2$
  The sum of two admissible heuristics is not necessarily admissible. For example, if $h^*(n) = 5$, $h_1(n) = 4$, and $h_2(n) = 4$, both $h_1$ and $h_2$ are admissible ($4 \le 5$). However, their sum $h_1(n) + h_2(n) = 8$, which is greater than $h^*(n)$ and therefore not admissible.
• Option 2: $h_1 \times h_2$
  Similar to the sum, the product can overestimate the cost. Using the same example, $h_1(n) \times h_2(n) = 4 \times 4 = 16$, which is greater than $h^*(n)=5$.
• Option 3: $h_1 / h_2$ ($h_2 \neq 0$)
  This combination can also overestimate. Consider $h^*(n) = 3$, $h_1(n) = 4$, and $h_2(n) = 1$. Both $h_1$ and $h_2$ are admissible ($4 > 3$ is false, so let's correct. $h^*(n) = 5$. $h_1(n)=4$, $h_2(n)=2$. Both admissible. $h_1/h_2 = 4/2 = 2 \le 5$. Works. Try $h^*(n) = 3$. $h_1(n) = 4$, $h_2(n) = 1$. $h_1$ is not admissible here. Let $h^*(n) = 5$. $h_1(n)=6$, $h_2(n)=2$. $h_1$ is not admissible. Let's consider a case where $h_1$ and $h_2$ are admissible but the division is not. If $h^*(n) = 4$, $h_1(n) = 5$, $h_2(n) = 2$. $h_1$ is not admissible. Let's use the property $h_1(n) \le h^*(n)$ and $h_2(n) \le h^*(n)$. Consider $h^*(n) = 3$. Let $h_1(n) = 3$ and $h_2(n) = 1$. Both are admissible. Then $h_1(n)/h_2(n) = 3/1 = 3 \le 3$. What if $h_1(n) = 4$, $h_2(n) = 1$? This requires $h^*(n) \ge 4$. Let $h^*(n) = 4$. Then $h_1(n)/h_2(n) = 4/1 = 4 \le 4$. Let $h^*(n)=5$. $h_1(n)=6$, $h_2(n)=2$. $h_1$ is not admissible. Consider $h_1(n)=5$, $h_2(n)=3$. $h^*(n)=4$. $h_1$ is not admissible. The expression $h_1/h_2$ is not guaranteed to be admissible. For instance, if $h^*(n) = 4$, $h_1(n) = 5$ (not admissible), $h_2(n) = 1$ (admissible). This example violates the premise. Correct example: $h^*(n) = 3$, $h_1(n) = 2$, $h_2(n) = 0.5$. $h_1$ is admissible. $h_2$ is admissible. $h_1/h_2 = 2 / 0.5 = 4$. $4 > 3$. Not admissible.
• Option 4: $|h_1 - h_2|$
  Since both $h_1$ and $h_2$ are admissible, we know $h_1(n) \le h^*(n)$ and $h_2(n) \le h^*(n)$. This implies that the maximum value either heuristic can take is $h^*(n)$. The absolute difference between two numbers, each less than or equal to a third number, must also be less than or equal to that third number. Mathematically, $|h_1(n) - h_2(n)| \le \max(h_1(n), h_2(n))$. Because $h_1(n) \le h^*(n)$ and $h_2(n) \le h^*(n)$, it follows that $\max(h_1(n), h_2(n)) \le h^*(n)$. Therefore, $|h_1(n) - h_2(n)| \le h^*(n)$, proving that this expression is always admissible.

Conclusion on Admissibility

Based on the analysis, the expression $|h_1 - h_2|$ is the only one guaranteed to be admissible when $h_1$ and $h_2$ are admissible heuristics.