For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once.

But if h(n) = number of tiles on correct place. h(n) is not an admissible heuristic. Can anybody please explain.

  • $\begingroup$ Try to use the definition of admissible heuristic. $\endgroup$ – Yuval Filmus Dec 9 '18 at 0:54
  • $\begingroup$ can you please elaborate? $\endgroup$ – jisan Dec 9 '18 at 17:23
  • $\begingroup$ To show that something is not an admissible heuristic, you need to show that it doesn’t satisfy the definition. $\endgroup$ – Yuval Filmus Dec 9 '18 at 17:24
  • $\begingroup$ yeah, by definition, a heuristic to be admissible to the search problem, the estimated cost must always be lower than or equal to the actual cost of reaching the goal state. So if 7 tiles is in correct place we got h(n) =7 and 1 is in wrong place. We can move this tile by 1 move. In that case, the actual cost is less than h(n). Then it should be admissible heuristic, isn't it. $\endgroup$ – jisan Dec 11 '18 at 18:57
  • $\begingroup$ An admissible heuristic is one that lower bounds the cost of all possible solutions. If you have to move only 1 tile but your heuristic says 7 tiles, then it’s not admissible. $\endgroup$ – Yuval Filmus Dec 11 '18 at 20:24

Your Answer

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

Browse other questions tagged or ask your own question.