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

6.2.5. Итеративный поиск в глубину При ограниченном поиске в глубину сложность поиска зависит от выбора ограничения. Например, при поиске маршрута можно использовать не число всех населенных пунктов в районе поиска подходящего маршрута, а максимальное число населенных пунктов, которые могут встретиться на каждом из возможных маршрутов. Это число называют обычно радиусом поиска. Знание радиуса поиска приводит к более эффективному ограниченному поиску в глубину. Однако в большинстве задач радиус поиска не известен до тех пор, пока задача не будет решена. Итеративный поиск в глубину использует стратегию, основанную на итеративном применении ограниченного поиска в 143 6. Стратегии поиска Рис. 6.4. Итеративный поиск в глубину глубину сначала для радиуса поиска, равного 0, затем 2, после этого 3 и т.д. Четыре итерации такого поиска для бинарного дерева иллюстрирует рис. 6. 4. Итеративный поиск в глубину может показаться очень неэффективным, поскольку некоторые вершины просматриваются многократно. Однако для многих задач подавляющая доля вершин находится на низком уровне. Напомним, что оценка сложности по времени при ограниченном поиске в глубину вычисляется по формуле