Давайте предположим, что этот путь пролегает через Нью-Йорк-Мадрид-Лондон-Париж. В Нью-Йорке (как для всех узлов), f = g + h. Помните, что g представляет собой сумму всех f из предыдущих узлов. Поскольку Нью-Йорк является начальным узлом, не имеющим родительских узлов, то в Нью-Йорке g=0. Для Мадрида также f = g + h (как для всех узлов). В этом случае g не равно 0, потому что Мадрид был посещен из другого узла. Значение g включает f из Нью-Йорка. Таким образом, g является общей стоимостью пробега до текущего узла. Если бы вы действительно отправились в это путешествие, то g было бы значением потраченной суммы денег до вашего текущего места нахождения.
В этом месте следует упомянуть одну из наиболее удивительных особенностей алгоритма A* - метод, которым он обрабатывает физические особенности местности. Выше я сказал, что стоимость прохождения от одной плитки к другой равна 1 или 1.41. Это истинно для всех плиток равного размера, но это высказывание не всегда истинно. Скажем, некоторые из плиток сделаны из воды. Вы, вероятно, не хотите послать вашего персонажа через воду, если это не является абсолютно необходимым. Так что вы присваиваете значение, скажем 10, любому переходу узла (перемещению из одного узла в другой), который использует воду. Это не гарантирует, что путь не будет проходить через воду. Но это даст исключительное предпочтение путям, которые не проходят по воде. Если вода представляет собой поток, полностью пересекающий карту и через него нет моста, то алгоритм A* в конечном счете дает вам путь через воду. Однако, если есть мост, и он достаточно близко, то A* даст вам путь, включающий в себя мост. С другой стороны, если ваш персонаж является наполовину человеком, а наполовину рыбой, то он может предпочесть воду. В этом случае вы можете дать для суши меньшую стоимость, чем для воды. Держа все это в голове, я должен, вероятно, изменить мое первоначальное утверждение, что A* всегда ищет кратчайший путь. Теперь, когда вы знаете больше, я могу дополнительно определить, что A* будет всегда находить путь с наименьшим счетом
Русская версия