1
$\begingroup$

I tried posting this on stack overflow and it got no takers, decided to cross post here:

One thing that I've never seen discussed about bidirectional breadth-first-search (which I'll abbreviate as bidi-BFS) is how exactly to search from both ends at once. Some options:

  1. Literally use two separate threads. This might actually slow things down terribly if it means you have to switch to some fancy concurrent data structures to coordinate them. (Or maybe it actually comes out ok. Never tried.) We could avoid this by making sure the threads take turns, but then why bother with using two threads?
  2. Use one thread, and the algorithms take turns on that thread. But how big is a "turn"? (Actually we could stick with two threads that take turns, and we still have to answer the exact same question.) Some ideas:
    • A turn is a full "level". That is, we search everything at distance k from src, then distance k from dst, then k+1 from src, then k+1 from dst, etc.
    • Or we could have more "fine-grained" turns. For instance, we enqueue the neighborhood of the node that's currently at the front of the queue for the "forward search" (from src), then we switch to the "backward search" (from dst) and so on. In other words, each turn, we dequeue exactly one node from the queue that BFS maintains, and do all the work associated with that node. (This one is probably the simplest to code, because you can simply take the inner loop of an ordinary BFS and call it one "step".)
    • We can be even more fine-grained than that. We can switch after the current search makes a certain amount of "progress", such as traversing exactly 100 edges (which will result in enqueueing less than 100 nodes, unless there are no duplicates encountered in the search).
    • Eventually we can get so fine grained that we start feeling silly: each turn is "X assembly instructions", or perhaps "Y clock cycles" or even "Z milliseconds".

Now, if the graph has a fairly regular shape, than all these variations will tend to produce similar results, and none of this matters much. But suppose the graph is somehow "lumpy" in that we sometimes see nodes with many neighbors, and sometimes see nodes with very few. Then it seems to me that the same intuition that says bidi-BFS is better than plain BFS should lead to the conclusion that finer-grained turned taking is better than larger-grained turn taking. (For example, if by the time the two parallel searches meet, it turns out that the forward search had traversed ten times as many edges as the reverse search, then it seems very likely that if we had somehow "favored" the reverse search more, we would have done less TOTAL work.)

Now, it could be that other factors such as ease of coding or overhead of switching matter more than this stuff, but: all else being equal, am I right that finer-grained is always better, or at least never worse? Or is there some other factor I'm neglecting?

$\endgroup$
6
  • 2
    $\begingroup$ Or perhaps this belongs more on CS stack exchange rather than here; hm... $\endgroup$ – Mark VY Aug 7 '20 at 18:16
  • $\begingroup$ Please do not post the same question on multiple sites. I suggest you pick one site where you want it to appear, and delete the other copies. I don't think this question is one of theoretical CS; it appears to be more pragmatically oriented. $\endgroup$ – D.W. Aug 7 '20 at 22:11
  • $\begingroup$ Okay; should I delete it from here then? $\endgroup$ – Mark VY Aug 8 '20 at 1:05
  • 1
    $\begingroup$ I just tried implementing one of the variations, and when I ran it, I realized that the only way for this to be a pure optimization of "plain" BFS is to use "level-at-time" searching; else the path found might well be longer than the one BFS would find. oops. $\endgroup$ – Mark VY Aug 8 '20 at 3:37
  • 1
    $\begingroup$ Sorry to say this but I think your question is right in the core of research in bidirectional search. I do highly recommend you looking for papers by Ariel Felner, Mike Barley or even myself about bidirectional search. You will se that we discuss option 2 quite in depth. Recently, Vidal Alcazar has published another work in AAAI'20 where he discusses the pros and cons of various approaches $\endgroup$ – Carlos Linares López Aug 19 '20 at 13:47

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.