12 Лекция №11. Управление поиском решений: предикаты отсечения и возврата

Время: 2 часа (90 мин.)

12.1 Основные вопросы

• предикат отсечения;

• предикат возврата.

12.2 Текст лекции

В процессе достижения цели Турбо-Пролог осуществляет автоматический перебор вариантов, выполняя возврат(откат) при неуспехе, за счёт встроенного механизма возврата. Механизм возврата является полезным программным механизмом, т.к. он освобождает пользователя от необходимости программировать данную процедуру самому.

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

В Турбо-Прологе имеется две возможности управлять возвратом:

- с помощью предиката возврата fail, который используется для безусловного возврата и поиска всех возможных решений.

- с помощью предиката отсечения cut, который используется для предотвращения возврата (обычно в программе обозначается восклицательным знаком «!»).

Рассмотрим действие каждого из этих предикатов на примерах приводимых ниже программ.

/* Программа 5 */

domains

person = symbol

predicates

roditel(person, person)

vse_reshenia

/* goal vse_reshenia. */

clauses

roditel(ola, sasha).

roditel(vita, sasha).

roditel(vita, kata).

roditel(sasha, ana).

roditel(sasha, vera).

roditel(vera, kola).

Vse_reshenia:-roditel(X,y), write(X, "родитель", y), nl, fail.

Данная программа отличается от предыдущей программы 3 добавлением предиката vse_reshenia и правила, определяющего этот предикат. Кроме того, в данной программе имеется раздел goal, который помещён в символы комментариев и, следовательно, пока "не работает".

Поставим для программы 5 задачу "Кто чей родитель":

Goal : roditel(X,Y).

Так как данная задача определяется как внешний запрос, то Турбо-Пролог выдаёт все возможные решения, т.е:

X=ola, Y=sasha

X=vita, Y=sasha

. . .

6 Soltions

Если же снять символы комментариев с раздела goal программы, то будет решаться внутренняя задача, определяемая предикатом vse_reshenia. Она решается в соответствии с правилом, определяющим данный предикат в разделе clauses. В это правило (точнее его правую часть) входят предикаты roditel(X, Y), write(X, "родитель", Y), символ управления печатью nl, и предикат fail, который вынуждает Турбо-Пролог повторно выполнять все идущие перед ним предикаты до нахождения всех возможных альтернативных решений (если они существуют). Фактически в правой части правила, определяющего целевой предикат vse_reshenia, значимой подзадачей, имеющей альтернативные решения является идущая первой после функтора правила подзадача roditel(X, Y). Поэтому после нахождения первого решения для предиката roditel(X, Y) Турбо-Пролог, в соответствии с логикой управления поиском принятия решений, задаваемой предикатом vse_reshenia, будет возвращаться к поиску других его решений, пока они есть. В результате будут получены те же шесть решений, как и в случае внешнего запроса, однако форма выдачи на экран результата будет уже определяться используемым стандартным предикатом write, входящем в правило. Т.о. получим:

ola - родитель sasha