patternMinor
Does an optimal path imply the heuristic is admissible?
Viewed 0 times
implypaththeoptimaladmissibleheuristicdoes
Problem
If we are given an A$^*$ path search with some heuristic $h$ that yields an optimal path, without knowing that the heuristic is admissible beforehand, would this imply that $h$ is admissible?
Solution
No.
Let us consider an extreme example. Let graph $G$ contain only two nodes, the starting node $s$ and the destination node $t$. The distance of edge $(s,t)$ is 1.
We have a heuristic function $h$, $h(s)=2$ and $h(t)=0$. $h$ is not admissible since $h(s)>1$.
However, using $A^*$ search algorithm, we will end up with the path $s, t$, the unique and, hence, optimal path.
Exercise. Construct a counterexample where there are more than one path.
Let us consider an extreme example. Let graph $G$ contain only two nodes, the starting node $s$ and the destination node $t$. The distance of edge $(s,t)$ is 1.
We have a heuristic function $h$, $h(s)=2$ and $h(t)=0$. $h$ is not admissible since $h(s)>1$.
However, using $A^*$ search algorithm, we will end up with the path $s, t$, the unique and, hence, optimal path.
Exercise. Construct a counterexample where there are more than one path.
Context
StackExchange Computer Science Q#104897, answer score: 3
Revisions (0)
No revisions yet.