Алгоритм.

Введем следующие обозначения:

s – узел начального состояния;

g – узел конечного (целевого) состояния;

OPEN – список выбранных, но необработанных узлов;

CLOSED – список обработанных узлов.

Шаги:

1. .

2. Если , то прекратить выполнение. Пути к целевому состоянию на графе не существует.

3. Удалить из списка OPEN узел n, для которого для любого узла m, уже присутствующего в списке OPEN, и перенести его в список CLOSED.

4. Сформировать список очередных узлов, в который возможен переход из узла n, и удалить из него все узлы, образующие петли; с каждым из оставшихся связать указатель на узел n.

5. Если в сформированном списке очередных узлов присутствует g, то завершить выполнение. Сформировать результат – путь, порожденный прослеживанием указателей от узла g до узла s.

6. В противном случае для каждого очередного узла , включенного в список выполнить следующую последовательность операций:

6.1 Вычислить .

6.2 Если не присутствует ни в списке OPEN, ни в списке CLOSED, добавить его в список, присоединить к нему оценку и установить обратный указатель на узел n.

6.3 Если уже присутствует в списке OPEN или в списке CLOSED, сравнить новое значение с прежним .

6.4 Если , прекратить обработку нового узла.

6.5 Если , заменить новым узлом прежний в списке, причем, если прежний узел был в списке CLOSED, перенести его в список OPEN.