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?
At the beginning, try a simple or naive heuristic. For example, "h" will be the sum of non-ascending order of two letters. Lets say when you develop a new child you got something like this [ACBED] here take first couple [AC] they are in ascending order, do nothing, but for the next couple [CB] it is not in ascending order then add one to "h". [BE] is good. For [ED] add one to "h". So "h == 2". This Heuristic looks simple but I believe it is better than blind search (i.e. breadth/depth search). From this idea you can add more rules to enhance the heuristic based on your analysis of outcomes. I hope that is useful.