Антон Тмур

Наставник курса "Алгоритмы и структуры данных"

В алгоритмических задачах на графах мы часто используем четыре известных алгоритма. Два из них — это алгоритмы обхода графа: Поиск в ширину и Поиск в глубину. Ещё два, A* и алгоритм Дейкстры, используются для нахождения оптимального пути внутри графа от одного узла до другого.

Я покажу, что все эти четыре алгоритма — это по сути один и тот же алгоритм. И вся разница между ними — только в разных структурах данных, используемых для хранения непосещённых узлов графа.

Задачка для примера

Сначала рассмотрим задачу поиска пути в небольшом простом графе:

Двигаясь от узла к узлу, мы хотим найти путь от start до target.

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

Тот самый один алгоритм

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

Помимо текущего узла нам нужно где-то хранить ещё не посещённые узлы, куда можно перейти на следующей итерации. Это узлы, которые мы уже встречали как соседей, но не рассматривали в качестве текущего. Хранить такие узлы будем в специальном хранилище, которое назовём nodes_storage.

Для текущего узла всегда проверяем, является ли он целевым. Если да, значит мы прибыли: путь от start до target найден, и алгоритм поиска может быть прерван. В противном случае мы должны рассмотреть узлы, соседние с текущим, и добавить их в хранилище nodes_storage.

Чтобы не запутаться и не ходить по одним и тем же узлам несколько раз, мы будем раскрашивать узлы графа следующим образом:

• белый —  мы ещё не посещали и даже не встречали этот узел;

• серый —  мы встречали этот узел в качестве соседа и уже добавили его в nodes_storage, но ещё не посещали его;

• чёрный  —  этот узел посещён и больше не нуждается в анализе.

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

Важно отдельно рассмотреть случай, если сосед текущего узла имеет цвет, отличный от белого; то есть мы встречаем этот узел уже не в первый раз. Это означает, что мы уже приходили в узел по другому пути, и теперь нужно решить, какой из путей нам подходит больше. Поскольку зачастую мы хотим найти кратчайший путь, то конфликт решается просто: нужно выбрать путь с кратчайшим расстоянием до этого узла от start.

Переходим к коду

Когда мы описали алгоритм в общих чертах, пришло время погрузиться в код — напишем этот алгоритм на языке Python.

Пока мы не будем прямо указывать структуру данных для хранения непосещённых узлов, назвав её AbstractNodeStorageClass. Нам нужно только знать, что этот класс содержит три метода: insert  —  для добавления узла в хранилище, get_first  —  для извлечения одного элемента из хранилища и is_empty  — для проверки, не опустело ли хранилище.

Получается вот такой код:

def find_path(
        graph: Graph,
        start_node: int,
        target_node: int,
        nodes_storage_structure_name: AbstractNodeStorageClass,
    ) -> bool:
    """
        Универсальный алгоритм обхода графа в поисках пути между 
        начальным (start) и целевым (target) узлами, используя 
        структуру графа и вспомогательную структуру nodes_storage.
        Возвращает True, если путь найден.
    """

    # красим все узлы в белый
    color = ['white'] * graph.number_of_nodes()  
    # в начале поиска расстояние до всех узлов кроме начального равны ∞
    dist = [float('Inf')] * graph.number_of_nodes()
    dist[start_node] = 0

    # положим start_node внутрь nodes_storage
    nodes_storage.insert(start_node)

    # цикл пока внутри nodes_storage есть узлы
    while not nodes_storage.is_empty():
        current_node = nodes_storage.get_first()

        if current_node == target_node:
            # конец поиска, целевой узел найден, а значит и путь до него
            return True

        # возьмём всех соседей текущего узла
        neighbours = list(graph.adj[current_node])
        for node_to_go in neighbours:
            # если этот узел встречается впервые
            if color[node_to_go] == 'white':
                # красим его в серый
                color[node_to_go] = 'grey'   

                # обновляем расстояние от стартового узла
                dist[node_to_go] = dist[current_node] + \
                  graph.get_edge_data(node_to_go, current_node)['weight']
                
                # добавляем узел в nodes_storage
                nodes_storage.insert(node_to_go)  
            else:
                # иначе нам нужно решить конфликт дублирования (два пути 
                # к одному узлу). Выбираем из двух путей более короткий.
                weight_from_current_node = graph.get_edge_data(node_to_go, current_node)['weight']
                if dist[current_node] + weight_from_current_node < dist[node_to_go]:
                    dist[node_to_go] = dist[current_node] + weight_from_current_node

        # красим текущий узел в чёрный, он нам больше не интересен
        color[current_node] = 'black'
    return False

Вот и всё! Это единственный алгоритм, который нам понадобится. Подставляя разные структуры данных в качестве хранилища, мы получим разные классические алгоритмы поиска пути в графе.

Поиск в глубину

Если мы используем стек в качестве хранилища непосещённых узлов, то описанный выше алгоритм превращается в Поиск в глубину.

Давайте проверим. Возьмём класс, который реализует хранение непосещённых узлов по принципу стека. То есть метод get_first возвращает элемент, добавленный последним:

class Stack(AbstractNodeStorageClass):
    """
        Стек работает по принципу LIFO - первым возвращается 
        последний добавленный элемент.
    """
    def __init__(self):
        self.nodes = []

    def get_first(self):
        return self.nodes.pop()

    def insert(self, node_number):
        self.nodes.append(node_number)

    def is_empty(self):
        return len(self.nodes) == 0

