3.6.3. Алгоритм а*

В алгоритме А* [1, 2] все точки в пространстве обобщенных координат, соответствующие разрешенным конфигурациям, представляются в виде вершин нагруженного графа. Вес ребра графа соответствуют расстояниям между вершинами, соединенными этим ребром. Путь ищется на графе от начальной вершины s до конечной вершины e. В основе алгоритма лежит выбор на каждом шаге поиска следующей точки пути такой точки, чтобы значение ее оценочной функции было минимальным. В качестве оценочной функции в данной работе использовалась функция

f(n)=g(n)+h(n), (3.108)

где g(n) – стоимость пути в дереве перебора от начальной вершины до вершины n, а h(n) – это расстояние в пространстве обобщенных координат от точки, соответствующей конфигурации n, до целевой конфигурации.

Алгоритм А* может быть представлен следующей последовательностью шагов:

1. Поместить начальную вершину s в список, называемый ОТКРЫТ, и вычислить f(s).

2. Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче; в противном случае нужно перейти к следующему этапу.

3. Взять из списка ОТКРЫТ ту вершину, для которой значений функции f наименьшее, и поместить ее в список ЗАКРЫТ. Дать этой вершине имя n. (В случае совпадения значений f для нескольких вершин, можно выбирать вершину с минимальным f произвольно, но всегда необходимо отдавать предпочтение целевой вершине.)

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

5. Раскрыть вершину n, построив все непосредственно следующие за ней вершины. (Если таких не оказалось, переходить к шагу 2.) Для каждой такой дочерней вершины n_i вычислить значение f(n_i).

6. Связать с теми из вершин n_i, которых еще нет в списках ОТКРЫТ или ЗАКРЫТ, только что подсчитанные значения f(n_i). Поместить эти вершины в список ОТКРЫТ и провести от них к вершине n указатели.

7. Связать с теми из непосредственно следующих за n вершинами, которые уже были в списках ОТКРЫТ или ЗАКРЫТ, меньшее из прежних и только что вычисленных значений f. Поместить в список ОТКРЫТ те из непосредственно следующих за n вершин, для которых новое значение f оказалось ниже, и изменить направление указателей от всех вершин, для которых значение f уменьшилось, направив их к n.

8. Перейти к шагу 2.

Рассмотрим использование алгоритма А* на примере, приведённом на рисунке 3.6. В результате работы найден путь A→E→I→J

	ОТКРЫТ	ЗАКРЫТ
	A	A:n, f(n)=0
g(ni)=AF=1 h(ni)=F EI J=3	f(ni)=4, AF
g(ni)=1 h(ni)= EI J=2	f(ni)=3, AE	AE
g(ni)= AEI=2 h(ni)= I J=1	f(ni)=3, AEI
g(ni)= AED=2 h(ni)=DIJ=2	f(ni)=4, AED
g(ni)= AEC=2 h(ni)=C DIJ=3	f(ni)=5, AEC	AEI
	AEI J

Рис.3.9.

Алгоритм А* применим для n-мерного пространства состояний. Алгоритм за конечное число шагов либо находит путь, либо сообщает,что путь найден быть не может. В среде без препятствий найденный путь является оптимальным.