Why is it true that given a monotonic heuristic function, A* can be seen as <PERSON>'s algorithm where no node needs to be processed more than once?
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 <PERSON>'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. 835
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 <PERSON>'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 ? 180