0
$\begingroup$

Could someone give the intuition behind consistency of heuristic function in the A* algorithm?

From wikipedia:

Every node i will give an estimate that, after accounting for the cost to reach i + 1, is always lesser than the estimate at node i + 1.

I understand what this means, but is there any intuitive meaning behind it? And how does this lead to monotonicity of the evaluation function = f(n) = g(n) + h(n)?

Improve this question
$\endgroup$
2
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Oct 12, 2022 at 19:55
  • $\begingroup$ @Community modified, is it better now? $\endgroup$
    – learner
    Oct 13, 2022 at 15:14

1 Answer 1

Reset to default
0
$\begingroup$

A consistent heuristic must not overestimate the true cost to get to the goal from a particular node - the heuristic estimate is always less than or equal to the cost to get to another node plus the estimated cost from that node to the goal (which itself cannot be an overestimate).

Basically, a consistent heuristic will not spuriously discard truly good options because it overestimates their cost and treats them as bad options. An inconsistent heuristic might overestimate the cost of some path, and instead explore another, costlier path and miss the optimal solution. A consistent heuristic allows paths to turn out longer than expected (since you can explore them and then go elsewhere if needed), but it does not allow paths to turn out shorter than expected (since you may miss them entirely if you get to the goal first).

With a consistent heuristic, the estimated final cost of of a partial solution (f(n) = g(n) + h(n)) is monotonically non-decreasing along the best path. The consistent heuristic can't overestimate costs, so true the cost must always be as large or larger than the estimated cost. If you move along the best path closer to the goal, the estimated final cost must not decrease - if you get closer to the goal and find your estimated final cost has decreased, it must mean that you overestimated the remaining cost somewhere along the way, which means the heuristic is not consistent.

Improve this answer
$\endgroup$

You must log in to answer this question.

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