0 down vote favorite
My problem is sorting strings given in three lists using implementation of A* search,so I need to develop a heuristic function that will make solving various instances of this problem efficient.
The state can be represented s a list of 3 lists, example: [ [C B], [D], [H G F A E] ]
I pick up the top portion of any stack and move it to any other. For example, the H above could be moved on top of the C or the D, and the [H G] could be moved onto the second stack to create [H G D], etc. In this domain, there are unit operator costs, so each move costs 1, regardless of how many words are being moved.
The goal is to take an initial, configuration of blocks and move them all to the left stack in sorted order from top down. For example, given the 8 blocks in the above example, the goal would be [[A B C D E F G H] [] []].
I need to develop a heuristic that can be used with A* search to make the search efficient. I should try to keep the heuristics you develop admissible. For that you may try to have your heuristics to approximate the number of steps remaining to reach the goal state.
I thinking about a heuristic depends on the sorted words in each stack and the sum of points of each stack is the heuristic for the state, but this is not efficient, I think that I need to include the ascii code of each letter to my calculations, any ideas?