Критерии завершения для двунаправленного поиска - PullRequest
Новая
       15

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

23 голосов
/ 23 ноября 2010

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

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

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

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

Ответы [ 4 ]

8 голосов
/ 12 января 2013

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

Псевдокод для 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

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

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

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

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

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

6 голосов
/ 27 июля 2014

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

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

(«Расширяя узел», R & N означает создание преемников. Выделение добавлено.)

5 голосов
/ 23 ноября 2010

Я не знаю, имел ли это в виду Рассел и Норвиг, но если график взвешенный (то есть некоторые ребра длиннее других), путь кратчайший может иметь больше шагов, чем другой который будет найден раньше в 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) лучше.

0 голосов
/ 15 сентября 2018

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

, но очевидно, что 2 сегмента из 6 + 6 хуже, чем один сегмент длиной 10.

...