algorithm - heuristic function for shortest path -

i want find shortest path (between 2 red circles) lowest cost (numbers in squares cost in each step).

in following picture a* method can solve problem don't have idea promising heuristic function. can gives me heuristic function?

since there's 0, , didn't state restrictions on distribution, presumably there can number of 0s, potentially cost reach target given point can 0, thus, admissible heuristic, without looking around, can use h(x) = 0, dijkstra's algorithm.

a slightly better, still not good, heuristic take minimum of surrounding cells.

anything else can think of either take long useful, or not guarantee getting target.

you can consider running dijkstra's algorithm both points @ same time, you'll have clever when stop.

---

if you're going run multiple shortest path calculations on same grid, consider preprocessing grid determine lowest cost path consisting of n nodes, use in heuristic, based on manhattan distance.

for example, if n = 3, 2-3-9, since 2+3+9 = 14 lowest sum of 3 neighbouring nodes can see.

then can divide 3 (n) cost of single move, , calculate manhattan distance target (assuming left, right, , down moves, otherwise calculation little more complex), subtract 2 (n-1), , multiply cost of single move heuristic.

we need divide n-1 since if distance target n-1, cost there might less calculated cost - consider above example of 2-3-9 - if remaining path 2-3, we'd have per-move cost of less 14/3, need ignore n-1 of distance.

for grid, heuristic starting point be:

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