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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Have you tried constructing a counterexample? Have you tried proving the conclusion? Where did you get stuck? $\endgroup$– John L.Feb 27, 2019 at 2:39
-
$\begingroup$ I'm thinking to assume the opposite, that an optimal path is not admissible. Then, h(n) > h*(n). That is, h(n) has a greater cost than the cost of an optimal heuristic and so h(n) is not optimal, a contradiction. Would this be sufficient. $\endgroup$– ParadoxFeb 27, 2019 at 3:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Is it not admissible because the heuristic over-estimated the cost of getting to t? $\endgroup$– ParadoxFeb 28, 2019 at 4:16
-
$\begingroup$ Correct, since the definition of admissible heuristic is that it never overestimates the cost of reaching the goal. $\endgroup$– John L.Feb 28, 2019 at 5:13
$\begingroup$
$\endgroup$
The solution provided by Apass Jack is absolutely correct but beyond simple examples proving that the answer is "definitely no", let me add another consideration (which actually provides a solution to the exercise suggested by Apass Jack):
A heuristic which is inadmissible does not necessarily mean that paths found by A$^*$ with that heuristic should be sub-optimal
The reason is that heuristics serve for the purpose of ranking nodes. Admissibility simply implies that if two nodes are wrongly ranked (so that one node gets expanded before the correct one) this will have a limited effect in the number of subsequent expansions as A$^*$ will never expand nodes beyond the $f$-layer that contains the optimal solution (provided that the heuristic is admissible, which is the hypothesis in this paragraph).
Consider now the case where one heuristic is inadmissible but always (always!) ranks nodes perfectly. Then, certainly nodes will get sorted in the open list in their optimal order and the optimal solution is necessarily found.
To see this consider a perfect heuristic function, $h^*(n)$ and now and inadmissible heuristic function which adds a large constant $M$ to $h^*(n)$, $h(n)=h^*(n)+M$. Well, $h(n)$ is clearly inadmissible for values of $M$ arbitrarily large, but if one node $n$ has an $h^*$-value strictly less than another $n'$, then it will be perfectly ranked by the perfect heuristic function, $h^*$, so does $h()$ because adding the same constant $M$ does not alter the ordering.
So far, the solution to the exercise suggested in the other reply is simply the following: take any graph $G(V, E)$ and compute $h^*(n), \forall n\in V$. Construct now a new heuristic function $h(n)=h^*(n)+M$ for all $n\in V$ with a constant $M$ arbitrarily large, run A$^*$ ... and smile! :)
Hope this helps,
answered Feb 28, 2019 at 0:32