Полнота поиска в глубину

Question

Цитирую Artificial Intelligence: A Modern Approach:

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

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

Кроме того, я не ясно получить разницу между «зацикливания» и «избыточных путей» ...

мая кто-то объяснить это мне?

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

Answer 1

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

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

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

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

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.

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

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

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