Результат использования этого класса показан ниже. На каждой итерации мы копаем как можно глубже в поисках целевого узла.

Чтобы поиграть в этой анимации с кнопками управления, жми сюда.

Поиск в ширину

Чтобы выполнить Поиск в ширину, нужно вместо стека использовать очередь:

class Queue(AbstractNodeStorageClass):
    """
        Очередь работает по принципу FIFO - первым возвращается 
        элемент, добавленный раньше всех.
    """

    def __init__(self):
        self.nodes = []

    def get_first(self):
        return self.nodes.pop(0)

    def insert(self, node_number):
        self.nodes.append(node_number)

    def empty(self):
        return len(self.nodes) == 0

Единственная разница со стеком заключается в том, что первый элемент берётся с помощью функции pop(0) вместо того, чтобы брать последний элемент с помощью pop(). Результат работы алгоритма с такой структурой показан ниже.

Чтобы поиграть в этой анимации с кнопками управления, жми сюда.

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

Алгоритм Дейкстры

Изначально алгоритм Дейкстры был разработан для нахождения кратчайшего пути к заданному узлу (и одновременно ко всем остальным), начиная с начального узла start. Мы можем применить его к нашей задаче поиска пути между двумя узлами.

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

Это означает, что  расстояние между узлами 0 и 1 в три раза больше, чем расстояние между узлами 0 и 2.

Теперь запишем структуру данных хранения узлов для алгоритма Дейкстры. В алгоритме Дейкстры мы каждый раз выбираем непосещённый узел с наименьшим расстоянием до начального узла, поэтому будем использовать очередь с приоритетом.

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

class DijkstraQueue(AbstractNodeStorageClass):
    """
        Очередь с приоритетом. Внутри метода get_first() выбирается
        узел с минимальным расстоянием distance от начального узла.
    """

    def __init__(self, distances):
        self.nodes = []
        self.distances = distances

    def get_first(self):
        closest_node_distance, closest_node = heappop(self.nodes)
        return closest_node

    def insert(self, element):
        heappush(self.nodes, (self.distances[element], element))

    def is_empty(self):
        return len(self.nodes) == 0

Результат алгоритма на такой структуре данных выглядит следующим образом:

Чтобы поиграть в этой анимации с кнопками управления, жми сюда.

Интересно, что в трёх случаях мы получили три разных пути, хотя и действовали в рамках одного графа и с помощью одного алгоритма. Изменялась только структура данных.

Усложним задачу до лабиринта

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

Сразу посмотрим, как решает эту задачу алгоритм Дейкстры. Не меняем ни алгоритм, ни структуру данных из предыдущего пункта — только граф.

Чтобы поиграть в этой анимации с кнопками управления, жми сюда.

Мы видим, как алгоритм последовательно перебирает узлы. При этом каждый следующий узел выбирается по принципу приоритетной очереди — как ближайший к начальному узлу start.

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

Алгоритм А*

Алгоритм А* учитывает как расстояние до начального узла, так и примерную оценку расстояния до целевого узла. Эта приблизительная оценка эвристически рассчитывается как евклидово расстояние от выбранного узла до целевого. Единственное изменение, которое нам нужно сделать, — это вычисление приоритета узла в очереди приоритетов. Вот код:

class AStarQueue(AbstractNodeStorageClass):
    """
        Очередь с приоритетом для алгоритма А*.
        В методе get_first() выбирается узел, для которого минимальна 
        сумма расстояния до начального узла и оценки расстояния
        (оценивается евклидова норма) до конечного узла.
    """

    def __init__(self, graph, distances, goal_node):
        self.nodes = []
        self.graph = graph
        self.x_goal, self.y_goal = graph.nodes[goal_node]['position']
        self.distances = distances

    def calc_heuristic(self, node):
        x_node, y_node = self.graph.nodes[node]['position']
        estimated_distance_to_goal = sqrt(
            (x_node - self.x_goal) ** 2 +
            (y_node - self.y_goal) ** 2
        )
        return estimated_distance_to_goal

    def get_first(self):
        optimal_node_value, optimal_node = heappop(self.nodes)
        return optimal_node

    def insert(self, element):
        heappush(self.nodes,
                 (self.distances[element] + 
                  self.calc_heuristic(element), element)
                 )

    def is_empty(self):
        return len(self.nodes) == 0

Здесь мы видим дополнительный метод calc_heuristic(), оценивающий расстояние до целевого узла. Теперь отдадим структуру данных алгоритму и получим следующий результат:

Чтобы поиграть в этой анимации с кнопками управления, жми сюда.

Обратите внимание, что благодаря использованию эвристики алгоритм A* быстрее находит правильный ответ — всего за 80 шагов вместо 203.

Вместо заключения

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

Иногда нам кажется, что алгоритмы и структуры данных - это два разных раздела computer science, но на практике они очень тесно связаны, и описанное выше - яркое тому подтверждение. На курсе "Алгоритмы и структуры данных" в Яндекс Практикуме мы стараемся не только научить людей писать эффективные алгоритмы, но и показать эту важную связь.

Если вам понравилась статья, вы можете посмотреть полный туториал и поиграться с кодом в google colab, либо посмотреть весь код на github.