Cодержание

1. Постановка задачи

2. Решение

1. Постановка задачи

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

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

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

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

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

2. Решение

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

(did_better(Man1Clue1, Man2Clue1, Friends)
name_(Man1Clue1, michael), sport(Man1Clue1,basketball),
nationality(Man2Clue1,american)

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

did_better(Man1Clue2, Man2Clue2, Friends)
name_(Man1Clue2, simon), nationality(Man1Clue2,israeli),
sport(Man2Clue2,tennis)).

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

first(Friends,ManClue3),sport(ManClue3,cricket)

Базовая программа для решения головоломок представлена программой 14.6. Вычислению подлежит отношение solve_puzzle( Puzzle,Solution), где Solution является решением головоломки Puzzle. Головоломка представляется структурой puzzle(Clues,Queries,Solution), где структура данных, подлежащая конкретизации, представляется ключами и вопросами а получаемые значения определяются аргументом Solution.

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

solve_puzzle(puzzle(Clues,Queries,Solution),Solution) :-
solve(Clues),
solve(Queries).
 
solve([Clue|Clues]) :-
Clue, solve(Clues).
solve([]).
 
test_puzzle(Name,Solution) :-
structure(Name,Structure),
clues(Name,Structure,Clues),
queries(Name,Structure,Queries,Solution),
solve_puzzle(puzzle(Clues,Queries,Solution),Solution).
 
structure(test,[friend(N1,C1,S1), friend(N2,C2,S2), friend(N3,C3,S3)]).
 
clues(test,Friends,
[(did_better(Man1Clue1, Man2Clue1, Friends), % Clue 1
name_(Man1Clue1, michael), sport(Man1Clue1,basketball),
nationality(Man2Clue1,american)),
(did_better(Man1Clue2, Man2Clue2, Friends), % Clue 2
name_(Man1Clue2, simon), nationality(Man1Clue2,israeli),
sport(Man2Clue2,tennis)),
(first(Friends,ManClue3),sport(ManClue3,cricket))]).
 
queries(test, Friends,
[ member(Q1,Friends),
name_(Q1,Name),
nationality(Q1,australian), % Query 1
member(Q2,Friends),
name_(Q2,richard),
sport(Q2,Sport) % Query 2],
[['The Australian is', Name], ['Richard plays ', Sport]]).
 
did_better(A,B,[A,B,C]).
did_better(A,C,[A,B,C]).
did_better(B,C,[A,B,C]).
 
name_(friend(A,B,C),A).
nationality(friend(A,B,C),B).
sport(friend(A,B,C),C).
 
first([X|Xs],X).

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

[frienfd(N1, C1, S1), friend (N2, C2, S2), friend (N3, C3, S3)].

В программе 14.7 даны определения условий did_better,name, nationality, sport и first, которые, очевидно, легко программируются.

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