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



Глава 8 5 4 Повышение эффективности зa счет добавления вычисленных фактов к базе данных



8. 5. 4.    Повышение эффективности зa счет добавления вычисленных фактов к базе данных

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

В качестве примера рассмотрим программу вычисления N-го числа Фибоначчи для некоторого заданного N. Последовательность Фибоначчи имеет вид:

        1,  1,  2,  3,  5,   8,  13,  ...

Каждый член последовательности, за исключением первых двух, представляет собой сумму предыдущих двух членов. Для вычисления N-гo числа Фибоначчи F определим предикат

        фиб( N, F)

Нумерацию чисел последовательности начнем с N = 1. Программа для фиб обрабатывает сначала первые два числа Фибоначчи как два особых случая, а затем определяет общее правило построения последовательности Фибоначчи:

        фиб( 1, 1).                             % 1-е число Фибоначчи

        фиб( 2, 1).                             % 2-е число Фибоначчи

        фиб( N, F) :-                         % N-е число Фиб., N > 2
                N > 2,
                N1 is N - 1, фиб( N1, F1),
                N2 is N - 2, фиб( N2, F2),
                F is F1 + F2.
               % N-e число есть сумма двух
                                                    % предыдущих

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

        ?-  фиб( 6, F).

На Рисунок 8.2 показано, как протекает этот вычислительный процесс. Например, третье число Фибоначчи f( 3) понадобилось в трех местах, и были повторены три раза одни и те же вычисления.

Этого легко избежать, если запоминать каждое вновь вычисленное число. Идея состоит в применении встроенной процедуры assert для добавления этих (промежуточных) результатов в базу данных в виде фактов. Эти факты должны предшествовать другим предложениям, чтобы предотвратить применение общего правила в случаях, для которых результат уже известен. Усовершенствованная процедура фиб2 отличается от фиб только этим добавлением:

        фиб2( 1, 1).                         % 1-е число Фибоначчи

        фиб2( 2, 1).                         % 2-е число Фибоначчи

        фиб2( N, F) :-                      % N-e число Фиб., N > 2
                N > 2,
                Nl is N - 1, фиб2( N1, F1),
                N2 is N - 2, фиб2( N2, F2),
                F is F1 + F2,
                       % N-e число есть сумма
                                                            % двух предыдущих
                asserta( фиб2( N, F) ).      % Запоминание N-го числа

Эта программа, при попытке достичь какую-либо цель, будет смотреть сперва на накопленные об этом отношении факты и только после этого применять общее правило. В результате, после вычисления цели фиб2( N, F), все числа Фибоначчи вплоть до N-го будут сохранены. На Рисунок 8.3 показан процесс вычислении 6-го числа при помощи фиб2. Сравнение этого рисунка с Рисунок 8.2. показывает, на сколько уменьшилась вычислительная сложность. Для больших N такое уменьшение еще более ощутимо.

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



Содержание Назад Вперед