A* Heuristic implementation

I am creating a program to solve this puzzle in the lowest cost

The sliding-title puzzle consists of three black titles, three white titles, and an empty space in the configuration shown in the Figure.

WWW_BBB

The goal of the puzzle is to get all white tiles to the right of the black tiles while the location of the space does not matter

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     
• 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.

I am having troubles understand how to create a Heuristic algorithm to be implemented in the algorithm.

I understand the implementation of Dijkstra's algorithm within this problem, but can't figure out how to then make it into the A* algorithm.

1 answer

  • answered 2018-02-13 01:31 Matt Timmermans

    Assuming you want to use A* on the graph of puzzle states with edges to the states reachable through one of the two rules, then a good heuristic to use would be the number of inversions: https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)

    That's the number of W,B pairs that are out of order (assuming that the relative order of same-colored tiles doesn't change). The W's and B's are in order when the number of versions is 0, and the number of inversions fixed by each type of move is less than or equal to its cost. Therefore the number of inversions as a heuristic will never overestimate the cost of the best sequence.