Talk:Consistent heuristic

Monotonicity Visualisation

Comparison of an admissible and a consistent heuristic evaluation function.

I've uploaded a chart that visualises the difference between an admissible (but not consistent) and a consistent heuristic. Or more specifically, it compares the estimated final cost of these heuristics at each iteration. I'd like to add it to the article, but would like your feedback first. I am quite sure the example heuristics are correct, but an approving look by someone else would be nice. - Johannes Simon (talk) 00:11, 2 December 2010 (UTC)

Thanks! But I think it could use more explanation. Are the step costs all 1? I'd expect the heuristic costs to decrease to zero as you approach the goal in step 5, but instead the values increase. Are we supposed to measure the heuristic as the distance from the square or circle up to the final cost, which is an actual path cost of 10?? ★NealMcB★ (talk) 04:22, 27 September 2012 (UTC)

Does c in the formulas stand for "cost of getting from a given node to its child node"?

If my guess is correct, then it would be helpful to write that for posterity, it's not clear otherwise what's meant by $c(N,P)$. — Preceding unsigned comment added by 79.181.31.243 (talk) 07:56, 24 May 2012 (UTC)

It's defined in the text as "the step cost of getting to P" [from N] for "every successor P of N". P can be a children of N, a grand children, a grand-grand-children... I.e. any node following N in the path. I've linked to the article containing the definition of successor. Diego (talk) 17:18, 24 May 2012 (UTC)

Pathmax

Using pathmax does not turn an admissible but inconsistent heuristic into a consistent heuristic. See

http://webdocs.cs.ualberta.ca/~holte/Publications/MisconceptionsFinal.pdf

for a specific example (on page 4). — Preceding unsigned comment added by 24.34.45.248 (talk) 17:12, 12 August 2013 (UTC)

   This comment is correct. I have edited the web page accordingly.Robert Holte (talk) 17:44, 10 July 2019 (UTC)

Any proof for the fact about consistent heuristic

> In fact, if the search graph is given cost c’(N, P) = C(N, P) + h(P) - h(N) for a consistent h, then A* is equivalent to best-first search on that graph using Dijkstra's algorithm.

Currently, it references to the book. I think there must be a proof for this ?