6.2.5. Итеративный поиск в глубину

При ограниченном поиске в глубину сложность поиска зависит от выбора ограничения. Например, при поиске маршрута можно использовать не число всех населенных пунктов в районе поиска подходящего маршрута, а максимальное число населенных пунктов, которые могут встретиться на каждом из возможных маршрутов. Это число называют обычно радиусом поиска. Знание радиуса поиска приводит к более эффективному ограниченному поиску в глубину. Однако в большинстве задач радиус поиска не известен до тех пор, пока задача не будет решена. Итеративный поиск в глубину использует стратегию, основанную на итеративном применении ограниченного поиска в

Рис. 6.4. Итеративный поиск в глубину

глубину сначала для радиуса поиска, равного 0, затем 2, после этого 3 и т.д. Четыре итерации такого поиска для бинарного дерева иллюстрирует рис. 6. 4.

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

Например, для будем иметь При итеративном поиске на глубину к вершины глубины к просматриваются один раз, глубины — два раза, глубины — три и т.д. Корневая вершина просматривается к раз. Таким образом, оценка сложности по времени при итеративном поиске в глубину вычисляется по формуле

Для будем иметь . По сравнению с оценкой сложности по времени для ограниченного поиска в глубину сложность по времени для итеративного поиска в глубину возросла только на 11%. Из формулы, приведенной выше, видно, что чем выше степень ветвления, тем ниже доля сложности, получающейся за счет повторного просмотра вершин. Но даже для случая, когда сложность по времени итеративного поиска в глубину только в два раза превосходит сложность по времени простого поиска в глубину. Это означает, что оценка сложности по времени

итерационного поиска в глубину по-прежнему равна а сложность по памяти Итеративный поиск в глубину достаточно хорошо себя зарекомендовал для задач с большим пространством поиска и неизвестной его глубиной.

6.2.6. Двунаправленный поиск

Идея двунаправленного поиска основана на использовании сразу двух стратегий — прямого поиска от корневой вершины и обратного от целевой вершины. Процесс поиска прекращается, когда оба этих процесса встретятся на середине глубины. Если считать, что степень ветвления при прямом и обратном поиске одинакова, то оценка сложности по времени двунаправленного поиска будет Эта оценка существенно лучше, чем аналогичная для рассмотренных стратегий поиска. Однако все это в идеале, т.е. при условии, что цель только одна, степень ветвления и сложность нахождения последователей и предшественников одна и та же. При решении практических задач, однако, это условие может нарушаться. Кроме этого могут возникать и другие проблемы. Например, установление факта появления одной и той же вершины в той и другой половине поиска может потребовать значительных усилий и составить значительную долю сложности. Если все эти проблемы можно решить за постоянное время, не зависящее от числа вершин, то оценка сложности по времени двунаправленного поиска останется равной

6.2.7. Сравнение стратегий поиска

Характеристики шести рассмотренных стратегий, где — степень ветвления, к — глубина поиска, максимальная глубина дерева поиска, — ограничение на глубину поиска, сведены в табл. 6.2.

Таблица 6.2 (см. скан)