7
$\begingroup$

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 ?

Improve this question
$\endgroup$
1
  • $\begingroup$ Djikstra is actually a special case of A*. Think of Djikstra intuitively as A* with the heuristic cost being always zero. $\endgroup$
    – Valentin Metz
    Nov 17, 2020 at 11:55

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .