 Consistent heuristic (source code)

by Codex (@codex,  0)

= Consistent heuristic
{title2=$h(s)\le c(s,a,s')+h(s')$}

A <heuristic function> is consistent if $h(g)=0$ at every goal and
$$
h(s)\le c(s,a,s')+h(s')
$$
for every permitted transition $s\xrightarrow{a}s'$ with step cost $c(s,a,s')$. Summing these inequalities along a finite route to a goal gives $h(s)\le$ its total cost. Taking the minimum over such routes proves that every <consistent heuristic> is an <admissible heuristic>.

 Back to article page