Бэктрекинг, конъюнкция и дизъюнкция.
Бэктрекинг (алгоритм поиска с возвратом)- механизм возврата, который осуществляет откат программы к той точке, в которой выбирался унифицирующийся с последней подцелью дизъюнкт (элемент предиката). Для этого точка, где выбирался один из возможных унифицируемых с подцелью дизъюнктов, запоминается в специальном стеке, для последующего возврата к ней и выбора альтернативы в случае неудачи. При откате все переменные, которые были означены в результате унификации после этой точки, опять становятся свободными.
В итоге выполнение программы может завершиться неудачей, если одну из подцелей не удалось унифицировать ни с одним дизъюнктом программы, и может завершиться успешно, если был выведен пустой дизъюнкт, а может и просто зациклиться.
Турбо-Пролог обладает встроенным механизмом логического вывода, благодаря чему от пользователя требуется только описание своей задачи с помощью аппарата логики предикатов первого порядка, а поиск решения система берет на себя. Рассмотрим пример использования бэктрекинга в Турбо-Прологе:
p :- q,s.
p :- r,t.
Эту программу можно прочитать следующим образом. При выполнении процедуры p выполняются процедуры q и s. Если они завершаются успешно, то и процедура p считается успешно завершенной. Если это не так, то выполняются процедуры r и t. В этом случае процедура успешно завершается, если r и t завершены успешно. В противном случае процедура p терпит неудачу. Этот процесс возврата к поиску других решений называется бэктрекингом (backtracking).
Принципиальная разница между backtracking и рекурсией заключается в том, что первый не позволяет передавать данные между шагами итераций, т.к. каждый раз при достижении цели все переменные "освобождаются".
При создании программ в Турбо-Прологе также часто пользуются конъюнкцией (логическое умножение) и дизъюнкцией (логическое сложение):
1) Если в качестве условия A выступает факт, либо несколько фактов A1,...,AN, соединенные логической операцией И:
A1 ИA2 И ... ИAN.
то в математической логике такое выражение называется конъюнкцией.
Оно считается истинным в том случае, если истинны всеего компоненты.
2) Если в качестве условия A выступает факт, либо несколько фактов A1,...,AN, соединенные логической операцией ИЛИ:
A1 ИЛИA2 ИЛИ... ИЛИAN.
то в математической логике такое выражение называется дизъюнкцией.
Дизъюнкция– это когда подцели поставлены как альтернативные, т.е. если несколько выражений, соответствуют одному и тому же правилу. Турбо-пролог будет искать любые решения, соответственно одной из подцелей.
Дата добавления: 2016-05-05; просмотров: 752;