com (см. Дополнение E для ссылок по поиску пути). Мой псевдо-код алгоритма A* подобен тому, что я нашел на Gamasutra (www.gamasutra.com), но не тот же самый. Если два человека садятся и пишут набросок сценария для Звездных войн: Эпизод 2, эти наброски, вероятно, будут иметь одинаковое содержание, но различаться в деталях. То же самое здесь: есть два различных описания одного алгоритма.
Разветвление поиска пути
Хотя первоначально он использовался для поиска пути, алгоритм A* в действительности имеет более общее назначение. Вы можете использовать его для поиска решений многих видов проблем. Мое понимание A* в применении к поиску пути является довольно твердым, но мое общее понимание A* относительно других его применений является, ну, в общем, незначительным. Если вы интересуетесь использованием алгоритма A* для задач отличающихся от поиска пути, вы можете, вероятно, найти большое количество ресурсов на сайтах в Интернет, чтобы получить дополнительную помощь в этом вопросе.
Основная терминология и функциональность алгоритма A*
Как многие основанные на математике концепции, алгоритм поиска пути A* использует набор терминов, с которыми вы должны познакомиться в процессе его рассмотрения. Эти термины описывают состояния, действия и результаты, которые следуют за этим процессом:
Узел представляет текущее состояние системы. В поиске пути, текущее состояние это просто плитка, которую мы проверяем в данный момент. В дальнейшем нашем рассмотрении узел является плиткой.
Действие раскрывания узла означает, что (в коде) вы посещаете каждого соседа узла.
Эвристикой в A* называется тренировочная гипотеза, основанная на выбранной единице измерения, которая дает в результате число. (Это довольно неопределенно, правда? Мы еще поговорим об эвристике позднее.)
Стоимость является числовым значением, которое мы назначаем действию перемещения от одного узла к другому.
Счет представляет собой сумму стоимости и эвристики в каждом узле, который вы посетили на пути к текущему узлу
Русская версия