Решение логических задач на Прологе

Лекция 8. Обработка списков и решение логических задач

Обработка списков

 

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

Список можно задать перечислением элементов. Например, имена учеников класса: [саша,петя,дима,ксюша,лена].

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

Альтернативный способ задания списка использует понятия головы и хвоста списка.

Например, в списке [X | Y] X - это голова списка, Y - его хвост.

Хвост списка по определению также является списком.

Теперь список может быть определен рекурсивно:

1) пустой список [] - список;

2) [X | Y] - список, если Y - список.

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

1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка;

2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста (в голове правила), через операцию над хвостом (в подцели).

Пример 1: определение числа элементов в списке.

Программа 7

сколько ([], 0).

сколько ([АIВ], N) сколько (В, М), N is М+1.

?- сколько ([саша, игорь, лена]), X).

Ответ: Х=3.

Пример 2: принадлежность элемента списку.

Программа 8

принадлежит (X, [X | Y]).

принадлежит (X, [A |Y ]): - принадлежит (X,Y).

?-принадлежит (4,[1,3,4,9]).

Ответ: да.

Данная программа имеет очень простой декларативный смысл: элемент принад­лежит списку, если он является его головой или принадлежит хвосту списка.

Пример 3: соединение двух списков.

Эту задачу можно описать с помощью следующих предикатов:

а) ограничение рекурсии состоит в том, что если к пустому списку Ц добавить список Р, то в результате получится Р;

б) рекурсия состоит в том, что можно список Р добавить к концу списка [X|Y], если Р будет добавлен к хвосту Y и затем присоединен к голове X (при этом получа­ется список [Х|Т]).

Программа 9.

присоединить([ ], Р, Р).

присоединить([X|Y], Р, [X | Т]):-присоединить(У, Р, Т).

? присоединить(L,[джим..R],[джек,бил,джим,тим,джим,боб]).

Ответ:

L=[джек,бил].

R—[тим джим,боб].

L=[джек,бил,джим,тим].

R=[6o6],

Существует традиция использовать для обозначения предиката слияния двух списков предикативный символ append (по-английски - добавить).

В некоторых случаях постановки вопросов к такого рода программам прихо­дится использовать отсечение (!).

Программа 10.

append([ ], L, L).

append ([А | В]’, С, [А | D]):- append (В, С, D).

?-append(X,Y, [1,2]).

Ответ:

Х=[]

Y=[l,2]

Х=[1]

Y=[2]

Х=[1,2]

Y=[ ].

Если же заменить первое предложение на append([ ], 1, 1):-!. и задать тот же во­прос, то получится правильный ответ:

Х=[]

Y=[l,2].

Пример 4. удаление элементов из списка.

Программа 11 аналогична проверке принадлежности элемента списку, но тре­бует уже трехарного предиката, один аргумент которого указывает удаляемый элемент, второй аргумент - исходный список и третий - список-результат.

 

Программа 11.

удал (X, [X i Y], Y): -!.

удал (X, [Z | Y], [Z | W]): - удал (X, Y, W).

Декларативный смысл: если удаляемый элемент совпадает с головой списка, то результатом программы является хвост списка, иначе удаления производятся из хвоста списка.

Данная программа удаляет первое вхождение в список элемента, связанного с пе­ременной X. Знак отсечения “!”в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта.

Для удаления всех вхождений элемента X программу надо дополнить:

удал (X,[],[]).

удал (X, [X | Y], W):- удал (X, Y, W). удал (X, [Z | Y], W):- удал (X, Y, W).

Декларативный смысл программы таков: пока список не пуст, удалить элемент, если он совпадает с головой списка, значит, отбросить голову списка, а затем удалять его из оставшегося хвоста, иначе надо сразу удалять элемент из хвоста.

Пример 5: индексация элементов списка.

Смысл программы 12 состоит в том, чтобы получить элемент под номером N или узнать номер элемента X.

 

