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

В качестве простого примера повышения эффективности давайте вернемся к задаче о восьми ферзях (см. рис. 4.7). В этой программе Y-координаты ферзей перебираются последовательно — для каждого ферзя пробуются числа от 1 до 8. Этот процесс был запрограммирован в виде цели

принадлежит( Y, [1, 2, 3, 4, 5, 6, 7, 8] )

Процедура принадлежитработает так: вначале пробует Y = 1, затем Y = 2, Y = 3 и т.д. Поскольку ферзи расположены один за другим в смежных вертикалях доски, очевидно, что такой порядок перебора не является оптимальным. Дело в том, что ферзи, расположенные в смежных вертикалях будут бить друг друга, если они не будут разнесены по вертикали на расстояние, превышающее, по крайней мере одно поле. В соответствии с этим наблюдением можно попытаться повысить эффективность, просто изменив порядок рассмотрения координат-кандидатов. Например:

принадлежит( Y, [1, 5, 2, 6, 3, 7, 4, 8] )

Это маленькое изменение уменьшит время, необходимое для нахождения первого решения, в 3-4 раза.

В следующем примере такая же простая идея, связанная с изменением порядка, превращает практически неприемлемую временную сложность в тривиальную.

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

Пусть карта задана отношением соседства

соседи( Страна, Соседи)

где Соседи — список стран, граничащих со страной Страна. При помощи этого отношения карта Европы с 20-ю странами будет представлена (в алфавитном порядке) так:

соседи( австрия, [венгрия, запгермания, италия,

лихтенштейн, чехословакия,

швейцария, югославия]).

соседи( албания, [греция, югославия]).

соседи( андорра, [испания, франция]).

...

Решение представим в виде списка пар вида

Страна / Цвет

которые устанавливают цвет для каждой страны на данной карте. Для каждой карты названия стран всегда известны заранее, так что задача состоит в нахождении цветов. Таким образом, для Европы задача сводится к отысканию подходящей конкретизации переменных C1, C2, СЗ и т.д. в списке

[австрия/C1, албания/C2, андорра/С3, ...]

Теперь определим предикат

цвета( СписЦветСтран)

который истинен, если СписЦветСтранудовлетворяет тем ограничениям, которые наложены на раскраску отношением соседи. Пусть четырьмя цветами будут желтый, синий, красный и зеленый. Условие запрета раскраски соседних стран в одинаковый цвет можно сформулировать на Прологе так:

цвета( []).

цвета( [Страна/Цвет | Остальные] ) :-

цвета( Остальные),

принадлежит( Цвет, [желтый, синий, красный, зеленый]),

not( принадлежит( Страна1/Цвет, Остальные),

сосед( Страна, Страна1) ).

сосед( Страна, Страна1) :-

соседи( Страна, Соседи),

принадлежит( Страна1, Соседи).

Здесь принадлежит( X, L) — как всегда, отношение принадлежности к списку. Для простых карт с небольшим числом стран такая программа будет работать. Что же касается Европы, то здесь результат проблематичен. Если считать, что мы располагаем встроенным предикатом setof, то можно попытаться раскрасить карту Европы следующим образом. Определим сначала вспомогательное отношение:

страна( С) :- соседи( С, _ ).

Тогда вопрос для раскраски карты Европы можно сформулировать так:

?- sеtоf( Стр/Цвет, страна( Стр), СписЦветСтран),

цвета( СписЦветСтран).

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

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