Визуальный язык ДРАКОН

A* – популярный информированный алгоритм поиска. Слово «информированный» означает, что вместо тупого перебора вариантов алгоритм исследует самые многообещающие из них. Критерием для определения перспективности является смутное ощущение «тепло-холодно» – эвристическая функция.

Какие задачи может решить А*?

• Найти решение.
• Построить последовательность шагов к цели.

Как и многие другие алгоритмы поиска, A* работает с пространством состояний. Пространство состояний – это граф, в котором:

• Узлы – возможные состояния системы.
• Рёбра – разрешённые переходы между состояними.

Если цель поиска – найти путь, то в качестве входных данных задаются начальное и конечное состояние.

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

Алгоритм начинает движение по пространству состояний с начального состояния. Основной вопрос, который задаётся на каждом узле, – куда двигаться дальше? Для каждого узла рассчитывается несколько величин:
g – Фактическая стоимость пути от начала до текущего узла.
h – Оценочная стоимость пути от текущего узла до цели.
f – Полная стоимость пути. Это сумма фактической и оценочной стоимостей.

f = g + h

Узлы-кандидаты содержатся в так называемом «открытом списке». Узлы в этом списке отсортированы по полной стоимости. Первым из открытого списка всегда берётся узел с наименьшей стоимостью.

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

A* старается найти самый короткий путь.

Эффективность алгоритма A* сильно зависит от того, насколько точно эвристическая функция оценивает расстояние до цели.

А* является «полным» алгоритмом. Он всегда находит путь к решению, если таковой путь существует.

ДРАКОН-схема алгоритма A*:

Скачать исходник в формате DRAKON Editor: a-star-ru.drn

Реализация алгоритма A* на гибридном языке ДРАКОН-Lua:

Скачать исходник в формате DRAKON Editor: a-star.drn Из этого файла можно сгенерировать работающий скрипт на Lua.

Степан Митькин