Искусственный интеллект

142 6.2. Слепой поиск Требования к объему памяти при поиске в глубину существенно меньше, чем при поиске в ширину. Как видно из рис. 6. 3, в памяти необходимо хранить все вершины, инцидентные вершинам на пути из корневой вершины к любой другой, соседние вершины которой рассматриваются. Очевидно, что при степени ветвления / и глубине дерева к оценка сложности по памяти при поиске в глубину равна О(1к). Оценка сложности по времени для поиска в глубину остается такой же, как и при поиске в ширину, а именно О(1к). Для задач, дерево поиска для которых конечно, а число целей сравнительно невелико, поиск в глубину может оказаться эффективным, так как имеет шанс найти это небольшое число целей без просмотра всех вершин. Для задач, имеющих большую или даже бесконечную глубину дерева, поиск в глубину может оказаться крайне неэффективным, так как будет стремиться все время в глубину, в то время как цель может оказаться близкой к корню дерева, но на том пути, который еще не был просмотрен. Поиск же все время уходит вниз и в случае бесконечной глубины дерева может никогда не вернуться назад к просмотру вершин, среди которых находятся целевые. Вследствие этого следует избегать использования поиска в глубину для решения задач с большой или бесконечной глубиной дерева. Поиск в глубину, таким образом, нельзя считать ни полным, ни оптимальным.