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

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

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

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

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

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

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

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

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

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

. . .

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

Страна / Цвет

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

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

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

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

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

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

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

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий