Поиск дерева в глубину может застрять в бесконечном цикле, поэтому он не является «полным».Поиск в графе отслеживает уже найденные узлы, поэтому он может избежать бесконечных циклов.
«Избыточные пути» - это разные пути, которые ведут от одного начального узла к одному и тому же конечному узлу.Поиск в графике все еще будет исследовать все эти избыточные пути, но как только он достигнет узла, который он посещал ранее, он не пойдет дальше, но будет выполнять резервное копирование и искать другие пути, которые еще не пробовал.
Это отличается от "бесконечного цикла", который представляет собой путь, который ведет от узла к самому себе.
В ответ на ваш комментарий посмотрите на только что опубликованную цитату:
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 ветви.Каждая из этих ветвей ведет к одному и тому же узлу, который имеет длинный путь, ведущий из него.Поиск по дереву будет идти по этому длинному пути дважды , по одному разу для каждой из двух ветвей, которые к нему ведут.На это указывает автор.