конк(L1,L2,L3), где L1 и L2 – два списка, а L3 – список, получаемый при их сцеплении.
Например: конк([a,b], [c,d], [a,b,c,d]) истинно,
конк([a,b], [c,d], [a,b,a,c,d]) ложно,
конк([a,b], [c,d], [a,b,d,c]) ложно.
Нам придётся рассмотреть два случая в зависимости от вида первого аргумента L1.
1) Если первый аргумент пуст, тогда второй и третий аргументы представляют собой один и тот же список.
На Прологе: конк([ ], L, L).
2) Если первый аргумент отношения «конк» не пуст, то он имеет голову и хвост и выглядит так: [G|Hvost1].
Рассмотрим графически, как происходит сцепление списка [G|Hvost1] с произвольным списком L2.
G
Hvost1
L2
↓
↓
↓
G
Hvost3
Hvost1=L1=[G|Hvost1],
L2=L2
Hvost3=L3=[G|Hvost3], где Hvost3 получен путём сцепления Hvost1 и L2.
На Прологе: конк([G,Hvost1], L2, [G|Hvost3]) :- конк(Hvost1, L2, Hvost3).
Отношение «конк» можно использовать в обратную сторону, т.е. для разбиения заданного списка на две части.
Например, если задать Пролог-системе вопрос: ?конк(L1,L2,[a,b,c]),
то Пролог-система выдаст последовательно все варианты разбиения:
L1=[ ] | L1=[a] | L1=[a,b] | L1=[a,b,c]
L2=[a,b,c] | L2=[b,c] | L2=[c] | L2=[ ]
Также, отношение конк можно использовать для поиска в списке комбинации элементов, отвечающей некоторому условию, задаваемому в виде шаблона или образца.
Например, можно найти все месяцы, предшествующие данному, и все месяцы, следующие за ним, сформулировав цель:
В процессе достижения целей Пролог-система осуществляет автоматический перебор вариантов, делая возврат при неуспехе какого-либо из них. Такой перебор – полезный механизм, который освобождает пользователя от необходимости программировать его самому. С другой стороны неограниченный перебор может стать источником неэффективности программы. Поэтому иногда его следует ограничить или исключить полностью. Для этого в Прологе используется конструкция отсечение.
Пример.
Добавим:
отец (“Том”,”Боб”).
отец (“Том”,”Лиз”).
отец (“Боб”,”Пат”).
отец (“Боб”,”Энн”).
И отношение дед:
дед (X,Y) :- отец (Z,Y), отец (X,Z).
Вопрос:
? дед (Х,”Боб”).
Шаги вычисления:
1) Y=”Боб” отец (Z, ”Боб”), отец (X,Z).
2) Z=”Том” отец (X,”Том”).
3) отец (X,”Том”).
Fail – происходит возврат.
Чтобы остановить работу механизма возврата, после доказательства 1 цели в теле правила «дед» ставится предикат отсечения.
дед (X,Y) :- отец (Z,Y), !, отец (X,Z).
Не могут быть пересогласованы цели, стоящие до отсечения, даже если они включают и головную часть.
Предикат fail – неуспех, true – успех. Это 2 предиката для управления перебором.
Предикат fail всегда терпит неудачу, true – заканчивается успешно.
Пример.
«Энн встречается со всеми своими родственницами, кроме Лиз».
встречается (“Энн”, Х) :- X=”Лиз”, !, fail.
встречается (“Энн”, Х) :- женщина (Х).
различны (Х, Х) :- !, fail.
различны (_, _).
различны (Х, Y) :- X=Y, !, fail; true.
Предикат repeat. Это цель, которая всегда успешна и всегда может быть пересогласована при возврате.
имя :- repeat, nl, write (“Имя:”), readln(X), встречается (“Энн”, X).
nl – перемещение позиции ввода к началу текущей строки.
readln(X) – чтение
write(X) – вывод.
Решение головоломок методом «образовать и проверить».
Метод «образовать и проверить» - это общий приём, используемый при проектировании алгоритмов и программ. Суть его состоит в том, что один процесс или программа генерирует множество предполагаемых решений задачи, а другой процесс или программа проверяет эти предполагаемые решения, пытаясь найти те из них, которые действительно являются решениями задачи. Используя вычислительную модель Пролога, легко создавать логические программы, реализующие этот метод. Обычно такие программы содержат конъюнкцию двух целей, одна из которых действует как генератор предполагаемых решений, а вторая проверяет, являются ли эти решения приемлимыми:
find(X) :- generate(X), test(X).
Такая Пролог-программа действует подобно обычной процедурной программе, выполняющей генерацию вариантов и их проверку. Процесс продолжается итерационно до тех пор, пока при успешной проверке не будет найдено решение с характерными свойствами или генератор не исчерпает все альтернативные решения.
Однако, программисту нет необходимости интересоваться циклом «образовать и проверить». Он может рассматривать этот метод более абстрактно, как пример недетерминированного программирования. В качестве генератора обычно используется программа для предиката принадлежности:
member (X, [X|H]). /*предикат принадлежности
member (X, [_|H]) :- member (X,H).
Этот предикат порождает множество решений.
На вопрос ? member (X, [a,b,c]) будут даны в требуемой последовательности решения X=a X=b X=c.
Таким образом, предикат member можно использовать в программах, реализующих метод «образовать и проверить» для недетерминированного выбора корректного элемента из некоторого списка.
В качестве примера рассмотрим решение следующей логической головоломки:
Три друга заняли 1, 2 и 3 места в соревнованиях универсиады. Друзья – из разных стран, их зовут по-разному и любят они разные виды спорта. Известно, что:
1) Майкл предпочитает баскетбол и играет лучше, чем американец.
2) Англичанин Саймон играет лучше теннисиста.
3) Игрок в крикет занял первое место.
Необходимо ответить на вопросы:
1. Кто является австралийцем?
2. Каким спортом занимается Ричард?
Подобные головоломки легко решаются посредством конкретизации значений подходящей структуры данных и выделения значения, приводящего к решению. Каждый ключ к разгадке преобразуется в факт относительно структуры данных. Это может быть сделано с использованием абстракции данных до определения точной формы структуры данных.
Проанализируем первый ключ к разгадке: «Майкл предпочитает баскетбол и играет лучше, чем американец». Очевидно. Речь идёт о двух разных людях. Одного зовут Майклом и он занимается баскетболом, в то время как второй – американец. Кроме того, Майкл лучше играет в баскетбол, чем американец.
Предположим, что Friends – это структура данных, подлежащая конкретизации, тогда наш ключ может быть выражен следующей конъюнкцией целей:
play_best (Man1, Man2, Friends), /*играет лучше
name (Man1, “Майкл”), /*имя 1-го мужчины
sport (Man1, “Баскетбол”), /*Майкл предпочитает баскетбол
country (Man2, “Американец”), /*2-ой мужчина – американец.
Аналогично второй ключ можно представить конъюнкцией целей:
play_best (Man1, Man2, Friends),
name (Man1, “Саймон”),
country (Man1, “Англичанин”),
sport (Man2, “Теннис”),
Наконец, третий ключ к разгадке выразится следующим образом:
first (Friends, Man), /*первый
sport (Man, “Крикет”),
Базовая программа для решения головоломок имеет вид:
Всё, что делает эта программа – это последовательное решение каждого ключа и вопроса, которые представляются как цели Пролога и выполняются с использованием метапеременных.
Ключи и вопросы для нашего примера à в программе №2. Но сначала рассмотрим структуру, представляемую ключами, для решения этой головоломки.
Каждый человек имеет 3 атрибута и может быть представлен структурой:
friend (Name, Country, Sport) /*друг (Имя, Страна, Спорт)
Есть три друга, распределение которых в итоге соревнований имеет существенное значение. Это наводит на мысль выбрать в качестве структуры данных для решения задачи упорядоченную последовательность из 3-х элементов, то есть список:
Каждая из целей play_best и member имеет дело с людьми, а остальные цели обращаются к атрибутам людей. Какие функции они выполняют – генерацию или проверку, зависит от того, конкретизированы из аргументы или нет.
Задание; пользуясь изложенным выше методом, написать программу решения головоломки Эйнштейна:
В пяти домах, окрашенных в разные цвета, обитают мужчины разных национальностей. Они держат разных животных, предпочитают разные напитки и курят сигареты разных марок. Известно, что:
1) Англичанин живёт в красном доме.
2) У испанца есть собака.
3) Кофе пьют в зелёном доме.
4) Украинец пьёт чай.
5) Зелёный дом – первый по правую руку от дома цвета слоновой кости.
6) Курильщик «Уинстона» держит улиток.
7) Сигареты «Кул» курят в жёлтом доме.
8) Молоко пьют в среднем доме.
9) Норвежец живёт в крайнем слева доме.
10) Мужчина, курящий «Честерфилд», живёт в доме, соседним с домом мужчины, у которого есть лиса.
11) Сигареты «Кул» курят в доме, соседним с домом, где имеется лошадь.
