What are some good methods to finding a heuristic for the A* algorithm?

algorithm graph heuristics shortest-path a-star
user1234 picture user1234 · Apr 16, 2011 · Viewed 34.4k times · Source

You have a map of square tiles where you can move in any of the 8 directions. Given that you have function called cost(tile1, tile2) which tells you the cost of moving from one adjacent tile to another, how do you find a heuristic function h(y, goal) that is both admissible and consistent? Can a method for finding the heuristic be generalized given this setting, or would it be vary differently depending on the cost function?

Answer

Drahakar picture Drahakar · Apr 16, 2011

Amit's tutorial is one of the best I've seen on A* (Amit's page). You should find some very useful hint about heuristics on this page .

Here is the quote about your problem :

On a square grid that allows 8 directions of movement, use Diagonal distance (L∞).

Related questions

Good Java graph algorithm library?

Has anyone had good experiences with any Java libraries for Graph algorithms. I've tried JGraph and found it ok, and there are a lot of different ones in google. Are there any that people are actually using successfully in production …

Read More
What is the maximum number of edges in a directed graph with n nodes?

What is the maximum number of edges in a directed graph with n nodes? Is there any upper bound?

Read More
How to trace the path in a Breadth-First Search?

How do you trace the path of a Breadth-First Search, such that in the following example: If searching for key 11, return the shortest list connecting 1 to 11. [1, 4, 7, 11]

Read More