Обзор исследований в области искусственного интеллекта


Обзор исследований в области искусственного интеллекта - стр. 11


f(n) = g(n) + h(n).

Здесь g(п) соответствует расстоянию на графе от узла п до начального состояния, a h(n) —оценка расстояния от п до узла, представляющего конечное (целевое) состояние. Чем меньше значение оценочной функции f(n), тем "лучше", т.е. узел п лежит на более коротком пути от исходного состояния к целевому. Идея алгоритма состоит в том, чтобы с помощью f(n) отыскать кратчайший путь на графе от исходного состояния к целевому.

Отсюда следует, что если h(n) — нижняя оценка действительного расстояния до целевого состояния, т.е. если h(n) никогда не дает завышенной оценки расстояния, то алгоритм А всегда отыщет оптимальный путь до цели при помощи оценочной функции f(n). Алгоритм, обладающий таким свойством, называется разрешимым (более подробное обсуждение этого вопроса читатель найдет в специальной литературе, в частности в работах Нильсона [Nilsson, 1980, Chapter 2] и Перла [Pearl, 1984, Chapter 2]).

Обозначения:

s — узел начального состояния;
g— узел целевого состояния;
OPEN — список, который содержит,выбранные, но необработанные узлы;
CLOSED — список, который содержит обработанные узлы.

Алгоритм

(1) OPEN:={s}.
(2) Если ОРЕN:={}, то прекратить выполнение. Пути к целевому состоянию на графе не существует.
(3) Удалить из списка OPEN узел п, для которого f(n) < f(m) для любого узла т, уже присутствующего в списке OPEN, и перенести его в список CLOSED.
(4) Сформировать список очередных узлов, в который возможен переход из узла n и удалить из него все узлы, образующие петли; с каждым из оставшихся связать указатель на узел п.
(5) Если в сформированном списке очередных узлов присутствует д, то завершить выполнение. Сформировать результат — путь, порожденный прослеживанием указателей от узла д до узла s.
(6) В противном случае для каждого очередного узла n', включенного в список, выполнить следующую последовательность операций.

  • Вычислить f(n').
  • Если n не присутствует ни в списке OPEN, ни в списке CLOSED, добавить его в список, присоединить к нему оценку f(n') и установить обратный указатель на узел п.



    Начало  Назад  Вперед