Программа 12.

получить ([X | Y], 1, X).

получить ([W | Y], N, X) N is М+1, получить (Y, М, X).

Пример 6: поиск максимального элемента.

Программа 13.

max ([X], X).

max ([X | Y], X) max (Y, W), X>W,!. max ([X | Y], W) max (Y, W).

Декларативный смысл программы: если в списке один элемент - он и является максимальным, если более одного, то это голова списка, если она больше макси­мального элемента хвоста, или максимальный элемент хвоста.

 

Пример 7: обращение списка.

Данная задача - самая сложная из рассмотренных. Для ее решения важно сооб­разить, что обратить список из одного элемента - означает оставить список без изменения. Обратить более длинный список - обратить его хвост, а потом сзади приставить к нему голову исходного списка.

Программа 14.

обр ([X], [X]).

обр ([X | Y], Z) обр (Y, W), присоединить (W, [X], Z).

В этой программе используется процедура слияния списков, описанная выше. Arity-Prolog располагает значительным числом встроенных предикатов для об­работки списков, так что приведенные программы имеют, в основном, учебный характер.

Решение логических задач на Прологе

 

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

Рассмотрим пример: нарисовать конверт, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии.

Введем обозначения, как показано на рис. 3.17. Ребра графа обозначены буква­ми а, б, в... (литерные константы), вершины - цифрами 1, 2, 3... Опишем струк­туру графа предикатом вида «ребро (S, А, В)», что означает, что от вершины А к вершине В идет ребро S. Так как граф неориентированный, помимо предикатов вида «ребро (S, А, В)» нужны и предикаты «ребро (S, В, А)». Знания о структуре графа можно представить так, как это записано рядом с рис. 3.17.

Рис. 3.17. Задача «конверт»

 

Решением задачи должен явиться список пройденных ребер графа, причем длина его должна быть равна 8 и в нем не должно быть повторяющихся ребер, что можно описать так:

путь(Т,П): - длина(П,8), writeJist(H),!. (1)

путь(Т,П): - ребро(Р,Т,Н),не_принад(Р,П),путь(Н,р>|П]). (2)

Переменная Т обозначает текущую вершину графа, а П - список пройденных ребер. Правило 1 означает, что если длина списка П пройденных вершин становит­ся равной 8, список П выводится на печать. Это правило ограничивает рекурсив­ный перебор вершин и ребер, проводимый правилом 2. Правило 2 является генера­тором перебора, оно перебирает предикаты «ребро()»и находит такое ребро Р из текущей вершины Т в новую Н, чтобы оно не принадлежало списку П, затем это ребро добавляется в качестве головы к списку П, и поиск дальнейшего пути произ­водится уже из новой вершины Н.

Нам потребуется программа, определяющая длину списка,

длина ([], 0).

длина ([А | В], N):- длина (В, М), N is М+1.

а также программа вывода элементов списка на экран

write_list([ ]).

write_list([H | T]):-write(H),writeJist(T).

Задание

?-путь(4,[ ]).

- искать путь, начиная с вершины 4 и пустого списка пройденных ребер.

Ответ: з, ж, в, а, б, д, г, е.

На вопрос?-путь(1,[ ]) ответ - «НЕТ».

Аналогично решаются другие задачи, связанные с поиском пути в графе, удовле­творяющего каким-то дополнительным условиям, например задача о коммивояжере.

Программа будет состоять

a) из базы знаний о структуре графа - вершинах и связывающих их ребрах (каждому ребру может сопоставляться набор весов);

b) из правил, выражающих дополнительные условия и ограничения на решения задачи и часто связанных с обработкой списков;

c) из рекурсивного правила - генератора перебора ребер и вершин с некоторым ограничивающим предложением, целевым условием;

d) из дополнительных процедур и промежуточных определений.

Интересно, что большинство задач, которые считаются логическими, сводятся к задаче поиска пути в некотором графе - графе состояний задачи. К этому типу задач можно отнести и разнообразные игры. Характерными особенностями многих задач являются следующие:

a) наличие неких дискретных состояний, число которых конечно, и одно из них принимается за начальное, а другое (или несколько других) за конечное (искомое);

b) определены правила перехода между состояниями;

c) для каждого состояния заданы определенные условия допустимости (оценки) этого состояния.

При анализе предметной области задачи эти состояния, правила перехода и ус­ловия допустимости должны быть выявлены, получены соответствующие обозначе­ния и затем записаны с помощью фраз Хорна.

Рассмотрим задачу: имеются два сосуда - на 3 и на 5 литров. Как отмерить с их помощью 4 литра воды?

В этой задаче состояния связаны с определенным количеством воды V в первом сосуде и W во втором. Начальным состоянием является V=0, W=0, а конечным V=0, W=4. Переходы между состояниями можно записать в виде правил:

сосуды(У1, W1):- сосуды(У2, W2).

Например, правило

сосуды(0, W):- сосуды(У, W).

означает, что вся вода из первого сосуда вылита. Обратим внимание на слово «вода» в условии задачи. Для предметной области, связанной с водой, характерно то, что воду можно просто выливать, и данное правило перехода между состояния­ми допустимо. Если бы задача решалась для молока, то его выливать было бы нельзя, и такое правило было бы недопустимым!

Правило

сосуды(3, W):- сосуды(У, W).

означает, что первый сосуд заполнен полностью.

Не разливая, жидкость можно перелить из одного сосуда в другой только так, что один станет пустым, а другой наполнится. Это можно записать в виде правил

сосуды(3,\У) сосуды(У,\У-У+3). сосуды(У,0)сосуды (V-W,W). сосуды(У,5)сосуды(У-\У+5,\У). сосуды(0,\У)сосуды(У,\У-У).

При решении данной задачи необходимо также избежать повторения одних и тех же состояний - «переливания из пустого в порожнее». Для этого в предикат «сосуды ()» следует добавить 3-й аргумент - список пройденных состояний П. Элементы в него будут добавляться парами:

сосуды(У 1,W 1,[V 1,\V 1 |П])не_принад(У I,W 1,П), сосуды(У2,\У2,П).

Условие, ограничивающее рекурсию, должно иметь вид: сосуды(_,4,П):- writejist(n).

 

 

Контрольные вопросы и задания

 

1. В чем состоят принципиальные различие процедурных и декларативных языков программирования?

2. Каковы этапы программирования на Прологе?

3. Какие типы данных допускает Пролог?

4. В чем существо операции сопоставления?

5. Как реализуются вопросы к программе на Прологе?

6. Приведите примеры рекурсий, отличные отданных в тексте.

7. Для чего служит предикат отсечения?

8. Для чего служат списки и как они задаются?

9. Опишите на Прологе:

а) свою родословную, определите бабушек, дедушек, прабабушек, прадеду­шек и т.д.;

б) телефонную книгу;

в) районы вашего города, республики, области, укажите численность их на селения, местные достопримечательности;

г) европейские государства (население, площадь и т.д.);

д) таблицу дат и событий русской истории;

е) небольшой словарь для перевода с русского языка на иностранный язык, который вы изучаете;

ж) ведомость зачета вашей группы;

з) успеваемость вашей группы (дайте определение «отличника»);

и) каталог книг в библиотеке.

10. Запишите на Прологе правила, являющиеся решением следующих заданий:

а) даны два числа а и Ь, получите их сумму, разность, произведение;

б) дана длина ребра куба, найдите объем куба и площадь его боковой по­верхности;

в) дан радиус основания г и высота цилиндра h, найдите его объем и пло­щадь боковой поверхности;

г) даны стороны а и b параллелограмма, а также угол между ними, найдите диагонали параллелограмма и его площадь;