1
$\begingroup$

Looking for information on choosing a heuristic for instances where the cost of traversing an edge can be less than one.

For example, say movement is allowed in the cardinal directions. Should all edge costs be at least one, then I would consider diagonal distance. However, if costs can be less than one, this could lead to an instance where diagonal distance will be an overestimate and thus is not an admissible heuristic.

My thought on the matter is perhaps to find the smallest possible cost and figure out a constant to divide diagonal distance by to guarantee it will never overestimate?

Would appreciate some guidance or some resources to look further into this.

$\endgroup$
  • $\begingroup$ Can you given a simple example of the situation such as 2 rows of edges by 2 or 3 columns of edges? $\endgroup$ – Apass.Jack Jan 16 at 5:13
  • $\begingroup$ Sure, say [[G, 1, 1, 1], [1, .5, 1, 1], [1, 1, .5, 1], [1, 1, 1, S]] where S is start and G is goal. Clearly the least expensive path is along the diagonals, the .5's, but diagonal distance will overestimate the cost of this path. $\endgroup$ – cadence Jan 16 at 5:18
  • $\begingroup$ I'm confused, you say you can only move across cardinal directions but you're also talking about moving diagonally? $\endgroup$ – RcnSc Jan 16 at 10:00
3
$\begingroup$

The simple options are to either multiply all path costs such that minimum cost is 1. Or multiply the heuristic such that the min cost is more or equal than the heuristic tells you for the same path.

The more complicated option is to look at the graph and estimate the chance that you will end up going through the low cost area. This requires some precalculation of the low cost areas and their influence on paths.

For example a low cost highway, any heuristic that is close to it will need to get a bonus to account for taking the highway. But heuristics that are not going to take the highway can use the larger estimation.

$\endgroup$
1
$\begingroup$

I don't know how helpful diagonal distances actually are here.

You could figure out the minimum cost of any edge, and then multiply the Manhattan distance (vertical difference plus horizontal difference) by that.

It would be better (give you a tighter lower bound) to figure out the minimum cost of any vertical edge, and then multiply the vertical component of the distance between source and target by that, do the same for horizontal edges, and then add the (separately) weighted horizontal and vertical distances together.

If your graph is grid-shaped, it would be better still to figure out, in a preprocessing step, for each column $x$ of parallel horizontal edges, what the minimum weight is of any edge in that column, and store this in $h[x]$. Then for each row $y$ of parallel vertical edges, figure out the minimum weight of any edge in that row, and store that in $v[y]$. Then for source and target at $(x_s, y_s)$ and $(x_t, y_t)$, respectively, $\sum_{i=x_s}^{x_t} h[i] + \sum_{j=y_s}^{y_t} v[j]$ is a lower bound on the distance from source to target. (You can even compute this in constant time, by building a list of partial sums for each direction during preprocessing, and subtracting: e.g. if you have precomputed $H[a] = \sum_{b=1}^{b=a} h[i]$, then $\sum_{i=x_s}^{x_t} h[i] = H[x_t] - H[x_s - 1]$.) Rationale: Any path from source to target must cross each of those rows and columns somehow, and you can't do better than by using the least-cost edge to do so in each case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.