Поиск A*

A* (произносится как "A-star") — это эффективный алгоритм обхода графа и поиска пути, который широко применяется в различных областях компьютерных наук благодаря своей полноте, оптимальности и высокой производительности.

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

Одним из основных практических недостатков алгоритма является его сложность в использовании памяти. Он требует \(O(b^d)\) памяти, где \(d\) — глубина решения (длина кратчайшего пути), а \(b\) — коэффициент ветвления (максимальное количество последователей для состояния). Это означает, что алгоритм сохраняет все сгенерированные узлы в памяти, что может быть значительным для систем с ограниченными ресурсами. Однако во многих случаях A* по-прежнему является лучшим решением.

Алгоритм был впервые опубликован в 1968 году Питером Хартом, Нильсом Нильссоном и Бертрамом Рафаэлем из Стэнфордского исследовательского института (ныне SRI International). Его можно рассматривать как расширение алгоритма Дейкстры, который обеспечивает более высокую производительность за счёт использования эвристических методов для управления поиском.

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

Описание

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

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

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

\[ f(n) = g(n) + h(n) \]

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

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

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

Значение \(f\) для этой цели также является стоимостью кратчайшего пути, так как \(h\) в точке достижения цели равно нулю в допустимой эвристике.

Реализация

python

import numpy as np


class Cell:
    # (1)!
    def __init__(self):
        self.position = (0, 0)
        self.parent = None
        self.g = 0
        self.h = 0
        self.f = 0

    # (5)!
    def __eq__(self, cell):
        return self.position == cell.position

    def showcell(self):
        print(self.position)


class Gridworld:
    # (2)!
    def __init__(self, world_size=(5, 5)):
        self.w = np.zeros(world_size)
        self.world_x_limit = world_size[0]
        self.world_y_limit = world_size[1]

    def show(self):
        print(self.w)

    def get_neighbours(self, cell):
        # (3)!
        neughbour_cord = [
            (-1, -1),
            (-1, 0),
            (-1, 1),
            (0, -1),
            (0, 1),
            (1, -1),
            (1, 0),
            (1, 1),
        ]
        current_x = cell.position[0]
        current_y = cell.position[1]
        neighbours = []
        for n in neughbour_cord:
            x = current_x + n[0]
            y = current_y + n[1]
            if 0 <= x < self.world_x_limit and 0 <= y < self.world_y_limit:
                c = Cell()
                c.position = (x, y)
                c.parent = cell
                neighbours.append(c)
        return neighbours


def astar(world, start, goal):
    # (4)!
    _open = []
    _closed = []
    _open.append(start)

    while _open:
        min_f = np.argmin([n.f for n in _open])
        current = _open[min_f]
        _closed.append(_open.pop(min_f))
        if current == goal:
            break
        for n in world.get_neighbours(current):
            for c in _closed:
                if c == n:
                    continue
            n.g = current.g + 1
            x1, y1 = n.position
            x2, y2 = goal.position
            n.h = (y2 - y1) ** 2 + (x2 - x1) ** 2
            n.f = n.h + n.g

            for c in _open:
                if c == n and c.f < n.f:
                    continue
            _open.append(n)
    path = []
    while current.parent is not None:
        path.append(current.position)
        current = current.parent
    path.append(current.position)
    return path[::-1]

position: представлена набором координат x и y, изначально заданных как (0,0).
parent: Содержит объект родительской ячейки, который был посещен до того, как мы добрались до этой ячейки.
g, h, f: Параметры, используемые при вызове нашей эвристической функции
Класс Gridworld представляет внешнее окружение в виде матрицы размером M * M
Возвращает соседей по ячейке
Реализация алгоритма запуска
Переопределяет метод Equals, иначе будут неверные результаты