0
$\begingroup$

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex. In other words: $h(x) \leq d(x,dest)$, where $x$ is a some vertex and $dest$ is the destination vertex.

Besides the lower bound, I happen to know an upper bound for $d(x,dest)$. I was wondering if I could use this information to somehow speed up the A* search.

I appreciate any ideas that you might have. Thank you.

Improve this question
$\endgroup$
2
  • $\begingroup$ It of course depends on how good of an upperbound is provided. For example, if your algorithm always outputs the upperbound $n$ (where $n$ is the number of vertices of the graph), then it will be useless. $\endgroup$
    – Tony Huynh
    Nov 2, 2014 at 18:46
  • $\begingroup$ My upperbound is better than the trival one. Do you have an idea of how to incorporate it into the A* algorithm? $\endgroup$
    – real
    Nov 2, 2014 at 19:07

1 Answer 1

Reset to default
1
$\begingroup$

(The following may well have occurred to you already, but for completeness ...)

If I've fully understood the information that you have (and in context of A* pseudocode as you cited):

  1. At any given time, the set openset holds the nodes that are candidates to step off to. Each of these nodes has an f_score[] value, which is the lower bound you refer to in your question.

    (Intuitively, if I'm using A* to find the shortest path on a simple four-connected grid, my lower bound distance is the 'as the crow flies' distance, which is a lower bound to the 'follow the grid' distance.)

  2. The condition you add is that, from another source, you know that the distance from $x$ to $dest$ should be no more than some upper bound.

Consequently when adding nodes to the open set (openset), you could ignore nodes that have a distance to $dest$ that are greater than your supplied upper bound. As in

upperboundDistToDest = (Calculation of upper bound)

(... then in the appropriate place ...)

if neighbor not in openset and dist(neighbour, dest) < upperboundDistToDest 
    add neighbor to openset
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Patrick. I didn't think about it. It's a cool idea. I wonder if this is the best use of the upper bound information I have. In your answer, I assume that by dist(neighbour,dest) you mean my_lower_bound(neighbour,dest). $\endgroup$
    – real
    Nov 3, 2014 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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