CODEWITHSUNDEEP
algorithma-starheuristics
James Smith
James Smith

Reputation: 25

How to tell when the A* algorithm is a good option, and how to choose a good heuristic?

Recently I wrote a solver for the famous "15 puzzle" using the A* algorithm by using a heuristic function based off the sum of the Manhattan distances of the distances for each tile to their destination spots.

This led me to wonder two things:

  1. How do you know when the A* algorithm is even something to use? Unless I came across online tutorials, I would have never guessed that the 15 puzzle could be solved this way.

  2. How do you know which heuristic function to use? At first, for the 15 puzzle, I considered a simple "sum of tiles not in position" heuristic. So if all pieces weren't in their right spots, the heuristic for the 15 puzzle might return 15, whereas 0 would indicate a solved board. But somehow the sum of the distances are better. How does one know, going into it?

Upvotes: 1

Views: 342

Answers (1)

user555045
user555045

Reputation: 64904

If you're exploring a graph to find a path that is in some way "shortest" (the cost doesn't have to be a "distance", but it has to be monotone), you can already use Dijkstra's. Your problem will typically look nothing like path-finding at a first glance though, as in, you're not planning to "travel over a route". It's more abstract than that.

Then if you can use Dijkstra and you have some admissible heuristic (that's the hard part), you can use A*.

An often used technique for finding heuristics is dropping some constraint of your problem. For example, if you can teleport each tile to its destination regardless of whether there's already a tile there, it will take #displacements teleports. So there's the first heuristic. If you have to slide the tiles but they can slide through each other, the cost for each tile is the Manhattan distance to its destination. Then you can look at improving the heuristic, for example the Manhattan distance heuristic obviously ignores that tiles interfere with each other as they move, but there is a simple case where we know where tiles must conflict and use more moves: consider two tiles (pretend there are no other tiles) in the same row and their destinations are also on that row but in order to get there they'd have to pass through each other. They'd have to go around each other, adding two vertical moves. This gives the Linear Conflicts heuristic. Even more interference can be taken into account, for example with pattern databases.

Upvotes: 2

Related Questions