Manhattan distance in *

Question

I am using the NxN puzzle solution using the A * search algorithm and using Manhattan distance as a heuristic, and I came across a curious error (?) That I cannot circle around.

Consider these puzzles (0 is empty space):
(Initial)

1 0 2
7 5 4
8 6 3

(target)

1 2 3
4 5 6
7 8 0

The minimum number of steps to reach a solution from the initial state is 11. However, my solver reaches the goal in 17 moves.

And this is the problem - my puzzle solves mainly solvable puzzles in the correct (minimum) number of moves, but for this particular puzzle my solver over-performs the minimum number of moves, and I think I nailed the problem to the calculation of the Manhattan distance in this particular case.

On this you can see what my solver does (on the right) and what the proven n-test solver does (Brian Borowski is an excellent solver available here ).

In the very first step, Brian solver immediately selects a solution that pushes element 5 up, but my solver has other ideas, and on the stack (on link ), my solver chooses a solution that pushes 2 to the left (since the distance to Manhattan on board is less , the board is on the front of the priority queue). I don’t see what the problem is, and I can’t blame my calculation of the Manhattan distance, since it correctly solves a number of other 3x3 puzzles.

Here's how I calculate the Manhattan distance of a given Rules:

 /** * Calculates sum of Manhattan distances for this board and stores it in private field to promote immutability. */ private void calculateManhattanDistance() { int manhattanDistanceSum = 0; for (int x = 0; x < N; x++) // x-dimension, traversing rows (i) for (int y = 0; y < N; y++) { // y-dimension, traversing cols (j) int value = tiles[x][y]; // tiles array contains board elements if (value != 0) { // we don't compute MD for element 0 int targetX = (value - 1) / N; // expected x-coordinate (row) int targetY = (value - 1) % N; // expected y-coordinate (col) int dx = x - targetX; // x-distance to expected coordinate int dy = y - targetY; // y-distance to expected coordinate manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); } } manhattanDistance = manhattanDistanceSum; } 

I would appreciate any ideas or ideas you may have.

If any additional code is needed, I will send it right away.

Answer 1

I was stuck in the same place somewhere back where I solved it in 17 moves. The problem was that I used heuristic h (n) for the A * algorithm, and to select the next node A * uses the baton manhattan (heuristic) + pathcost (the cost to reach the node from the root called g (n)) to do a choice. Once you connect this to the algorithm, it works like a charm.

Hope this helps someone stuck in one place.

Answer 2

If your heuristic is valid (and this means this ), then A * always returns the optimal solution. It may be slower or faster (expanding more or less nodes), but it returns the optimal solution.

Thus, your heuristic is valid, the problem should be in the implementation of the A * algorithm.

In addition, the fact that his first step is different from the optimal one does not make sense: the algorithm can correctly execute the return line in order to get the correct solution path in the future. All open nodes are candidates for the next step, and not just from the current current node.