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.

Edit below

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.

  • 1
    $\begingroup$ The way to tell whether a heuristic is admissible is to check whether it satisfies the definition of "admissible". Do you know the definition? Have you tried applying it to this particular proposed heuristic? What progress have you made? Where did you get stuck? $\endgroup$ – D.W. Feb 13 '18 at 7:13
  • $\begingroup$ well for it to be admissible, you have to have the path from the current node to the destination be greater than the cost of the heuristic estimate plus the path cost to the node that is being evaluated. I can not think of why this heuristic would not work and be admissible. $\endgroup$ – Jeffrey Hennen Feb 13 '18 at 8:01
  • $\begingroup$ For the heuristic to be admissible, it is necessary for it to work for all cases (i.e. it must satisfy the property for all cases). So, I would suggest that you find out all the cases which the heuristic needs to cover. It seems you have found some possible heuristics which seems to be logical. There couldn't be too many cases as the problem isn't much complex! $\endgroup$ – kiner_shah Feb 13 '18 at 8:24
  • $\begingroup$ as far as i can tell, these would be admissible but I am unable to tell for sure $\endgroup$ – Jeffrey Hennen Feb 13 '18 at 8:25

Your Answer

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

Browse other questions tagged or ask your own question.