Критерии завершения двустороннего поиска

Согласно большей части чтения, которое я сделал, говорят, что двунаправленный алгоритм поиска заканчивается, когда границы "вперед" и "назад" сначала пересекаются. Однако в разделе 3.4.6 "Искусственный интеллект: современный подход", "Рассел" и "Норвиг":

Двунаправленный поиск реализуется путем замены теста цели на проверку, чтобы увидеть пересекаются ли границы двух поисков; если они это сделают, было найдено решение. Важно понимать, что первое найденное решение может быть не оптимальным, , даже если два поисковых запроса являются как по ширине; требуется дополнительный поиск, чтобы убедиться, что не является ярлыком в промежутке.

Я рассматривал это утверждение довольно давно, но не могу найти пример такого поведения. Может ли кто-нибудь представить примерный график, где первое пересечение между прямым и обратным границами двунаправленного BFS или * поиска не является самым коротким путем?

Изменить: Ясно, что BFS не найдет кратчайший путь в взвешенном графике. Похоже, что этот отрывок относится к двунаправленной BFS на неориентированном графе. Альтернативно, мне было бы интересно увидеть контрпример с использованием двунаправленного A * на взвешенном графике.

Ответ 1

Я не знаю, имел ли это в виду Рассел и Норвиг, но если граф взвешен (т.е. некоторые ребра длиннее других), кратчайший путь может иметь больше шагов, чем другой, который будет найден раньше BFS. Даже если количество шагов одинаковое, лучшее может быть найдено не первым; рассмотрим граф с шестью узлами:

(A- > B) = (A- > C) = 0

(B- > D) = 2

(C- > E) = 1

(D- > F) = (E- > F) = 0

После одного шага вперед от A и одного шага назад от F, передний фронт - {B, C}, а обратная граница - {D, E}. Теперь поисковик расширяет B и эй! Пересечение! (A- > B- > D- > F) = 2. Но он должен искать еще немного, чтобы обнаружить, что лучше (A- > C- > E- > F).

Ответ 2

В невзвешенном графике (удельная стоимость) двунаправленная BFS обнаружила оптимальное решение, когда оно попадает на пересечение, так как Рассел и Норвиг сами заявляют о себе на странице 80 выпуска 2003 года "AIMA":

Двунаправленный поиск реализуется путем проверки одного или обоих запросов каждым node до его расширения, чтобы увидеть, находится ли он в области другого дерева поиска [...] Алгоритм завершен и оптимальный (для равномерных затрат на шаг), если оба поиска имеют ширину в ширину [.]

( "Расширение a node", R & N означает создание преемников. Акцент добавлен.)

Ответ 3

Я думаю, что это связано с реализацией двунаправленного поиска.

Псевдокод для BFS выглядит примерно так:

until frontier.empty?
    node <- frontier.pop()
    add node to explored
    for each child not in expored or frontier:
        if child is goal then
            return path
        add child to frontier

Представьте себе реализацию двунаправленного поиска, например:

until frontierForward.emtpy? or frontierBackward.empty?
    node <- frontierForward.pop()
    add node to exploredForward
    for each child not in exporedForward or frontierForward:
        if child in frontierBackward then
            return pathForward + pathBackward
        add child to frontierForward

    Do something similar but now searching backwards

В основном, чередующиеся шаги "вперед" BFS и "назад" BFS. Теперь представьте себе такой график:

    B-C-D
  /       \
A           E
  \       /
    F - G

Первые обратные и обратные пробеги BFS дадут нам следующее состояние:

1) expandedForward = A ; frontierForward = B, F
2) expandedBackward = E ; frontierBackward = D, G

Теперь алгоритм выбирает следующий node для расширения с передней границы и выбирает B.

3) expandedForward = A, B ; frontierForward = F, C

Теперь мы запускаем обратную BFS и расширяем node D. D child, C, находится в передней границе, поэтому мы возвращаем путь A-B-C-D-E.

Я думаю, что это то, о чем говорят Рассел и Норвиг. Если реализация не учитывает этот сценарий, это может дать вам решение, которое не является оптимальным.

Он должен завершить расширение всех узлов на границе, которые имеют одинаковую глубину, прежде чем решить, что нашли оптимальное решение. Или, возможно, чередуйте поиск по BFS вперёд и назад по слою, а не по node (разверните все узлы в слое 0, разверните назад все узлы в слое 0, разверните все узлы в слое 1 и т.д.)