I am using [A\*](http://en.wikipedia.org/wiki/A*_search_algorithm) (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.



Using upper bound information in graph search
(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](http://en.wikipedia.org/wiki/A*_search_algorithm#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

```

