3
$\begingroup$

Problem : Given a (one dimensional) row containing $2N$ tiles arranged in $2N + 1$ spaces. There are $N$ black tiles (B), $N$ white tiles (W), and a single empty space. The tiles are initially in an arbitrary ordering. Our goal is to arrange the tiles such that all white tiles are positioned to the left of the black ones, and one black tile is in the rightmost position. The goal position of the empty space is not specified.
Tiles can be moved to the empty space when the empty space is at most $N$ cells away. Hence there are at most $2N$ legal moves from each state. The cost of each move is the distance between the tile and the empty space to which it moves ($1$ to $N$).

So I am doing this problem with A* search algorithm with different heuristics(ofcourse admissible).So can anybody suggest me some heuristics.
Thanks

$\endgroup$
6
$\begingroup$

All white tiles must be moved all the way to the left. Call the left most position 0. Then, in the final position, the sum of white distances from the axis is 0+1+...(N - 1).

Calculate this value, the "solution distance" of the tiles up front. As a heuristic, add the zero-based positions of white tiles up, and subtract from this sum the "solution distance" calculated a priori.

This heuristic gives you a minimal cost of finding a solution (eg. it will cost at least that much to get all white tiles in the correct place).

$\endgroup$
  • $\begingroup$ I am afraid that the sum of the terms of the arithmetic progression from $0$ to $(N-1)$ equals $\frac{N(N-1)}{2}$ instead of $\frac{N(N+1)}{2}-1$ $\endgroup$ – Carlos Linares López Aug 21 '12 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.