Полнота поиска по глубине - программирование

Я цитирую Искусственный интеллект: современный подход:

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

Я не понимаю, как можно выполнить поиск по графу, а поиск по дереву не будет, будучи деревом определенного графика.

Кроме того, я четко не понимаю разницу между "бесконечными циклами" и "избыточными путями"...

Может кто-нибудь мне это объяснит?

пс. Для тех, у кого есть книга, это страница 86 (3-е издание).

Ответ 1

Поиск дерева в глубину может застрять в бесконечном цикле, поэтому он не является "полным". Поиск по графику отслеживает узлы, которые он уже просматривал, поэтому он может избежать бесконечных циклов.

"Резервные пути" - это разные пути, которые ведут от одного и того же старта node к тому же концу node. Поиск по графику будет по-прежнему исследовать все эти избыточные пути, но как только он достигнет node, который он посетил раньше, он больше не пойдет, но будет резервным копировать и искать дополнительные пути, которые он еще не пробовал.

Это отличается от "бесконечного цикла", который является путем, который ведет от node к себе.

В ответ на ваш комментарий просмотрите цитату, которую вы только что опубликовали:

Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node.

Таким образом, хотя поиск по дереву глубины сначала отслеживает путь от корня до текущего node, чтобы избежать бесконечных циклов, он должен выполнять линейный поиск по этому пути каждый раз, когда он посещает новый node, Если вы написали реализацию дерева поиска по глубине, который не выполнял эту проверку, он мог попасть в бесконечный цикл.

Вы правы, что в книге говорилось о "распространении избыточных путей", не относится к полноте. Это просто указывает на разницу между графиком и деревом. Поскольку поиск по дереву только отслеживает текущий путь, он может работать один и тот же путь более одного раза в одном и том же поиске (даже если вы делаете проверку, о которой я только что упомянул).

Скажите, что ваш корень node имеет 2 ветки. Каждая из этих ветвей ведет к одному синглу node, который имеет длинный путь, ведущий от него. Поиск дерева будет следовать за этим длинным путем дважды, один раз для каждой из 2 ветвей, которая ведет к нему. Это то, что автор указывает.