Теория графов и алгоритмы Дейкстры и A*: математические основы и реализация поиска пути

1. Введение

В современной информатике теория графов (Graph Theory) предоставляет мощную математическую основу для моделирования сетевых структур. В нашей повседневной жизни технологии вычисления «кратчайшего пути» используются в различных ситуациях, таких как автомобильная навигация, информация о пересадках на поездах, интернет-маршрутизация и даже поиск пути ИИ в играх.

В этой статье представлено всестороннее объяснение, начиная с математического определения теории графов, которая является основой этого поиска пути, и заканчивая механизмами типичных алгоритмов поиска: алгоритма Дейкстры (Dijkstra’s Algorithm) и его дальнейшего развития, алгоритма A* (A-Star Algorithm), их математическими доказательствами и практическими методами реализации с использованием Python.

2. Основы теории графов

Перед тем как перейти к объяснению алгоритмов, давайте сначала математически определим граф, который является целевой структурой данных.

2.1 Математическое определение графа

Граф $ G $ определяется парой из множества вершин (Vertex/Node) $ V $ и множества ребер (Edge) $ E $.

$$ G = (V, E) $$

Здесь элемент $ e $ множества ребер $ E $ соединяет две вершины $ u, v \in V $ и представляется как $ e = (u, v) $.

Неориентированный граф (Undirected Graph): Граф без направления ребер. Если $ (u, v) \in E $, то $ (v, u) \in E $.
Ориентированный граф (Directed Graph): Граф с направлением ребер. $ (u, v) $ и $ (v, u) $ различаются.

2.2 Взвешенный граф (Weighted Graph)

При реальном поиске пути необходимо учитывать расстояние, время, стоимость и т. д. Поэтому мы рассмотрим взвешенный граф, в котором каждому ребру назначен «вес» (Weight). При введении весовой функции $ w: E \rightarrow \mathbb{R} $ граф определяется как $ G = (V, E, w) $.

$$ w(u, v) \ge 0 $$

Во многих случаях, поскольку расстояние и время не могут быть отрицательными, предполагается, что веса ребер неотрицательны.

  graph LR
    A(("A")) -- "4" --> B(("B"))
    A -- "2" --> C(("C"))
    B -- "5" --> D(("D"))
    C -- "1" --> B
    C -- "8" --> D
    C -- "10" --> E(("E"))
    D -- "2" --> E
    D -- "6" --> Z(("Z"))
    E -- "3" --> Z

Приведенный выше рисунок представляет собой пример взвешенного ориентированного графа от вершины $ A $ до $ Z $. Числа на ребрах обозначают стоимость (вес).

2.3 Формулировка задачи о кратчайшем пути

Пусть путь (Path) $ P $ от начальной точки (Source) $ s \in V $ до конечной точки (Target) $ t \in V $ представляет собой последовательность вершин $ (v_0, v_1, \dots, v_k) $ (где $ v_0 = s, v_k = t $), и для каждого $ i $ выполняется $ (v_i, v_{i+1}) \in E $. Общая стоимость $ W(P) $ этого пути $ P $ выражается суммой весов ребер на пути.

$$ W(P) = \sum_{i=0}^{k-1} w(v_i, v_{i+1}) $$

Задача о кратчайшем пути (Shortest Path Problem) — это задача нахождения пути $ P^* $, минимизирующего $ W(P) $ среди всех возможных путей $ P $.

3. Алгоритм Дейкстры (Dijkstra’s Algorithm)

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

3.1 Интуитивное понимание алгоритма

Алгоритм Дейкстры основан на жадном алгоритме (Greedy Algorithm) с подходом «последовательного определения ближайшей неподтвержденной вершины от начальной точки».

Подготовьте массив для хранения предварительного расстояния от начальной точки, инициализируйте начальную точку как 0, а остальные — как бесконечность ( $ \infty $ ).
Среди неподтвержденных вершин выберите вершину $ u $ с минимальным предварительным расстоянием и отметьте её как «подтвержденную».
Для всех смежных с вершиной $ u $ вершин $ v $, если путь через $ u $ дает меньшее предварительное расстояние, обновите расстояние (эта операция называется релаксацией (Relaxation)).
Повторяйте шаги 2 и 3, пока все вершины не будут подтверждены или пока не будет подтверждена целевая вершина.

3.2 Математическое выражение релаксации (Relaxation)

Операция релаксации ребра от вершины $ u $ к $ v $ математически выражается следующим образом. Здесь $ d[v] $ обозначает текущее предварительное кратчайшее расстояние от начальной точки до $ v $.

$$ \text{если } d[u] + w(u, v) < d[v]: \\ d[v] = d[u] + w(u, v) $$

3.3 Реализация алгоритма Дейкстры на Python

Для эффективной реализации в качестве структуры данных для получения минимального значения используется очередь с приоритетом (Priority Queue). В Python можно использовать модуль heapq.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import heapq

def dijkstra(graph, start):
    """
    graph: Тип словаря. Формат graph[u] = {v1: weight1, v2: weight2, ...}
    start: Начальный узел
    """
    # Словарь для хранения расстояний. Начальное значение - бесконечность
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # Очередь с приоритетом [(расстояние, узел)]
    pq = [(0, start)]
    
    # Словарь для восстановления пути
    previous_nodes = {node: None for node in graph}

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        # Пропустить, если уже обработано (найден более короткий путь)
        if current_distance > distances[current_node]:
            continue

        # Поиск соседних узлов
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # Операция релаксации (Relaxation)
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    return distances, previous_nodes

3.4 О вычислительной сложности

