Тщательное исследование способа, при помощи которого пролог-система пытается достичь цели
цвета
, обнаруживает источник неэффективности. Страны расположены в списке в алфавитном порядке, а он не имеет никакого отношения к их географическим связям. Порядок, в котором странам приписываются цвета, соответствует порядку их расположения в списке (с конца к началу), что в нашем случае никак не связано с отношением
соседи
. Поэтому процесс раскраски начинается в одном конце карты, продолжается в другой и т.д., перемещаясь по ней более или менее случайно. Это легко может привести к ситуации, когда
при попытке раскрасить очередную страну окажется, что она окружена странами, уже раскрашенными во все четыре доступных цвета. Подобные ситуации приводят к возвратам, снижающим эффективность.
Ясно поэтому, что эффективность зависит от порядка раскраски стран. Интуиция подсказывает простую стратегию раскраски, которая должна быть лучше, чем случайная: начать со страны, имеющей иного соседей, затем перейти к ее соседям, затем — к соседям соседей и т.д. В случае Европы хорошим кандидатом для начальной страны является Западная Германия (как имеющая наибольшее количество соседей — 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 ).
Оказывается, что для выполнения конкатенации достаточно простого сопоставления этой цели с предложением