Полнота поиска в глубину
Я цитируюИскусственный интеллект: современный подход:
Свойства поиска в глубину сильно зависят от того, используется ли версия для поиска в графе или в виде дерева. Версия для поиска в графе, которая позволяет избежать повторяющихся состояний и избыточных путей, завершена в конечных пространствах состояний, потому что она в конечном итоге расширит каждый узел. Версия поиска по дереву, с другой стороны,не полный [...]. Поиск по дереву в глубину можно изменить без дополнительных затрат памяти, чтобы он сравнивал новые состояния с теми, которые находятся на пути от корня к текущему узлу; это позволяет избежать бесконечных циклов в конечных пространствах состояний, но не предотвращает распространение избыточных путей.
Я не понимаю, как поиск по графу может быть полным, а поиск по дереву не может быть, будучи деревом, как определенный граф.
Кроме того, я не вижу четкой разницы между «бесконечными циклами» и «избыточными путями» ...
Может кто-нибудь объяснить это мне?
пс. Для тех, у кого есть книга, это страница 86 (3-е издание).