<<
>>

Стратегия поиска в языке Prolog

Prolog проводит резолюцию в строго линейной стиле, заменяя цели слева направо и рассматривая формулы в базе данных в порядке сверху-вниз. Подцели также рассматриваются немедленно, по мере их установки.
Таким образом, эта стратегия поиска реализуется как поиск в глубину на дереве возможных вариантов. Например, рассмотрим следующие формулы:

(1) ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

(2) ancestor(X, X).

(3) parent(liza, tom).

Для цели ancestor(X, tom) стратегия поиска Prolog (слева направо и сначала в глубину) на дереве подцелей показана на рис. 21.1. Ребра на этом рисунке помечены номерами формул, используемых системой Prolog для резолюции, а конкретизации переменных записаны в фигурных скобках.

Листовые вершины в этом дереве достигаются, если не найдено совпадение для крайней левой формулы или если все формулы были устранены, что соот

Язык Prolog

665

ветствует успеху.
Всякий раз, когда зафиксирован отказ (или пользователь задал непрерывный поиск с помощью точки с запятой), Prolog выполняет откат вверх по дереву, чтобы обнаружить другие пути к листу, освобождая конкретизации переменных. Таким образом, если после нахождения в дереве решения X = liza инициируется откат, эта конкретизация X будет освобождена и будет найден новый путь к листу с X = tom.

Рис. 21.1. Дерево поиска для Prolog, показывающее подцели, формулы, используемые для резолюции, и конкретизации переменных

Эта стратегия «сначала в глубину» чрезвычайно эффективна, поскольку она может быть реализована на основе стека или в рекурсивном стиле. Однако она же означает, что решения не могут быть найдены, если в дереве поиска имеются ветви бесконечной глубины. Например, предположим, что мы написали формулы в несколько отличном порядке:

(1) ancestor(X, Y) :- ancestor(Z, Y), parent(X, Z).

(2) ancestor(X, X).

(3) parent(liza, tom).

Такая запись заставит Prolog войти в бесконечный цикл в попытках удовлетворить ancestor(Z, Y) путем многократного использования первой формулы. Конечно, это является следствием леворекурсивного способа, которым была написана первая формула, и того факта, что никакие другие формулы не предшествуют ей. В «чистом» логическом программировании, где используется поиск «вначале в ширину» («сначала вширь»), всегда будут искаться и другие решения (если они есть). К сожалению, поиск типа «сначала вширь» значительно дороже поиска в глубину, поэтому лишь немногие системы логического программирования используют его. Prolog всегда использует поиск в глубину.

<< | >>

Еще по теме Стратегия поиска в языке Prolog:

  1. 29 Стратегия поиска "среднего"
  2. Аристотелева стратегия поиска "первоначал"
  3. Поиск смысла жизни – это поиск бессмертия!
  4. О языке и методе
  5. Установки — на естественном языке внутренней речи.
  6. Установки — на естественном языке внутренней речи.
  7. Формулировать задание внутренней природе организма следует на языке души
  8. Стратегии
  9. Разминка антистрессовая, приемы и спецприемы, целевые установки — на естественном языке «внутренней речи».
  10. Разминка антистрессовая, приемы и спецприемы, целевые установки — на естественном языке «внутренней речи».
  11. Моделирование стратегий гениев
  12. Пятая глава СТРАТЕГИЯ ЛИДЕРСТВА ЖЕНЩИНЫ
  13. Стратегии организации в отношениях с внешней средой.
  14. Стратегия переговоров
  15. Практическое применение стратегий Аристотеля
  16. СТРАТЕГИЯ