1
$\begingroup$

I am studying for an artificial inteligence class, and i have to classify the following sentence

"For any search space, there is always an admissable and consistent A* heuristic".

Well, i know that there is always an admissable heuristic, for example zero, since its an underestimation of the real cost (althoug this would lead to uniform cost instead of a*).

What I would like to know is if there is always a consistent heuristic, and why.

Thanks for your help

$\endgroup$
1
$\begingroup$

The zero heuristic is trivially admissible, as you've noted. It's also trivially consistent as long as all step-costs are non-negative: if $h(x)=0$ for all $x$ and $c(x,y)\geq 0$ for all $x$ and $y$, then $$ h(x)\leq c(x,y) + h(y) $$ for all $x$, $y$.

$\endgroup$
  • $\begingroup$ you are right, i'm actualy ashamed i did not notice that haha. please just correct the sentence to consistent, and i will consider it as correct "It's also trivially admissible as long as all step-costs are non-negative" $\endgroup$ – Rafael Marques Nov 15 '17 at 19:35
  • $\begingroup$ @RafaelMarques Yeah, I guess "it's also trivially admissible" was a bit of a trivial statement! :-D $\endgroup$ – David Richerby Nov 15 '17 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.