Во многих случаях (таких как эти карты, в которых нет изменений местности, подобно реализациям, использованным позднее в данном разделе), путь с наименьшим счетом также приводит к кратчайшему пути.
Разъяснение A*, почти на обычном языке
Давайте посмотрим на сам алгоритм на псевдо-коде.
1 AЗвезда.Поиск
2 создать открытый массив
3 создать замкнутый массив
4 s.g = 0
5 s.h = НайтиЭвристику( s.x, s.y )
6 s.f = s.g + s.h
7 s.родитель = ноль
8 Поместить в открытый массив
9 установить признакПоиска в true
10 Пока признакПоиска
11 взять узел n из открытого
12 Если n равно узлу назначения
13 создать путь от начала до конца
14 установить признакПоиска в false
15 для каждого соседа m из n
16 newg = n.g + стоимость( n, newx, newy )
17 Если m не был посещен
18 m.g = n.f
19 m.h = найтиЭвристику( newx, newy )
20 m.f = m.g + m.h
21 m.родитель = n
22 добавить его в открытый массив
23 сортировать открытый массив
24 Иначе
25 Если newg < m.g
26 m.родитель = n
27 m.g = newg
28 m.f = m.g + m.h
29 сортировать открытый массив
30 Если m находится в замкнутом
31 удалить его из замкнутого
32 Поместить n в замкнутый массив
33 Если время поиска > максимальное время
34 установить флагПоиска в false
35 вернуть path
Этот алгоритм использует два списка (который во Flash являются массивами), открытый и замкнутый. Открытый массив содержит все узлы, которые были раскрыты (то есть, все его соседи, которые были посещены). Мы используем открытый массив как приоритетную ветвь. Мы используем открытый массив не только для хранения узлов, но также для хранения узлов в определенном порядке. Мы поддерживаем массив отсортированным от меньшего счета (f) к большему. Каждый раз, когда мы добавляем узел в открытый массив или изменяем значение g в узле открытого массива, мы должны сделать новую сортировку массива, с тем чтобы расположить узлы по значению стоимости от меньшей к большей
Русская версия