Member (Neighbors, Colors I)

Программа 14.4. Раскрашиваниекарты.

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

Отношением верхнего уровня рассматриваемой программы является со1оr_ тар (Map,Colors), где Map – карта, представляемая описанным выше способом, Colors- список цветов, используемых для раскрашивания карты. Выберем цвета: красный, желтый, голубой и белый. Ядро алгоритма – определение отношения color_ region (Region, Colors):

color__region (region (Name, Color, Neighbors), Colors)¬

select (Color, Colors, Colors 1),

Цели select и members в зависимости от того, конкретизированы или нет их аргументы, могут либо производить генерацию вариантов, либо выполнять проверку.

Итогом выполнения программы о раскрашивании карты является конкретизация структуры данных – карты. Вызовы предикатов select и members могут рассматриваться как описания локальных ограничений. Предикаты либо генерируют предполагаемое решение посредством конкретизации элементов структуры,либо проверяют, удовлетворяют ли конкретизированные значениялокальным ограничениям.

В качестве последнего примера рассмотрим решение логической головоломки. Поведение этой программы будет подобно поведению программы для решения задачи о раскрашивании карты. Логическая головоломка состоит из нескольких фактов относительно небольшого числа объектов, которые имеют различные атрибуты. Минимальное число фактов относительно объектов и атрибутов связано с желанием выдать единственный вариант назначения атрибутов объектам.

Тестовые данные

test_color(Name,Map) ¬

map (Name, Map),

colors(Name, Colors),

color_map(Map, Colors).

map(test, [region(a, A, [B, C, D]),

region (b,B, [A, C,E]), region (c,C, [A, B,D,E,F]),

region (d, D, [A,C, F]), region (e, E, [B, C, F]),

region(f,F,[C,D,E])]).

map(west_europe, [region (portugal, P, [E]), region(spain, E, [F, P]),

region(france,F, [E,1,S,B,WG,L]), region(belgium,B,[F,H,L,WG]),

region (holland, H, [B, WG]), region(west_germany, WG, [F, A, S, H. B, L]),

region (luxembourg, L, [F, B, WG]), region (italy, I, [F, A, S]),

region (Switzerland, S, [F, I, A, WG]), region (austria, A, [I, S, WG])]).

colors(X,[red,yellow, blue, white]).

Программа 14.5. Тестовые данные для задачи о раскрашивании карты.

Метод решения логических головоломок опишем на следующем примере.

Три друга заняли первое, второе и третье места в соревнованиях универсиады. Друзья-разной национальности, зовут их по-разному, и любят они разные виды спорта.

Майкл предпочитает баскетбол и играет лучше чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крикет занял первое место.

Кто является австралийцем? Каким спортом занимается Ричард?

Подобные логические головоломки изящно решаются посредством конкретизации значений подходящей структуры данных и выделения значения, приводящего к решению. Каждый ключ к разгадке преобразуется в факт относительно структуры данных. Это может быть сделано с использованием абстракции данных до определения точной формы структуры данных. Проанализируем первый ключ к разгадке: «Майкл предпочитает баскетбол и играет лучше чем американец». Очевидно, речь идет о двух разных людях. Одного зовут Майклом и он занимается баскетболом, в то время как второй – американец. Кроме того, Майкл лучше играет в баскетбол, чем американец. Предположим, что Друзья структура данных, подлежащая конкретизации, тогда наш ключ может быть выражен следующей конъюнкцией целей:

играет __лучше(мужчина 1,Мужчина2,Друзья),

имя(Мужчина 1,Майкл),спорт(Мужчина 1.баскетбол),

национальность(Мужчина2,американец).

Аналогично второй ключ можно представить конъюнкцией целей:

играет _лучше(мужчина1,Мужчина2,Друзья),

имя(Мужчина1,Саймон),национальность(Мужчина1,израильтянин),

спорт(Мужчина2,тенннс).

Наконец, третий ключ к разгадке выразится следующим образом:

первый(Друзья.Мужчина),спорт(Мужчина,крикет).

