4
$\begingroup$

The A* algorithm is some kind of an enhanced Dijkstra. Keep in mind that I want an optimal algorithm here and A* is optimal if the heuristic does not overestimate the distance to the goal.

The bidirectional case of A* is not as simple as the bidirectional Dijkstra as the finish condition is a bit tricky, of course you can manage to implement it if you work with "consistent potential functions" (see paper reference below).

Now to my question: when implementing a special distance estimate for A* (landmarks/ALT) this works also in the bidirectional case. In some papers they say one can change the active set of landmarks while the search is going on. This makes sense as the estimates will get better and still only a subset is involved for the estimate.

But will changing/improving the distance estimate while the search is going influence the optimality?

Unintuitive things can follow from this, e.g. a distance update to a node lowers the distance from source to this node but could increase the distance from this node to the goal due to the better distance estimate but I'm unsure if this violates the 'consistent potential' definition and could result in suboptimal paths. (E.g. in my latest trial to implement this I sometimes get suboptimal results but this could be also other bugs.)

The paper "Computing Point-to-Point Shortest Paths from External Memory" says I can do so but I'm unsure if I misunderstood something:

6.1 Restarting. As we shall see below, we sometimes need to change the way lower bounds are calculated in the middle of an ALT computation, e.g., by replacing the current potential functions p f and p r by another consistent pair.

$\endgroup$
1
$\begingroup$

I think I have found the answer in the paper and it is indeed not just a replacement of the potentials:

Now, if we want to replace p_f and p_r (forward and reverse potential) , all we need to do is change the keys of the labeled vertices for the two searches appropriately and update the priority queues containing these vertices. This takes time proportional to the number of labeled vertices at this point.

$\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.