[Solved]: Heuristics for an Artificial Intelligence problem

ignougroup
Problem Detail: 

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

Asked By : justice league

Answered By : Kirby

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).
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3266

Leave a Reply