Стратегия поиска в языке 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 всегда использует поиск в глубину. |