Программирование на языке Пролог для искусственного интеллекта


5 1 2 Эксперимент 2



5. 1. 2.    Эксперимент 2

Проделаем теперь еще один эксперимент со второй версией нашей программы. Предположим, мы задаем вопрос:

        ?-  f( 7, Y).

        Y = 4

Проанализируем, что произошло. Перед тем, как был получен ответ, система пробовала применить все три правила. Эти попытки породили следующую последовательность целей:

Попытка применить правило 1:

    7  <  3  терпит неудачу, происходит возврат, и попытка применить правило 2 (точка отсечения достигнута не была)

Попытка применить правило 2:

    3  <=  7  успех, но  7  <   6  терпит неудачу; возврат и попытка применить правило 3 (точка отсечения снова не достигнута)

Попытка применить правило 3:

    6  <=  7  - успех

Приведенные этапы вычисления обнаруживают еще один источник неэффективности. В начале выясняется, что  X  <  3  не является истиной  (7  <  3  терпит неудачу). Следующая цель -   3 =< Х    (3  <=  7- успех).  Но нам известно, что, если первая проверка неуспешна, то вторая обязательно будет успешной, так как второе целевое утверждение является отрицанием первого. Следовательно, вторая проверка лишняя и соответствующую цель можно опустить. То же самое верно и для цели  6 =< Х  в правиле 3. Все эти соображения приводят к следующей, более экономной формулировке наших трех правил:

        если  Х < 3,  то  Y = 0

        иначе, если  3 <= X   и  Х < 6,  то  Y = 2,

        иначе  Y = 4.

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

        f( X, 0) :- X < 3,  !.

        f( X, 2) :- X < 6,  !.

        f( X, 4).

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

        f( X, 0) :- X < 3.

        f( X, 2) :- X < 6.

        f( X, 4).

Она может порождать различные решения, часть из которых неверны. Например:

        ?-  f( 1, Y).

        Y = 0;
        Y = 2;
        Y = 4;

        nо             (нет)

Важно заметить, что в последней версии, в отличие от предыдущей, отсечения затрагивают не только процедурное поведение, но изменяют также и декларативный смысл программы.

Более точный смысл механизма отсечений можно сформулировать следующим образом:

line();

Назовем "целью-родителем" ту цель, которая сопоставилась с головой предложения, содержащего отсечение. Когда в качестве цели встречается отсечение, такая цель сразу же считается успешной и при этом заставляет систему принять те альтернативы, которые были выбраны с момента активизации цели-родителя до момента, когда встретилось отсечение. Все оставшиеся в этом промежутке (от цели-родителя до отсечения) альтернативы не рассматриваются.

line();

Чтобы прояснить смысл этого определения, рассмотрим предложение вида

        Н :- В1, В2, ..., Вm, !, ..., Вn.

Будем считать, что это предложение активизировалось, когда некоторая цель  G   сопоставилась с  Н.  Тогда  G   является целью-родителем. В момент, когда встретилось отсечение, успех уже наступил в целях  В1,  ...,  Вm.  При выполнении отсечения это (текущее) решение  В1,   ...,  Вm  "замораживается" и все возможные оставшиеся альтернативы больше не рассматриваются. Далее, цель  G  связывается теперь с этим предложением: любая попытка сопоставить  G  с головой какого-либо другого предложения пресекается.

Применим эти правила к следующему примеру:

        С :- Р, Q, R, !, S, Т, U.
        С :- V.
        А :- В, С, D.
        ?-  А.

Здесь  А,  В,  С,  D,  Р  и т.д. имеют синтаксис термов. Отсечение повлияет на вычисление цели  С  следующим образом. Перебор будет возможен в списке целей  Р,    Q,  R;  однако, как только точка отсечения будет достигнута, все альтернативные решения для этого списка изымаются из рассмотрения. Альтернативное предложение, входящее в  С:

        С :- V.

также не будет учитываться. Тем не менее, перебор будет возможен в списке целей  S,  Т,   U.  "Цель-родитель" предложения, содержащего отсечения, -это цель  С  в предложении

        А :- В, С, D.

Поэтому отсечение повлияет только на цель  С.   С другой стороны, оно будет "невидимо" из цели  А.  Таким образом, автоматический перебор все равно будет происходить в списке целей  В,  С,  D,  вне зависимости от наличия отсечения в предложении, которое используется для достижения  С.



Начало Назад Вперед


Книжный магазин