Недетерминированность управления выводом и эвристические знания. Алгоритм А*.

Эвристическая информация используется таким образом, чтобы процесс поиска распространялся только по наиболее перспективным направлениям. Для вычисления "перспективности" вершин можно применить, например, метод использования оценочной функции. Это позволяет сократить поиск решения.

Алгоритм А*

Основная идея алгоритма состоит в использовании для каждого узла n на графе пространства состояний оценочной функции вида

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

Здесь

  • g(n) соответствует расстоянию на графе от узла n до начального состояния
  • h(n) - оценка расстояния от узла n до узла, представляющего конечное (целевое) состояние.

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

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

    • s - узел начального состояния;
    • g- узел конечного (целевого) состояния;
    • OPEN - список выбранных, но необработанных узлов;
    • CLOSED - список обработанных узлов.

    Шаги:

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