Лекция 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) , XW, !. 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 параллелограмма, а также угол между ними, найдите диагонали параллелограмма и его площадь;
