Talk:Consistent heuristic

This article is rated Stub-class on Wikipedia's content assessment scale.
It is of interest to the following WikiProjects:

Computing

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
???	This article has not yet received a rating on the project's importance scale.
	This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the `\|auto=` parameter.

Monotonicity Visualisation

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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 ?