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



         

Повышение эффективности зa счет добавления вычисленных фактов к базе данных - часть 3


                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 такое уменьшение еще более ощутимо.

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

fig8_2.gif (2820 bytes)

Рис. 8. 2.  Вычисление 6-го числа Фибоначчи процедурой фиб.

fig8_3.gif (2414 bytes)

Рис. 8. 3.  Вычисление 6-го числа Фибоначчи при помощи процедуры фиб2, которая запоминает предыдущие результаты. По сравнению с процедурой фиб здесь вычислений меньше (см. рис. 8.2).

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


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