I have a modified 8 puzzle problem such that each transition's cost is associated with the number of the piece that is moved. So, for example, if piece "3" is moved, the move would cost 3 units.

I am trying to find an admissible heuristic that dominates the Manhattan distance, but am having trouble deriving one.

My thoughts:

Since the Manhattan distance gives us the distance of any tile from its end goal, wouldn't a heuristic that dominates the Manhattan distance not be admissible? For example, if a piece is 1 state away from its goal state, how can there be an admissible heuristic that is $>=$ 1 for that piece?

  • $\begingroup$ Check the definition of admissible again, and work through an example. Can you find an example configuration where that particular heuristic is an underestimate of the total number of moves needed to solve the puzzle? $\endgroup$ – D.W. Jan 25 '17 at 21:49
  • $\begingroup$ @D.W. thought about your comment and honestly still not sure what direction to head $\endgroup$ – JasonDor Jan 27 '17 at 1:53
  • $\begingroup$ Maybe this paper could give you some ideas: ethesis.nitrkl.ac.in/5575/1/110CS0081-1.pdf $\endgroup$ – Chocksmith Mar 24 '18 at 10: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.