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
    Commented 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
    Commented 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
    Commented Nov 3, 2014 at 10:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .