решения задачи о восьми ферзях
В качестве простого примера повышения эффективности давайте вернемся к задаче о восьми ферзях (см. рис. 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 раза.
В следующем примере такая же простая идея, связанная с изменением порядка, превращает практически неприемлемую временную сложность в тривиальную.
8. 5. 2. Повышение эффективности программы раскраски карты
Задача раскраски карты состоит в приписывании каждой стране на заданной карте одного из четырех заданных цветов с таким расчетом, чтобы ни одна пара соседних стран не была окрашена в одинаковый цвет. Существует теорема, которая гарантирует, что это всегда возможно.
Пусть карта задана отношением соседства
соседи( Страна, Соседи)
где Соседи - список стран, граничащих со страной Страна. При помощи этого отношения карта Европы с 20-ю странами будет представлена (в алфавитном порядке) так:
соседи( австрия, [венгрия, запгермания, италия,
лихтенштейн, чехословакия,
швейцария, югославия]),
соседи( албания, [греция, югославия]).
соседи( андорра, [испания, франция]).
. . .
Решение представим в виде списка пар вида
Страна / Цвет
которые устанавливают цвет для каждой страны на данной карте. Для каждой карты названия стран всегда известны заранее, так что задача состоит в нахождении цветов. Таким образом, для Европы задача сводится к отысканию подходящей конкретизации переменных C1, C2, СЗ и т.д. в списке
[австрия/C1, албания/С2, андорра/С3, . . .]
Теперь определим предикат
цвета( СписЦветСтран)
который истинен, если СписЦветСтран удовлетворяет тем ограничениям, которые наложены на раскраску отношением соседи. Пусть четырьмя цветами будут желтый, синий, красный и зеленый. Условие запрета раскраски соседних стран в одинаковый цвет можно сформулировать на Прологе так:
цвета( [ ]).
