3
$\begingroup$

I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,W,W,W), where * represents a blank space. A piece can move into a blank space and can jump over one or two other pieces into a blank space. I've attached a picture of the graph.

enter image description here

This Heuristic is Admissible because the distance to the goal is ALWAYS more than the distance from the B's to the rightmost W.

The thing I'm not sure of is if this Heuristic is monotonic. My understanding of Monotonic is that the cost of going to an adjacent node plus the estimate of the new node have to be less than the total distance to the goal. How would I determine if this Heuristic is monotonic?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Although drawing the entire tree can help for a small example to get a basic idea, it is usually better use formal reasoning for the 'real' case, as it can give you an answer for the general problem, including (B,B,B,B,*,W,W,W,W), for example. As for how to show it, I think a proof by contradiction might work: what happens if $h(parent) > cost(parent,child) + h(child)$? Do we arrive at a contradiction? $\endgroup$
    – Discrete lizard ♦
    Commented Apr 3, 2017 at 11:34
  • $\begingroup$ I do not see why the distance to the goal is always more than the distance from the B's to the rightmost W. If we move from (B,B,B,W,W,$\star$,W) to (B,B,$\star$,W,W,B,W) (jumping over 2 W's), then the heuristic function decreases by 3 in a single move. Is there a different cost for moves depending on whether they jump over 0,1, or 2 pieces? $\endgroup$
    – Vincenzo
    Commented Jan 16, 2019 at 13:17

1 Answer 1

Reset to default
-2
$\begingroup$

If your heuristic is essentially the original problem, but with some constraints removed, it is monotonic. Otherwise, you must prove that there is no transition which does not uphold the formula in Caesar's answer.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Again, this is more of a comment. It would be more helpful if you provided a few simple example of both cases. $\endgroup$
    – Yuval Filmus
    Commented Apr 3, 2017 at 7:09
  • $\begingroup$ That certainly isn't the definition. If it's a theorem, it needs to be backed up by some sort of argument as to why it would be true. And what does "essentially" mean? $\endgroup$
    – David Richerby
    Commented Apr 3, 2017 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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