2
$\begingroup$

Maybe I am missing something very easy and obvious.

But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: $$d′(x,y)=d(x,y)+h(y)−h(x)$$

What I currently know:

A* algorithm can be used as an extension for Dijkstra's algorithm. At each iteration of its main loop, it chooses the vertex with the minimum of estimation cost plus cost of the path to this vertex:

For vertex $u$ and its successor $v$, overall cost is calculated with $$f(u, v) = d(u, v) + h(v)$$ using some heuristic function $h$. Where:

  • $d(u,v)$ cost of the path from $u$ to $v$
  • $h(v)$ estimate cost from $v$ to the target vertex $t$

If for any adjacent vertices $u$ and $v$, it is true that $$h(u) <= d(u, v) + h(v)$$ then $h$ is a monotonic. In other words, graph holds triangle inequality property.

It is stated in Wiki page of A* algorithm:

If the heuristic h satisfies the additional condition $h(x) ≤ 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)$.

My questions are:

and A* is equivalent to running Dijkstra's algorithm with the reduced cost $d'(x, y) = d(x, y) + h(y) − h(x)$.

Any proof for this equivalence ?

It is clear for me that $0 <= d(x, y) + h(y) - h(x)$, and it is feasible. But:

  • Why this formula is chosen as a new distance function ?
  • Is there any formal proof that it works ?
  • Why it is not enough to run Dijkstra with $d'(x, y) = d(x, y) + h(y)$ ?
  • What is the math behind it ?
$\endgroup$
  • $\begingroup$ Have you tried one or two simple examples? What work and what do not? $\endgroup$ – Apass.Jack Jan 19 at 13:08
  • $\begingroup$ I have tried on a simple graph on a plane, it works the same as d'(x,y) = d(x,y) + h(y). But I suppose that I could not come up with a right example that explains why h(x) must be subtracted. $\endgroup$ – maksadbek Jan 19 at 13:14
  • $\begingroup$ Hi there and very welcome to Stack Exchange! I'm willing to provide an answer to your question (even if I'm literally swamped these days!) but I'd like to make sure I understood the question. Can your question be formulated as follows?: Why is it true that given a monotonic (consistent) heuristic function, A* can be seen as Dijkstra's algorithm where no node needes to be processed more than once? ---Cheers $\endgroup$ – Carlos Linares López Jan 21 at 0:15
  • $\begingroup$ Hi @CarlosLinaresLópez, I will very happy if you could answer to this question. You're right, question can be formulated exactly as yours. Moreover, it is interesting for me why the consistency condition became the heuristic function and what is a "reduced cost". I'll change the question topic. Thank you! $\endgroup$ – maksadbek Jan 21 at 7:34
  • $\begingroup$ Okay, gimme please two days maximum to address your question which is indeed pretty interesting ... Cheers and again be very welcome to Stack Exchange :) $\endgroup$ – Carlos Linares López Jan 21 at 8:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.