Алгоритмы поиска пути: Алгоритм дейкстры и А*

Автор статьи: Артем Михайлов

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

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

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

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

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

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

Определение графа

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

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

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

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

Алгоритмы поиска пути

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

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

Алгоритм Дейкстры — это классический алгоритм поиска пути, который был разработан голландским ученым Эдсгером Дейкстрой в 1959 году. Этот алгоритм используется для поиска кратчайшего пути в взвешенном графе от одной вершины (обозначим ее как начальную) до всех остальных вершин.

Принцип работы

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

Сначала инициализируются два множества:

• Множество, содержащее уже обработанные вершины (изначально пустое).
• Множество, содержащее все остальные вершины графа (изначально содержит все вершины графа).

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

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

Процесс продолжается, пока не будут посещены все вершины или пока мы не найдем путь до конечной вершины (если она задана).

Реализация на Python

В Python алгоритм Дейкстры может быть реализован следующим образом:

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_vertex = heapq.heappop(queue)

        # Обрабатываем только вершину с наименьшим расстоянием
        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # Рассматриваем этот новый путь только в том случае, если он лучше любого пути, который мы нашли до сих пор
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

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

graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'C': 2},
    'C': {'A': 3, 'B': 2}
}

В этом графе вершина 'A' связана с вершиной 'B' весом 1 и с вершиной 'C' весом 3, и так далее.

Алгоритм A*

Алгоритм A* — это популярный алгоритм поиска пути, часто используемый в областях, таких как искусственный интеллект и компьютерные игры. Алгоритм A* был предложен Питером Хартом, Нильсом Нильсоном и Бертраном Рафаэлем в 1968 году.

Принцип работы

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

g(n) — это уже известная стоимость пути от начальной вершины до текущей.
h(n) — это эвристическая оценка стоимости пути от текущей вершины до цели.
Сумма f(n) = g(n) + h(n) дает оценку общей стоимости пути через данную вершину. Эвристика h(n) играет ключевую роль в алгоритме A*. Она должна быть адекватной, чтобы алгоритм был эффективным.

На каждом шаге алгоритм выбирает вершину с наименьшей оценкой f(n) из списка открытых вершин (вершин, которые уже были обнаружены, но еще не обработаны), затем смотрит на соседей этой вершины и обновляет их стоимости g(n), если через текущую вершину можно добраться до них быстрее. Если вершина еще не была открыта, она добавляется в список открытых вершин.

Процесс продолжается, пока не будет найден путь до целевой вершины или пока не кончатся вершины в списке открытых вершин (что означает, что путь не существует).

Реализация на Python

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

class Node:
    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position
        self.g = 0
        self.h = 0
        self.f = 0

def calculate_h(node1, node2):
    return abs(node1.position[0] - node2.position[0]) + abs(node1.position[1] - node2.position[1])

Теперь мы можем реализовать сам алгоритм A*:

def a_star(maze, start, end):
    start_node = Node(None, start)
    end_node = Node(None, end)
    
    open_list = []
    closed_list = []

    open_list.append(start_node)

    while len(open_list) > 0:
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index

        open_list.pop(current_index)
        closed_list.append(current_node)

        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1]

        children = [Node(current_node, (current_node.position[0] - 1, current_node.position[1])),
                    Node(current_node, (current_node.position[0] + 1, current_node.position[1])),
                    Node(current_node, (current_node.position[0], current_node.position[1] - 1)),
                    Node(current_node, (current_node.position[0], current_node.position[1] + 1))]

        for child in children:
            if child in closed_list:
                continue
            
            child.g = current_node.g + 1
            child.h = calculate_h(child,end_node)
            child.f = child.g + child.h

            if len([open_node for open_node in open_list if child == open_node and child.g > open_node.g]) > 0:
                continue

            open_list.append(child)

В этом коде maze — это двумерный список, где 1 — это преграда, а 0 — это свободная ячейка. start и end — это координаты начальной и конечной вершин.

Пример использования
Давайте применим этот алгоритм к простому лабиринту:

maze = [[0, 0, 0, 0, 1, 0],
        [1, 1, 0, 0, 1, 0],
        [0, 0, 0, 1, 0, 0],
        [0, 1, 1, 0, 0, 1],
        [0, 0, 0, 0, 0, 0]]

start = (0, 0)
end = (4, 5)

path = a_star(maze, start, end)
print(path)  # Output: [(0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5)]

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

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

Применение

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

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

Эффективность и производительность

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

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

Веса ребер

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

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

Управление памятью

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

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

Универсальность

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

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

Заключение

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

Напоследок хочу порекомендовать вам бесплатный вебинар, в рамках которого эксперты OTUS расскажут про остроумный алгоритмом Ахо-Корасика для поиска нескольких шаблонов в тексте. Вы создадите недетерминированный конечный автомат в виде префиксного дерева, добавите суфиксные и финальные ссылки, вместе с экспертов пропустите текст через этот Бор и найдёте все шаблоны за линейное время, реализовав алгоритм Ахо-Корасика.

Зарегистрироваться на бесплатный вебинар