Если в качестве очереди с приоритетом используется бинарная куча (Binary Heap), каждая вершина извлекается из очереди один раз, а каждое ребро релаксируется один раз. Следовательно, временная сложность составляет $ O((|V| + |E|) \log |V|) $. При использовании фибоначчиевой кучи теоретически она улучшается до $ O(|E| + |V| \log |V|) $, но на практике часто применяется бинарная куча.

4. Алгоритм A* (A-Star Algorithm)

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

4.1 Введение эвристической функции

Алгоритм A* приоритетно продвигает поиск в направлении цели, используя «оценочное расстояние» от текущего узла до цели. Функция, возвращающая это оценочное расстояние, называется эвристической функцией (Heuristic Function) $ h(n) $.

В A* функция $ f(n) $ для оценки узла $ n $ определяется следующим образом.

$$ f(n) = g(n) + h(n) $$

Где,

$ g(n) $: Фактическая стоимость от начальной точки до узла $ n $ (то же самое, что расстояние в алгоритме Дейкстры)
$ h(n) $: Оценочная стоимость от узла $ n $ до конечной точки (эвристика)
$ f(n) $: Оценочная общая стоимость пути от начальной точки до конечной через $ n $

4.2 Условия эвристики

Чтобы алгоритм A* всегда находил кратчайший путь (оптимальность), эвристическая функция $ h(n) $ должна удовлетворять следующим условиям.

$$ h(n) \le h^*(n) $$
(где $ h^*(n) $ — истинная кратчайшая стоимость от $ n $ до конечной точки)
$$ h(m) \le c(m, n) + h(n) $$
Здесь $ c(m, n) $ — стоимость ребра от $ m $ к $ n $. Согласованная эвристика автоматически становится допустимой.

4.3 Типичные эвристические функции

Для поиска пути на сетке часто используются следующие функции расстояния.

Манхэттенское расстояние (Manhattan Distance): Когда движение возможно только вверх, вниз, влево и вправо $$ h(n) = |x_n - x_{goal}| + |y_n - y_{goal}| $$
Евклидово расстояние (Euclidean Distance): Когда возможно прямолинейное движение в любом направлении $$ h(n) = \sqrt{(x_n - x_{goal})^2 + (y_n - y_{goal})^2} $$

4.4 Реализация алгоритма A* на Python

Реализация A* очень похожа на алгоритм Дейкстры, за исключением того, что ключом для очереди с приоритетом становится $ f(n) $.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import heapq

def a_star(graph, start, goal, heuristic_func):
    """
    graph: Словарь со стоимостями между узлами
    start: Начальная точка
    goal: Конечная точка
    heuristic_func: Эвристическая функция h(node, goal)
    """
    open_set = []
    heapq.heappush(open_set, (0, start))
    
    # Фактическая стоимость от начальной точки g(n)
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    
    # f(n) = g(n) + h(n)
    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic_func(start, goal)
    
    came_from = {}

    while open_set:
        # Получить узел с минимальным f(n)
        current_f, current_node = heapq.heappop(open_set)

        if current_node == goal:
            return reconstruct_path(came_from, current_node)

        for neighbor, weight in graph[current_node].items():
            tentative_g_score = g_score[current_node] + weight

            if tentative_g_score < g_score[neighbor]:
                # Найден лучший путь
                came_from[neighbor] = current_node
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + heuristic_func(neighbor, goal)
                
                # Добавить в open_set
                heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None # Если путь не найден

def reconstruct_path(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    path.reverse()
    return path

4.5 Сравнение алгоритма Дейкстры и A*

Следующая диаграмма Mermaid представляет собой концептуальное сравнение диапазонов поиска алгоритма Дейкстры и A*. В то время как алгоритм Дейкстры расширяет поиск концентрическими кругами, A* продвигает поиск в форме эллипса, вытянутого в направлении цели.

  graph TD
    subgraph "Дейкстра"
        S1(("Начало")) --> A1((" "))
        S1 --> B1((" "))
        S1 --> C1((" "))
        A1 --> D1((" "))
        B1 --> Goal1(("Цель"))
        C1 --> E1((" "))
        style S1 fill:#4a9,stroke:#333
        style Goal1 fill:#f94,stroke:#333
    end

    subgraph "A_Звезда"
        S2(("Начало")) --> B2((" "))
        B2 --> Goal2(("Цель"))
        style S2 fill:#4a9,stroke:#333
        style Goal2 fill:#f94,stroke:#333
    end

5. Применение поиска пути и перспективы

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

Двунаправленный поиск (Bidirectional Search): Метод, который радикально сокращает пространство поиска путем одновременного продвижения поиска как от начальной, так и от конечной точки, объединяя их посередине.
Алгоритм D* (Dynamic A*): Метод эффективного пересчета пути в средах, где динамически появляются неизвестные препятствия (например, автономное вождение роботов).
JPS (Jump Point Search): Метод дальнейшего ускорения поиска A* на однородных картах-сетках. Он использует симметрию для пропуска ненужных узлов.

Алгоритмы поиска пути — это область, в которой прекрасно сочетаются математическая красота теории графов и алгоритмическая эффективность информатики.

6. Заключение

В этой статье мы начали с базовых определений теории графов и объяснили математическую подоплеку, конкретные механизмы и примеры реализации на Python алгоритма Дейкстры и алгоритма A*.

Алгоритм Дейкстры оценивает все узлы одинаково и гарантирует нахождение надежного кратчайшего пути.
Алгоритм A* реализует эффективный поиск к цели путем введения эвристической функции $ h(n) $.

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