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

Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность

Инструменты пользователя

Инструменты сайта


algoritmy:a-star
Перевод этой страницы:

Алгоритм A*

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.

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

algoritmy/a-star.txt · Последние изменения: 2012/08/12 18:23 — Степан Митькин