What kind of heuristics for BFS use to solve this

问题:

I want to solve a 'game'. I have 5 circles, we can rotate circles into left or into right (90 degrees).

Example:

Goal: 1,2,3,....,14,15,16 Ex. of starting situations: 16,15,14,...,3,2,1

I'm using BFS to find path but I can't invent heuristic function (my every solutions are not good). I was trying manhattan distance and others... (Maybe idea is good but something wrong with my solution). Please help!

回答1:

One trick you might try is to do a breadth-first search backward from the goal state. Stop it early. Then you can terminate your (forward from the initial state) search once you've hit a state seen by the backward search.

Sum of Manhattan distances from pieces to their goals is a decent baseline heuristic for the forward A* search. You can do rather better by adding up the number of turns needed to get 1-8 into their places to the number of turns needed to get 9-16 into their places; each of these state spaces is small enough (half a billion states or so) to precompute.

回答2:

One heuristic that you could use is the cumulative number of turns that it takes to move each individual segment to its designated spot. The individual values would range from zero (the item is in its spot) to five (moving corner to corner). The total for the goal configuration is zero.

One has to be careful using this heuristic, because going from the initial configuration to the desired configuration may require steps when the cumulative number of turns increases after a move.

Finding a solution may require an exhaustive search. You need to memoize or use another DP technique to avoid solving the same position multiple times.

回答3:

A simple conservative (admissible) heuristic would be:

1. For each number 1 <= i <= 16, find the minimum number of rotations needed to put i back in its correct position (disregarding all other numbers)
2. Take the maximum over all these minimums.

This amounts to reporting minimum number of rotations needed to position the "worst" number correctly, and will therefore never overestimate the number of moves needed (since fixing all numbers' positions simultaneously requires at least as many moves as fixing any one of them).

It may, however, underestimate the number of moves needed by a long way. You can get more sophisticated by calculating, for each number 1 <= i <= 16 and for each wheel 1 <= j <= 5, the minimum number of rotations of wheel j needed by any sequence of moves that positions i correctly. For each wheel j, you can then take a separate maximum over all numbers i, and finally add these 5 maxima together, since they are all independent. (This may be less than the previous heuristic, but you are always allowed to take the greater of the two, so this won't be a problem.)