Поиск решений Пролог-системой

Вопрос к системе – это всегда последовательность, состоящая из одной или нескольких целей. Для ответа на поставленный вопрос Пролог-система должна достичь всех целей, т.е. показать, что утверждения вопроса истинны в предположении, что все отношения программы истинны. Если в вопросе имеются переменные, то система должна найти конкретные объекты, которые, будучи подставлены вместо переменных, обеспечат достижение цели. Если система не в состоянии вывести цель из имеющихся фактов и правил, то ответ должен быть отрицательный. Таким образом, факты и правила в программе соответствуют аксиомам, а вопрос – теореме.

При поиске ответа на поставленный вопрос Пролог-система находит факт или правило для содержащегося в вопросе предиката и выполняет операцию сопоставления (унификации) объектов предиката. При этом возможны следующие случаи успешного сопоставления:

• сопоставляются две одинаковые константы;

• сопоставляется свободная переменная с константой (при этом переменная получает значение, равное константе);

• сопоставляется связанная переменная с константой, равной значению переменной;

• сопоставляется свободная переменная с другой свободной переменной. Никаких значений переменные при этом не получают, но между ними устанавливается связь, таким образом, что в дальнейшем они будут выступать в качестве синонимов. Такие переменные называют сцепленными.

После успешного сопоставления все переменные получают значения и становятся связанными, а предикат считается успешно выполненным (если сопоставление выполнялось с фактом) или заменяется на тело правила (если сопоставление выполнялось с головой правила). Связанные переменные освобождаются, если цель достигнута или сопоставление неуспешно.

Процесс сопоставления похож на использование оператора «=». Интерпретация этого оператора Прологом зависит от того, известны ли оба значения, связанные этим оператором или только одно из них. Если оба значения известны, то оператор интерпретируется как оператор сравнения. Если известно только одно значение, то оператор интерпретируется как присваивание, причем присваивание может выполняться как слева направо, так и справа налево в зависимости от того, слева или справа от оператора находится известное значение.

Для достижения целей Пролог использует механизм отката. При вычислении цели выполняется сопоставление с фактами и головами правил. Сопоставления выполняются слева направо. Возможно, некоторые подцели будут неуспешны при сопоставлении с некоторыми фактами или правилами, поэтому Пролог должен запоминать «точки», в которых он может поискать альтернативные пути решения. Если цель была неуспешной, то выполняется откат влево к ближайшему указателю отката и выполняется новая попытка достичь цели. Этот откат будет повторяться, пока цель не будет достигнута или исчерпаются все указатели отката. Если все цели были достигнуты, но использовались не все указатели отката, то будет продолжен поиск других решений.

Пример: Рассмотрим работу Пролог-системы при вопросе: предок(том,энн).

Сначала выполняется сопоставление цели и головы первого правила, сопоставление успешно и переменные X и Y становятся связанными (X получает значение том, а Y – значение энн). При этом Пролог-система запоминает, что имеется второе правило, по которому можно будет продолжить поиск решения. Далее начинает выполняться тело первого правила (новая цель родитель(том,энн)). Опять выполняются все возможные сопоставления с фактами предиката родитель. Сопоставление неуспешно, все связи разорваны.

Далее происходит возврат для сопоставления цели и головы второго правила. Сопоставление успешно и переменные X и Y становятся связанными (X получает значение том, а Y – значение энн). Далее начинает выполняться тело второго правила (новая цель родитель(том,Z)). В нем имеется две цели, их достижение проверяется по порядку. Первая цель успешна, т.к. сопоставляется с фактом родитель(том,боб), при этом Z получает значение боб. Новая цель - предок(боб,энн). Опять выполняется составление цели и головы первого правила. Оно успешно, при этом X получает значение боб, а Y – значение энн. Новая цель – правая часть первого правила родитель(боб,энн) успешна.

Следовательно, цель успешна и ответ Пролог-системы: да.

Представим шаги вычислений графически.

Рисунок 11 - Поиск решений

Можно посмотреть, как Пролог-система ищет решения:

Включить опцию трассировки всех предикатов, выполнив команду: trace. или нажав кнопку на панели инструментов

После появления приглашения [trace]?- можно вводить предикат для трассировки. После запуска предиката продолжить пошаговый поиск решения можно клавишей Enter. Отказ от трассировки осуществляется командой notrace.

В окне трассировки могут появиться следующие слова:

• Call

Далее указывается текущая цель: имя предиката и значения его аргументов. Если переменная не имеет значения, то ее имя начинается с подчеркивания.

• Exit

Указывается цель, которая успешна.

• Redo

Возврат в отмеченную точку возврата для поиска альтернативного решения.

• Fail

Указанная цель не была достигнута.

43