Я никогда не видел обсуждения двунаправленного поиска в ширину (которое я буду сокращать как bidi-BFS) - это то, как точно выполнять поиск с обоих концов одновременно. Некоторые варианты:
- Буквально использовать два отдельных потока. На самом деле это может сильно замедлить работу, если это означает, что вам придется переключиться на некоторые причудливые параллельные структуры данных для их координации. (Или, может быть, это действительно выходит нормально. Никогда не пробовал.) Мы могли бы избежать этого, убедившись, что потоки сменяют друг друга, но тогда зачем вообще использовать два потока?
- Используйте один поток, и алгоритмы включаются по очереди. эта нить. Но насколько велик «поворот»? (На самом деле мы могли бы придерживаться двух потоков, которые сменяют друг друга, и мы все равно должны ответить на один и тот же вопрос.) Некоторые идеи:
- Ход - это полный «уровень». То есть мы ищем все на расстоянии k от
src, затем на расстоянии k от dst, затем k + 1 от src, затем k + 1 от dst, et c. - Или мы могли бы иметь более мелкозернистые повороты. Например, мы ставим в очередь соседство узла, который в настоящее время находится в начале очереди для «прямого поиска» (из
src), затем мы переключаемся на «обратный поиск» (из dst) и так далее. Другими словами, каждый ход мы удаляем ровно один узел из очереди, которую поддерживает BFS, и выполняем всю работу, связанную с этим узлом. (Этот, вероятно, самый простой для кодирования, потому что вы можете просто взять внутренний l oop обычного BFS и назвать его одним «шагом».) - Мы можем быть даже более детализированными, чем это . Мы можем переключиться после того, как текущий поиск совершит определенный «прогресс», такой как прохождение ровно 100 ребер (что приведет к постановке в очередь менее 100 узлов, если в поиске не обнаружены дубликаты).
- В конце концов, мы можем получить такую мелкую детализацию, что начинаем чувствовать себя глупо: каждый ход - это «инструкции по сборке X», или, возможно, «тактовые циклы Y», или даже «миллисекунды Z». * Теперь, если график имеет довольно правильную форму, все эти вариации будут давать похожие результаты, и все это не имеет большого значения. Но предположим, что граф является каким-то «бугристым» в том смысле, что мы иногда видим узлы с большим количеством соседей, а иногда видим узлы с очень небольшим числом. Тогда мне кажется, что та же интуиция, которая говорит, что двунаправленная BFS лучше, чем обычная BFS, должна привести к выводу, что более мелкозернистая поворотная обработка лучше, чем более крупная поворотная обработка. (Например, если к моменту встречи двух параллельных поисков выяснится, что прямой поиск прошел в десять раз больше ребер, чем обратный поиск, то очень вероятно, что если бы мы каким-то образом «одобрили» обратный поиск больше , мы бы сделали меньше ВСЕГО работы.)
Теперь, возможно, другие факторы, такие как простота кодирования или накладные расходы на переключение, имеют большее значение, чем это, но: при прочих равных, я прав, что мелкозернистый всегда лучше или, по крайней мере, никогда не хуже? Или есть какой-то другой фактор, которым я пренебрегаю?