Итеративный поиск в глубину
В компьютерных науках итеративный поиск с углублением или, более конкретно , итеративный поиск с углублением в глубину [2] (IDS или IDDFS) представляет собой стратегию поиска в пространстве состояний /графе, в которой ограниченная по глубине версия поиска в глубину запускается многократно с увеличением глубины . ограничения, пока цель не будет найдена. IDDFS оптимальна, как и поиск в ширину , но использует гораздо меньше памяти; на каждой итерации он посещает узлы в дереве поиска в том же порядке, что и поиск в глубину, но кумулятивный порядок, в котором узлы впервые посещаются, фактически является в ширину. [1]
В следующем псевдокоде показана IDDFS, реализованная в терминах рекурсивной DFS с ограниченной глубиной (называемой DLS) для ориентированных графов . Эта реализация IDDFS не учитывает уже посещенные узлы и поэтому не работает для неориентированных графов .
Если целевой узел найден, то DLS раскручивает рекурсию, возвращаясь без дальнейших итераций. В противном случае, если хотя бы один узел существует на этом уровне глубины, оставшийся флаг позволит продолжить работу IDDFS .
2-кортежи полезны в качестве возвращаемого значения, чтобы сигнализировать IDDFS о продолжении углубления или остановке, в случае, если глубина дерева и членство в цели заранее неизвестны . В другом решении вместо этого можно было бы использовать контрольные значения для представления не найденных или оставшихся результатов уровня.
IDDFS сочетает в себе эффективность поиска в глубину и полноту поиска в ширину (когда коэффициент ветвления конечен). Если решение существует, оно найдет путь решения с наименьшим количеством дуг. [3]
Поскольку итеративное углубление посещает состояния несколько раз, это может показаться расточительным, но оказывается не таким затратным, поскольку в дереве большинство узлов находится на нижнем уровне, поэтому не имеет большого значения, если верхние уровни посещаются несколько раз. раз. [4]
