I am trying to create a heuristic function for use in an A* algorithm. The problem to be solved is a single row tile puzzle with 3 total w tiles and 3 b tiles and one "_" tile as shown below
The goal of this puzzle is to get the white tiles on the right of the black tiles regardless of the position of the "_".
The possible moves for this puzzle is as shown below
The puzzle has two legal moves(i.e. actions) with associated costs: • A title may move into an adjacent empty location. – This has a step cost of 1. • A title can hop over one or two other tiles into the empty position. – This has a step cost equal to the number of tiles jumped over.
My idea for the heuristic function would be the amount of spaces the black tiles would be away from the goal state and divide this number by 2 rounded up to the nearest int. Example of this would be wbw_bwb, this state would be a heuristic cost of (1+2+2 = 5).
Would this be an admissible estimate, Also i am looking for a secondary heuristic function that I could use to satisfy the assignment.
I have thought of a couple others that I think will work and probably will be closer to what the problem would actually be.
first one is the amount of total chars that are out of position so bwbb-ww this would be a heuristic of 2.
next would be the amount of w's are to the left of each b added together so wwb-wbb this would be (2 + 3 + 3) for a total of 8.