heuristic function for shortest path

Question

I Want to find shortest path (between two red circles) with lowest cost (numbers in squares are cost in each step).

In the following picture with A* method can solve the problem But I don't have any idea about a promising heuristic function. Can anybody gives me a good heuristic function?

Answer 1

Since there's a 0, and you didn't state any restrictions on distribution, presumably there can be any number of 0s, thus potentially the cost to reach the target from any given point can be 0, thus, for an admissible heuristic, without looking around, you can only use h(x) = 0, which is Dijkstra's algorithm.

A slightly better, but still not very good, heuristic would be to simply take the minimum of the surrounding cells.

Anything else I can think of would either take too long to be useful, or would not guarantee getting to the target.

You can also consider running Dijkstra's algorithm from both points at the same time, you'll just have to be clever about when you stop.

---

If you're going to run multiple shortest path calculations on the same grid, you could consider preprocessing the grid to determine the lowest cost path consisting of n nodes, then use this in your heuristic, based on something like the Manhattan distance.

For your example, if n = 3, that would probably be 2-3-9, since 2+3+9 = 14 is the lowest sum of 3 neighbouring nodes I can see.

Then you can divide this by 3 (n) to get the cost of a single move, and calculate the Manhattan distance to the target (assuming only left, right, up and down moves, otherwise the calculation will be a little more complex), subtract 2 (n-1), and multiply by the cost of a single move as the heuristic.

We need to divide by n-1 since if the distance to the target is n-1, the cost to get there might be less than the calculated cost - consider the above example of 2-3-9 - if the remaining path were to be 2-3, we'd have a per-move cost of less than 14/3, so we need to ignore n-1 of the distance.

For your grid, the heuristic from the starting point will be:

h(x) = cost for single move * (change in x + change in y - (n-1))
     = 14/3 * (7 + 14 - 2)
     = 88.7

Answer 2

If starting point's location is (x, y) and the end point's location is (i, j), then the simple heuristic function can be ((x - i)^2 + (y - j)^2)^(1/2). Basically its Pythagoras theorem, you just track approximate distance to the end point, so moving to the opposite side will cost you more, so A* will check points closer to the end point first.