Breaking A* admissibility caused exponential speed-up?

Question

I've been working on a generalized version of the sliding tile puzzle where the tiles do not have numbers. Instead, each location either has a tile or a hole and is represented with a boolean as true or false (tile or hole).

The point of the search is to take an initial state with n tiles and a goal state with n target locations and use A* to find the solution of how to move the tiles so that every target location is populated. Here is an example below for a 4x3 grid:

Initial State:
T F T F
F F T F
F F T T

Goal State
T T T T
T F F F
F F F F

I had been working on different heuristics to do this and the most successful had a logic that went something like this:

int heuristicVal = 0

for every tile (i)...
int closest = infinity
for every goal location (j)...
if (manhattan distance of ij < closest) closest = manhattan distance of ij
end for
heuristicVal += closest
end for

return heuristicVal

Unfortunately, this was still too slow in situations where two or more tiles were being guided by the heuristic to the same target location. I tried multiplying heuristicVal by the number of tiles and suddenly there was an exponential speed-up. Problems that were taking 28 seconds before were taking less than 1 second.

Edit: It turns out it is not always producing optimal solutions after all with this change. However, I don't understand why it sped up so much or why it is still finding the correct (although suboptimal) answer despite no longer being admissible.

Answer 1

If you break admissability, A* no longer works correctly. Note that no longer works correctly doesn't mean you're never gonna get an optimal result - you're just no longer guaranteed to get one. You can also end up converging faster on solution, but what's the point if that solution is not the right one?