0
$\begingroup$

Is there any way to prove that an admissible heuristic may not be consistent? Most proof I came across are through examples .Is there a generalized proof?

$\endgroup$
2
  • $\begingroup$ What have you tried? Where did you get stuck? Do you have a specific instance of the problem that you weren't sure how to handle? One valid way to dis-prove "X is always true" is to exhibit one example where X isn't true, so it's not clear what you are asking -- it seems you already know of some counterexamples, so I can't tell what you are looking for. $\endgroup$
    – D.W.
    Jul 21 '15 at 18:07
  • $\begingroup$ A counterexample is a proof. $\endgroup$ Jul 21 '15 at 21:36
2
$\begingroup$

If you want to prove a heuristic is not consistent a counterexample is all you need, you don't need a more "generalized" proof. A counterexample is proof enough.

This is because a heuristic is consistent if some property always holds. It is not consistent if the property doesn't hold once. An example is all you need to show something happens once, if you want to show something always holds then you need a general proof.

$\endgroup$
3
  • $\begingroup$ can you provide a counterexample . $\endgroup$
    – Alex_ban
    Jul 21 '15 at 16:29
  • $\begingroup$ "if you want to show something always holds then you need a general proof."Liked this line.Thanks. $\endgroup$
    – Alex_ban
    Jul 21 '15 at 16:29
  • $\begingroup$ @Alex_ban $2$ is a counterexample to the claim "all even numbers are squares". $\endgroup$ Jul 21 '15 at 22:39

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.