Search algorithm heuristic *

Question

I am trying to find the best solution for a sliding puzzle of any length using the A * algorithm.

Puzzle with a sliding block - a game with white (W) and black tiles (B), placed on a linear game board with one empty space (-). Given the initial state of the board, the goal of the game is to arrange the tiles in the target pattern.

For example, my current status on board is BBW-WWB, and I need to reach BBB-WWW. The tiles can move as follows: 1. Go to an adjacent empty space with a value of 1. 2. Jump over another plate into an empty space with a value of 1. 3. Jump over 2 tiles into an empty space with a value of 2.

Everything is implemented for me, but I'm not sure about the heuristic function. It calculates the shortest distance (minimum cost) possible for an inappropriate tile in the current state to the nearest colored tile placed in the target state.

Given this problem for the current state of BWB-W and the target state of BB-WW, the heuristic function gives me a result of 3. (according to the minimum distance: B = 0 + W = 2 + B = 1 + W = 0). But the actual cost of achieving the goal is not equal to 3 (moving inappropriate cost W => 1, and then inappropriate B => cost 1), but 2.

My question is: should I calculate the minimum distance in this way and not care about re-evaluation, or should I divide it by 2? According to the methods of the tile, you can move, one tile can overcome twice as much at the same cost (see Steps 1 and 2).

I tried both versions. While shared distance gives a better final cost to the reachable goal, it visits more nodes => takes longer than not shared. What is the correct way to calculate it? Which one should I use?

Answer 1

It does not seem obvious to me what a valid heuristic function looks like for this problem, so I won’t say: "Use division into two functions." But I will tell you that the naive function that you came up with is unacceptable and therefore will not give you a good job. For A * to work properly, the heuristic used must be valid; in order to be valid, heuristics must absolutely always give an optimistic assessment. This does not happen, precisely for the reason that you emphasize in your example.

(Although now, when I think about it, dividing by two really seems like a reasonable way to force validity. I'm just not going to do it.)

Answer 2

Your heuristic is invalid, so your A * is not guaranteed to find the optimal answer every time. Valid heuristics should never overestimate value.

A better heuristic than dividing the heuristic value by 3 would be: instead of adding the distance D of each letter to its final position, add ceil (D / 2). So the letter 1 or 2, gets 1 value, 3 or 4, gets 2 values, and so on.