Вопрос о полноте первой полноты и неполноте первой глубины

Question

Согласно Норвигу в AIMA (Искусственный интеллект: современный подход), алгоритм «Глубина в первую очередь» не завершен (не всегда приводит к решению), поскольку существуют случаи, когда нисходящее поддерево будет бесконечным.

С другой стороны, подход, основанный на ширине, называется полным, если коэффициент ветвления не бесконечен. Но разве это не то же самое, что и в случае бесконечного поддерева в DFS?

Нельзя ли сказать, что DFS завершена, если глубина дерева конечна? Как получается, что BFS завершена, а DFS - нет, поскольку полнота BFS зависит от конечного фактора ветвления!

Answer 1

Дерево может быть бесконечным, не имея бесконечного фактора ветвления.В качестве примера рассмотрим дерево состояний для кубика Рубика.Учитывая конфигурацию куба, существует конечное число ходов (я полагаю, 18, поскольку ход состоит из выбора одной из 9 «плоскостей» и вращения ее в одном из двух возможных направлений).Тем не менее, дерево бесконечно глубоко, поскольку вполне возможно, например, вращать одну и ту же плоскость поочередно назад и вперед (никогда не делая никакого прогресса).Чтобы предотвратить это, DFS обычно кэширует все посещенные состояния (эффективно сокращая дерево состояний) - как вы, вероятно, знаете.Однако, если пространство состояний слишком велико (или на самом деле бесконечно), это не поможет.

Я не изучал ИИ подробно, но я предполагаю, что обоснование для того, чтобы сказать, что BFS завершена, а DFS не является(полнота, в конце концов, просто термин, который где-то определен) заключается в том, что бесконечно глубокие деревья встречаются чаще, чем деревья с бесконечными факторами ветвления (поскольку наличие бесконечного фактора ветвления означает, что у вас есть бесконечное число вариантов выбора, которые, я считаю,не часто - игры и симуляции обычно бывают дискретными).Даже для конечных деревьев BFS, как правило, будет работать лучше, потому что DFS с большой вероятностью может начать с неправильного пути, исследуя большую часть дерева, прежде чем достичь цели.Тем не менее, как вы указали, в конечном дереве DFS в конечном итоге найдет решение, если оно существует.

Answer 2

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

Представьте себе странно определенное пространство состояний, в котором каждый узел имеет то же число преемников, что и следующий номер в последовательности Фибоначчи.Итак, он рекурсивно определен и, следовательно, бесконечен.Мы ищем узел 2 (отмечен зеленым на графике).Если DFS начинается с правой ветви дерева, потребуется бесконечное количество шагов, чтобы убедиться, что наш узел не существует.Поэтому он не завершен (он не закончится в разумные сроки).BFS найдет решение в 3-й итерации.

бесконечное пространство

Пространство состояний кубика Рубика конечно, оно огромно, но конечно (человек застрял в циклах, но DFS не будет повторять один и тот же ход дважды).DFS найдет очень неэффективный способ ее решения, иногда такое решение неосуществимо.Обычно мы считаем максимальную глубину бесконечной, но наши ресурсы (память) всегда конечны.