Вопрос о полноте первой полноты и неполноте первой глубины
Согласно Норвигу в AIMA (Искусственный интеллект: современный подход), алгоритм "Глубина в первую очередь" не является полным (не всегда дает решение), поскольку существуют случаи, когда нисходящее поддерево будет бесконечным.
С другой стороны, подход шириной в первую очередь считается полным, если коэффициент ветвления не бесконечен. Но разве это не то же самое, что и в случае бесконечного поддерева в DFS?
Нельзя ли сказать, что DFS завершена, если глубина дерева конечна? Как получается, что BFS завершена, а DFS нет, поскольку полнота BFS зависит от конечного фактора ветвления!
2 ответа
Дерево может быть бесконечным, не имея бесконечного фактора ветвления. В качестве примера рассмотрим дерево состояний для кубика Рубика. Учитывая конфигурацию куба, существует конечное число ходов (я полагаю, 18, поскольку ход состоит из выбора одной из 9 "плоскостей" и вращения ее в одном из двух возможных направлений). Тем не менее, дерево бесконечно глубоко, поскольку вполне возможно, например, вращать одну и ту же плоскость поочередно назад и вперед (никогда не делая никакого прогресса). Чтобы предотвратить это, DFS обычно кэширует все посещенные состояния (эффективно сокращая дерево состояний) - как вы, вероятно, знаете. Однако, если пространство состояний слишком велико (или фактически бесконечно), это не поможет.
Я не очень подробно изучал ИИ, но я предполагаю, что обоснование для того, чтобы сказать, что BFS является полным, а DFS - нет (в конце концов, полнота - это просто термин, который где-то определен) состоит в том, что бесконечно глубокие деревья встречаются чаще, чем деревья с бесконечным факторы ветвления (поскольку наличие бесконечного фактора ветвления означает, что у вас есть бесконечное количество вариантов, что, я считаю, не является распространенным - игры и симуляции обычно дискретны). Даже для конечных деревьев BFS, как правило, будет работать лучше, потому что DFS с большой вероятностью может начать с неверного пути, исследуя большую часть дерева, прежде чем достичь цели. Тем не менее, как вы указываете, в конечном дереве DFS в конечном итоге найдет решение, если оно существует.
DFS не может застрять в циклах (если у нас есть список открытых и закрытых состояний). Алгоритм не является полным, поскольку он не находит решения в бесконечном пространстве, хотя решение находится в глубине d что намного ниже бесконечности.
Представьте себе странно определенное пространство состояний, в котором каждый узел имеет то же число преемников, что и следующий номер в последовательности Фибоначчи. Итак, он рекурсивно определен и, следовательно, бесконечен. Мы ищем узел 2 (отмечен зеленым на графике). Если DFS начинается с правой ветви дерева, потребуется бесконечное количество шагов, чтобы убедиться, что наш узел не существует. Поэтому он не завершен (он не закончится в разумные сроки). BFS найдет решение в 3-й итерации.
Пространство состояний кубика Рубика конечно, оно огромно, но конечно (человек застрял в циклах, но DFS не будет повторять один и тот же ход дважды). DFS найдет очень неэффективный способ ее решения, иногда такое решение неосуществимо. Обычно мы считаем максимальную глубину бесконечной, но наши ресурсы (память) всегда конечны.
Свойства поиска в глубину сильно зависят от того, какой вариант используется: поиск по графу или поиск по дереву. Версия с поиском по графу, которая избегает повторяющихся состояний и избыточных путей, завершена в пространствах конечных состояний, потому что в конечном итоге она расширит каждый узел. Версия с поиском по дереву, с другой стороны, не является полной - например, на рис. 3.6 алгоритм будет следовать циклу Арад – Сибиу – Арад – Сибиу навсегда. 
Источник: AI: современный подход