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

Можно было бы построить такой правильно упорядоченный список стран вручную, но в этом нет необходимости. Эту работу выполнит процедура создспис. Она начинает построение с некоторой указанной страны (в нашем случае — с Западной Германии) и собирает затем остальные страны в список под названием Закрытый. Каждая страна сначала попадает в другой список, названный Открытый, а потом переносится в Закрытый. Всякий раз, когда страна переносится из Открытыйв Закрытый, ее соседи добавляются в Открытый.

создспис( Спис) :-

собрать( [запгермания], [], Спис ).

собрать( [], Закрытый, Закрытый).

% Кандидатов в Закрытый больше нет

собрать( [X | Открытый], Закрытый, Спис) :-

принадлежит( X | Закрытый), !,

% X уже собран ?

собрaть( Открытый, Закрытый, Спис).

% Отказаться от X

собрать( [X | Открытый], Закрытый, Спис) :-

соседи( X, Соседи),

% Найти соседей X

конк( Соседи, Открытый, Открытый1),

% Поместить их в Открытый

собрать( Открытый1, [X | Закрытый], Спис).

% Собрать остальные

Отношение конк — как всегда — отношение конкатенации списков.

До сих пор в наших программах конкатенация была определена так:

конк( [], L, L).

конк( [X | L1], L2, [X | L3] ) :-

конк( L1, L2, L3 ).

Эта процедура неэффективна, если первый список — длинный. Следующий пример объясняет, почему это так:

?- конк( [а, b, с], [d, e], L).

Этот вопрос порождает следующую последовательность целей:

конк( [а, b, с], [d, e], L)

конк( [b, с], [d, e], L') где L = [a | L']

конк( [с], [d, e], L'') где L' = [b | L''']

конк( [], [d, e], L''') где L'' = [c | L''']

true (истина) где L''' = [d, e]

Ясно, что программа фактически сканирует весь первый список, пока не обнаружит его конец.

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

[а, b, с]

можно представить следующими двумя списками:

L1 = [a, b, c, d, e]

L2 = [d, e]

Подобная пара списков, записанная для краткости как L1-L2, представляет собой "разность" между L1 и L2. Это представление работает только при том условии, что L2 — "конечный участок" списка L1. Заметим, что один и тот же список может быть представлен несколькими "разностными парами". Поэтому список [а, b, с]можно представить как

[а, b, с]-[]

или

[a, b, c, d, e]-[d, e]

или

[a, b, c, d, e | T]-[d, e | T]

или

[а, b, с | T]-T

где T — произвольный список, и т.п. Пустой список представляется любой парой L-L.

Поскольку второй член пары указывает на конец списка, этот конец доступен сразу. Это можно использовать для эффективной реализации конкатенации. Метод показан на рис. 8.1. Соответствующее отношение конкатенации записывается на Прологе в виде факта

конкат( A1-Z1, Z1-Z2, A1-Z2).

Давайте используем конкатдля конкатенации двух списков: списка [а, b, с], представленного парой [а, b, с | Т1]-Т1, и списка [d, e], представленного парой [d, e | Т2]-Т2:

?- конкат( [а, b, с | Т1]-T1, [d, e | Т2]-Т2, L ).

Оказывается, что для выполнения конкатенации достаточно простого сопоставления этой цели с предложением конкат. Результат сопоставления:

T1 = [d, e | Т2]

L = [a, b, c, d, e | T2]-T2

Рис. 8.1. Конкатенация списков, представленных в виде разностных пар. L1представляется как A1-Z1, L2как A2-Z2и результат L3 — как A1-Z2. При этом должно выполняться равенство Z1 = А2.

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

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

1, 1, 2, 3, 5, 8, 13, …

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

фиб( N, F)

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

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

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

фиб( N, F) :- % N-e число Фиб., 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-e число Фибоначчи

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

фиб2( N, F) :- % N-e число Фиб., N > 2

N > 2,

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