According to this Wikipedia article

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

Can someone intuitively explain why the reduced cost is of this form ?

  • $\begingroup$ Djikstra is actually a special case of A*. Think of Djikstra intuitively as A* with the heuristic cost being always zero. $\endgroup$ Nov 17 '20 at 11:55

What you are doing when calculating $d'(x,y)$:

  1. $d(x,y)$: calculating the original edge distance from $x$ to $y$
  2. $h(y)$: plus the heuristic from $y$ to the goal
  3. $h(x)$: minus the heuristic from $x$ to the goal

So, using this recalculation of the original edge-values ($1.$) in Dijkstra's algorithm you are inherently accounting for the heuristic component of A* by incorporating it ($2.$) into the value of the edge traversed, and discarding ($3.$) the accumulated previous heuristic values of previous nodes in the path.

The additional condition $h(x) ≤ d(x, y) + h(y)$ ensures the new edge-values are strictly positive.


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.