ОБЗОР АЛГОРИТМА УГЛУБЛЕННОГО ПОИСКА СВЯЗЕЙ

OVERVIEW OF THE DEPTH FIRST SEARCH ALGORITHM

Alina Abgaldaeva

Master student, Moscow State University of Technology "STANKIN", Russia, Moscow

Alexey Pushkin

Scientific adviser, Associate professor of the department information technologies and computer systems, Moscow State University of Technology "STANKIN", Russia, Moscow

Аннотация. В статье приводится обзор алгоритма углубленного поиска связей.

Abstract. This article is given an overview of the depth first search algorithm.

Ключевые слова: алгоритм углубленного поиска связей, DFS, путь, узел, дерево поиска.

Keywords: depth first search algorithm, path, node, search tree.

Введение

Алгоритм углубленного поиска связей или DFS - рекурсивный алгоритм обхода дерева или графовой структуры данных. Он получил такое название благодаря тому, что начинает свою работу с корневого узла и проходит каждый путь наибольшей глубины, прежде чем перейти к следующему пути [1].

Он использует стек данных для своей реализации, и его выполнение схоже с алгоритмом поиска в ширину [1].

Преимущества и недостатки

Преимущества:

1. Данный алгоритм требует небольших затрат памяти, его основное требование - это хранилище стека узлов пути от корневого узла до текущего узла;
2. Его работа занимает немного времени, чтобы достичь целевого узла чем у алгоритма поиска в ширину при прохождении по верному пути.

Недостатки:

1. Существует вероятность повторений некоторых шагов, что не гарантирует нахождения решения;
2. Данный алгоритм используется для глубокого поиска, и иногда это может привести к бесконечному циклу;

Пример действия алгоритма

На рисунке 1. изображено дерево поиска с помощью которого можно продемонстрировать последовательность поиска в глубину. Поиск будет происходить по следующему маршруту:

1. Корневой узел
2. Левый узел
3. Правый узел

Поиск начнется из узла S, и пересечет А, далее В, далее D и E, после пересечения Е, он вернется к дереву так, как узел Е не имеет другого преемника, и целевой узел по-прежнему не будет найден.

После обратного отслеживания он пересечет узел C, а затем G, и здесь он завершится, поскольку найдет целевой узел.

Рисунок 1. Дерево поиска

Характеристики алгоритма

Полнота алгоритма:

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

Временная сложность: Временная сложность алгоритма будет эквивалентна узлу, пройдутом алгоритмом. Она вычисляется по формуле ниже:

T(n)= 1+ n2+ n3 +.........+ nm=O(nm)

Где m = максимальная глубина любого узла, и ее значение может намного превышать d, где d - это глубина решения.

Сложность пространства: Алгоритм должен хранить только один путь от корневого узла, поэтому сложность пространства эквивалентна размеру набора периферий.

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