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?

$\endgroup$
  • 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 Apr 3 '17 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 Jan 16 at 13:17
-1
$\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.

$\endgroup$
  • 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 Apr 3 '17 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 Apr 3 '17 at 9:20

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.