6
$\begingroup$

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*.

So let $l(u,v)$ be length of the (oriented) edge $u,v$, $\pi_f(v)$ the potential of vertex $v$ in forward search and $\pi_r(v)$ potential of vertex $v$ in reverse search and $d(u,v)$ length of the shortest path from $u$ to $v$. Let $s$ be start vertex, $t$ goal vertex. The algorithm selects vertices by $d(s,v)+\pi_f(v)$ forward and $d(v,t)+\pi_r(v)$ reverse.

Let's call $\mu$ the length of the shortest path found so far, $n_f$ the vertex on top of forward queue and $n_r$ the vertex on top of reverse queue. I found two ways

  1. The obvious option is to stop forward when $d(s,n_f)+\pi_f(n_f)\geq\mu$ and reverse when $d(n_r,t)+\pi_r(n_r)\geq\mu$. It is also not needed to process edges that were already processed in the other direction. Here the $\pi_f$ and $\pi_r$ are independent can be very specific, but the algorithm may need to continue quite long after the shortest path was actually found if the potential function is significantly underestimating.

  2. Create a pair of consistent potential functions as defined in this lecture. The requirements are given as $$\pi_f(u) + \pi_r(u) == \pi_f(v) + \pi_r(v)$$ for each edge $u,w$ (which really means the sum has to be constant over the whole graph). Without loss of generality we can make $\pi_r(v) = -\pi_f(v)$ and use the normal stopping condition from non-goal-directed search expressed as $$d(s,m_f)+\pi_f(m_f) + d(m_r,t)+\pi_r(m_r) \geq \mu+\pi_r(t)$$ (assuming we shift $\pi$ so that $\pi_f(s) = 0$).

    This allows easier stop, but the potential function has to only indicate whether $v$ is closer to start or goal and for vertex (equally) far from both will be the same as for vertex in the middle of the shortest path. Therefore it will be less specific.

Now what I am looking for is:

  1. anything that would give me idea which would be more efficient (without having to implement both and test them) and
  2. whether the second can even be used if the heuristics is not monotonous, i.e. when $d(u,v) - \pi_f(u) + \pi_f(v) \ge 0$ does not hold (the linked lecture assumes that, but not doing so could save me a lot of data and I/O is a bottleneck, so I would prefer not to even though it means occasionally having to reprocess vertex).

1Some important optimization techniques can only be applied to bidirectional search.

$\endgroup$
  • 1
    $\begingroup$ I guess starting multiple instances of Dijkstra is not efficient enough for you, then? $\endgroup$ – Raphael Jul 28 '14 at 20:45
  • $\begingroup$ @Raphael: What good would multiple instances of Dijkstra do for searching a single path between two points? $\endgroup$ – Jan Hudec Jul 29 '14 at 8:08
  • $\begingroup$ Start one run in $s$, the other in $t$, and execute them in an interleaved fashion. You get a shortest path when they first meet. $\endgroup$ – Raphael Jul 29 '14 at 9:51
  • 2
    $\begingroup$ @Raphael: Except it's not true that "when they first meet", which is what the question is about. For Dijkstras it is when $d(s,m_f)+d(m_t,t)\geq\mu$, which I know. But when I want A*, the more general algorithm, there are two ways to construct it, yielding different stopping conditions. And that's what I am asking about. $\endgroup$ – Jan Hudec Jul 29 '14 at 10:03

Your Answer

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

Browse other questions tagged or ask your own question.