1
$\begingroup$

In the $A^*$ algorithm, the optimality of the path is guaranteed when the heuristic has the property of being admissible or monotone\consistent.

I was able to understand the admissible property, however, I am not able to wrap my head as how the monotone property guarantees that any node can be explored only once (i.e., the path that lead to that node has the shortest path). As stated in the wiki page ,

"If the heuristic $h$ satisfies the additional condition $h(x) \le d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), then $h$ is called monotone, or consistent. In such a case, $A^*$ can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see closed set below)—and $A^*$ is equivalent to running Dijkstra's algorithm with the reduced cost $d'(x, y) = d(x, y) + h(y) − h(x)$."

$\endgroup$
2
$\begingroup$

When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

enter image description here

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $$d(a,b)+d(b,c) < d(a,c)$$ is true, we must visit $b$ first. We can add $h(c)$ on both sides without changing anything. $$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$ If the monotonic constraint is fulfilled, we can replace $d(b,c)+h(c)$ by $h(b)$, since it's less or equal. The equation $$d(a,b)+h(b) < d(a,c)+h(c)$$ is still true. This also happens to be the test the $A*$ algorithm uses do decide whether or not it will visit $b$ before $c$. If it is true, it visits $b$ first. This is exacly what we wanted to achive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.