Базовая программа для решения головоломок представлена программой 14.6. Вычислению подлежит отношение решить _головоломку(Головоломка, Решение), где Решение является решением головоломки Головоломка, Головоломка представляется структурой головоломка(Ключи, Вопросы, Решение), где структура данных, подлежащая конкретизации, представляется ключами и вопросами, а получаемые значения определяются аргументом Решение.

решить головоломку (Головоломки, Решение) ¬

Решение - решение головоломки Головоломки, которая представляется структурой головоломка (Ключи, Вопросы, Решении).

решить_головоломку (головоломка (Ключи, Вопросы, Решение), Решение)¬ решить(Ключи),

решить (Вопросы).

решить ([Ключ [Ключи])¬

Ключ, решить (Ключи). решить([ ]).

Программа 14.6. Решатель головоломок.

Программа решить _головоломку тривиальна. Все, что она делает, состоит в последовательном решении каждого ключа и вопроса, которые представляются как цели Пролога и выполняются с использованием метапеременных.

Ключи и вопросы для нашего примера даны в программе 14.7. Рассмотрим структуру, представляемую ключами, для решения этой головоломки. Каждый человек имеет три атрибута и может быть представлен структурой друг{Имя,Страна,Спорт). Есть три друга, распределение мест которых в итоге соревнований имеет существенное значение. Это наводит на мысль выбрать в качестве структуры данных для решения задачи упорядоченную последовательность из трех элементов, т. е. список:

[Друг(N1,C1,S1), друг(N2.C2,S2), друг (N3,C3,S3)]. Тестовые данные

тест для головоломки (Имя, головоломка (Ключи, Вопросы, Решение))¬

структура (Имя, Структура),

ключи(Имя, Структура, Ключи),

вопросы (Имя, Структура, Вопросы, Решение).

структуpa(Tecт,[Дpyr(N1,C1,S1),дpyr(N2,C2,S2),дpyr(N3,C3,S3)]).

ключи (тест, Друзья,

[(играет_лучше (Мужчина1 Ключ1,Мужчина2 Ключ1, Друзья), % Ключ 1

имя(Мужчина1 Ключ1,майкл),спорт (Мужчина1 Ключ1, баскетбол),

национальность(Мужчина2Ключ1,американец)),

(играет_лучше(Мужчина1Ключ2,Мужчина2Ключ2, Друзья), % Ключ 2

имя(Мужчина1 Ключ2,саймон), национальность (Мужчина 1 Ключ2,

израильтянин),

спорт(Мужчина2Ключ2,теннис)),

первый (Друзья. МужчинаКлюч3),

спорт(МужчинаКлюч3, крикет)) % Ключ 3

]).

вопросы (тест. Друзья,

[принадлежит (Q1, Друзья),

имя(Q1,Имя),

национальность (Q1, австралиец), % Вопрос 1

принадлежит (Q2,Дручья),

имя(Q2,ричард),

спорт (Q2,Спорт) % Вопрос 2

],

[[‘Имя австралийца -',Имя], [‘Ричард играет в ',Спорт]]

).

играет_лучше(А, В, [А, В, С]).

играет_лучше(А, С, [А, В, С]).

играет..лучше (В, С, [А, В, С]).

имя(друг(А,В,С).А).

национальность (друг(А. В, С), В).

спорт (друг (А, В, С), С).

первый ([X | Xs], X).

Программа 14.7. Описание головоломки.

В программе 14.7 даны определения условий играет_лучше, имя, национальность, спорт и первый, которые, очевидно, легко программируются.

Объединение программ 14.6 и 14.7 дает нечто гигантское на тему «образовать и проверить». Каждая из целей играет_лучше и принадлежит (member) имеет дело с людьми, а остальные цели обращаются к атрибутам людей. Какие функции они выполняют генерацию или проверку, зависит от того, конкретизированы их аргументы или нет. Для любопытных сообщаем ответ нашей головоломки: Майкл-австралиец, а Ричард играет в теннис.

Дата добавления: 2014-01-07