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



         

Повышение эффективности программы раскраски карты


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

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

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

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

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

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

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

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

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

        . . .

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

        Страна / Цвет

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

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

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

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

который истинен, если СписЦветСтран

удовлетворяет тем ограничениям, которые наложены на раскраску отношением соседи.


Содержание  Назад  Вперед