1

I know Manhattan distance is an admissible heuristic function since it doesn't overestimate the cost of moving a tile to the correct location. But my question is

If I double h, say scale up each of the weighted Manhattan distances by a factor of 2, or the factor of the corresponding tile value (e.g., h'=9*h if we are moving tile 9, 2*h if we move 2).

Is it still admissible? My feeling is it's not since it overestimate the true cost. So for this specific problem, is Manhattan distance the most dominant heuristic function possible?

taking this as an example, starting with

1 2 3
4 5 6
7 0 8

we want

1 2 3
4 5 6
7 8 0

Apparently we only need one move (swap 0 and 8) and guaranteed to find a solution, so admissible or non admissible at this point doesn't matter. But in general, does 2*MD an admissible heuristic function? How do we justify this?

  • It would take work to come up with a specific example that breaks. But a heuristic that overestimates the distance will happily find an answer with an initial wrong move, gets close, then does a bunch of backtracking at the end. Without ever considering the right move. – btilly Feb 06 '23 at 19:08

0 Answers0