7

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 ?

nbro
  • 39,006
  • 12
  • 98
  • 176
Shrey Shrivastava
  • 71
  • 2
  • Djikstra is actually a special case of A*. Think of Djikstra intuitively as A* with the heuristic cost being always zero. – Valentin Metz Nov 17 '20 at 11:55

1 Answers1

1

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.

brazofuerte
  • 991
  • 8
  • 24