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

Цель setof — построить "шаблон" списка СписЦветСтран, в котором в элементах вида страна/ цвет вместо цветов будут стоять неконкретизированные переменные. Предполагается, что после этого цель цвета конкретизирует их. Такая попытка скорее всего потерпит неудачу вследствие неэффективности работы программы.

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

Ясно поэтому, что эффективность зависит от порядка раскраски стран. Интуиция подсказывает простую стратегию раскраски, которая должна быть лучше, чем случайная: начать со страны, имеющей иного соседей, затем перейти к ее соседям, затем — к соседям соседей и т.д. В случае Европы хорошим кандидатом для начальной страны является Западная Германия (как имеющая наибольшее количество соседей — 9). Понятно, что при построении шаблона списка элементов вида страна/цвет Западную Германию следует поместить в конец этого списка, а остальные страны - добавлять со стороны его начала. Таким образом, алгоритм раскраски, который начинает работу с конца списка, в начале займется Западной Германией и продолжит работу, переходя от соседа к соседу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8.5.3. Повышение эффективности конкатенации списков за счет совершенствования структуры данных

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

конк( [], 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.

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

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

В качестве примера рассмотрим программу вычисления 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 число есть сумма

                         % двух предыдущих