принадлежит(Х,[Х|_]).
принадлежит(Х,[_|Y]):- принадлежит(Х,Y).
Следующая операция 'включение' реализуется предикатом включает, причем включает(Х, Y)завершается успешно, если Xявляется подмножеством Y, т. е. Yвключает X. Второе утверждение в его определении опирается на математическое соглашение о том, что пустое множество является подмножеством любого множества. В Прологе это соглашение дает способ проверки граничного условия для первого аргумента, поскольку запрограммирована рекурсивная обработка его хвоста:
включает([А|Х],Y):- принадлежит(А,Y), включает(Х,Y).
включает([],Y).
Следом идет самый сложный случай, реализация пересечения. Целевое утверждение пересечение(Х, Y,Z) доказуемо, если пересечением Xи Yявляется Z. Это как раз тот случай, когда используется предположение, что данные списки не содержат повторяющихся элементов:
пересечение([], X, []).
пересечение([X|R],Y,[X|Z]):-принадлежит(Х, Y),!,пересечение(R, Y,Z).
пересечение([Х|R],Y,Z):- пересечение(R, Y,Z).
Наконец, объединение. Целевое утверждение объединение (X,Y,Z)доказуемо, если объединением Xи Yявляется Z. Заметим, что реализация предиката объединениесконструирована на основе определений предикатов пересечениеи присоединить:
объединение([],Х,Х).
объединение([Х|R],Y,Z):- принадлежит(Х,Y),!,
объединение(R,Y,Z). объединение([X |R],Y,[X|Z]):- объединение(R,Y,Z).
Этим исчерпывается наш перечень предикатов работы с множествами. И хотя использование множеств может оказаться не характерным для ваших программ, тем не менее полезно изучить эти примеры. Они позволяют вам получить ясное представление о том, как можно использовать рекурсию и возвратный ход.
7.7. Сортировка
Иногда полезно упорядочить список элементов в соответствии с заданным порядком их следования. Если элементами списка являются целые числа, то для того чтобы определить соблюден ли порядок следования, можно использовать предикат '‹'. Список (1, 2, 3) упорядочен, поскольку любая пара соседних целых чисел этого списка удовлетворяет предикату '‹'. Если элементами списка являются атомы, то мы можем воспользоваться предикатом меньше,о чем уже говорилось в гл. 3. Список [alpha,beta,gamma]упорядочен в алфавитном порядке, поскольку каждая пара соседних атомов этого списка удовлетворяет предикату меньше.
Специалисты по информатике разработали много методов сортировки списков, когда задан некоторый предикат, который говорит нам о том, находятся ли соседние элементы списка в требуемом порядке следования. Мы рассмотрим Пролог-программы для четырех таких методов: наивная сортировка, сортировка включением (вставками), сортировка методом пузырька и быстрая сортировка. В каждой программе используется предикат упорядочено, который может быть определен через '‹' меньшеили любой другой предикат по вашему усмотрению, в зависимости от того, какого рода структуры вы сортируете. При этом предполагается, что целевое утверждение упорядочено(Х, Y)доказуемо, если объекты Xи Yудовлетворяют требуемому порядку следования, т. е. если Xв некотором смысле меньше чем Y.
Один из способов сортировки чисел в порядке возрастания состоит в следующем: вначале создается некоторая перестановка чисел, затем проверяется расположен ли полученный список в порядке возрастания. Если это не так, то создается новая перестановка чисел. Этот метод известен под названием наивная сортировка:
наивсорт(L1,L2):- перестановка(L1,L2),отсортировано(L2),!.
перестановка(L,[H|T]):-присоединить(V,[Н|U],L), присоединить(V,U,W), перестановка(W,Т).
перестановка([],[]).
отсортировано(L):- отсортировано(0,L).
отсортировано(_,[]).
отсортировано(N,[H|T]):- упорядочено(N,Н),отсортировано(Н,T).
Используемый здесь предикат присоединитьмногократна определялся ранее. В этой программе предикаты имеют следующий смысл:
Наивсорт(L1, L2)означает, что L2– это список, являющийся упорядоченной версией списка L1;
Перестановка(L1, L2)означает, что L2- это список, содержащий все элементы списка L1в одном из многих возможных порядков их следования; в терминологии разд. 4.3 – это генератор.
Предикат отсортировано(L)означает, что числа в списке Lупорядочены в порядке возрастания; это – 'контролер'.
Процесс поиска упорядоченной версии списка заключается в создании некоторой перестановки элементов и проверки ее упорядоченности. Если это так, то единственный ответ найден. Иначе мы вынуждены продолжать создание перестановок. Это не очень эффективный метод сортировки списка.
При сортировке включениемкаждый элемент списка рассматривается отдельно и включается в новый список на соответствующее место. Этот метод используется, например, при игре в карты, когда игрок сортирует имеющиеся на руках карты, вынимая и переставляя по одной карте за раз. Целевое утверждение вклюсорт(X, Y)доказуемо тогда, когда список Yявляется упорядоченной версией списка X. Каждый элемент удаляется из головы списка и передается предикату вклюсорт2, который включает этот элемент в список и возвращает измененный список.
вклюсорт([],[]).
вклюсорт([Х|L],М):- вклюсорт(L,N), вклюсорт2(Х,N,М).
вклюсорт2(Х,[А|L],[А|М]):- упорядочено(А,Х),!,вклюсорт2(Х,L,М).
вклюсорт2(Х,L,[Х |L]).
Чтобы сделать предикат сортировки включением более универсальным, удобно задавать предикат проверки порядка следования в качестве аргумента предиката вклюсорт.Используем для этого предикат ' =..', который рассматривался в гл. 6:
вклюсорт([],[],_).
вклюсорт([Х|L],М,О):- вклюсорт(L,N,О),вклюсорт2(Х,N,М,О).
вклюсорт2(Х,[А|L],[А|М],0):-Р=..[O,А,Х], call(P),! ,вклюсорт2(Х,L,М,O).
вклюсорт2(Х,L,[Х|L],О).
Теперь мы можем использовать такие цели как вклюсорт(А,В,'‹') и вклюсорт(А,В,меньше),т. е. отпадает необходимость в предикате упорядочено.Этот метод может быть распространен.и на другие алгоритмы сортировки данного раздела.
При сортировке методом пузырькав списке ищется пара соседних элементов, расположенных не по порядку следования. Если такие элементы находятся, то они меняются местами. Этот процесс продолжается до тех пор, пока перестановки станут ненужными. Если при сортировке включением выбранный элемент как бы «тонет», попадая на нужное место, то сортировка методом пузырька названа так потому, что здесь элементы, подобно пузырькам воздуха, постепенно «всплывают», занимая соответствующее место.
пусорт(L,S):-присоединить(Х,[А,В|Y],L),упорядочено(В,А),присоединить(Х, [В, А|Y],M),пусорт(M,S).
пусорт(L,L).
присоединить([],L,L).
присоединить([Н|Т],L[Н|V]):- присоединить(Т,L,V).
Заметим, что здесь применяется тот же самый предикат присоединить, с которым мы встречались ранее. Этот пример отличается от предыдущих необходимостью возвратного хода после каждого найденного решения. Поэтому в первом правиле в определении пусорт«отсечение» не используется. Эта программа еще один пример «недетерминированного» программирования,- для выбора элементов списка L здесь используется предикат присоединить. При этом контроль полноты выполненных перестановок целиком возложен на присоединить.
Быстрая сортировка- это более сложный метод сортировки, предложенный Хоором и применимый для сортировки больших списков. Для реализации быстрой сортировки на Прологе мы должны сначала разделить список, состоящий из головы Ни хвоста Т, на два списка Lи Мтакие, что:
• все элементы Lменьше или равны Н;
• все элементы Мбольше чем Н;
• порядок следования элементов в Lи Мтакой же как в [Н |Т].
После того, как мы разделили список, применяем быструю сортировку к каждому из полученных списков (это рекурсивная часть), и присоединяем Мк LЦель разбить(H,T,L,M)разделяет список [Н |Т]на списки Lи М, как сказано выше:
paзбить(H,[A|X],[A|Y],Z):- А=‹ Н, разбить(Н,Х,Y,Z).
разбить(Н,[А|Х],Y,[А|Z]):- А › Н, разбить(Н,Х,Y,Z).
разбить(_,[], [],[]).
Тогда программа быстрой сортировки примет вид:
бысорт([],[]).
бысорт([H|T],S):-разбить(Н,Т,А,В),бысорт(А,А1),бысорт(В,В1), присоединить(А1, [H|B1],S).
Предикат присоединитьможно встроить внутрь программы сортировки. Тогда получается другой предикат
бысорт2 ([H|T], S,X):-разбить(Н,T,А,В), бысорт2(А,S,[Н|Y]), бысорт2(B,Y,X).
бысорт2([],Х,Х).
В этом случае третий аргумент используется как временная рабочая область, и при обращениях к бысорт2этот аргумент должен заполняться пустым списком.
Более подробные сведения о методах сортировки можно найти в книге D. Knuth, The Art of Computer Programming,v. 3 (Sort and Searching), Addison-Wesley, 1973 (Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3 (Сортировка и поиск). М.: Мир, 1978.- Перев.)Метод быстрой сортировки Хоора описан в его статье в Computer Journal n. 5 (1962), стр. 10-15.
Упражнение 7.5.Проверьте, что предикат перестановка (L1, L2)строит все перестановки заданного списка L1(причем каждую по одному разу) и выдает их как альтернативные значения списка L2. В каком порядке строятся эти решения?
Упражнение 7.6.Быстрая сортировка лучше всего работает ка больших списках, поскольку там она обеспечивает более быструю сходимость к решению. В то же время объем работы, выполняемой на каждом уровне рекурсии быстрой сортировки, превышает то, что делается в других методах, из-за использования разбить. Поэтому, при сортировке небольших списков рекурсивные вызовы бысорт,видимо, можно заменить обращениями к другим методам сортировки, например, к сортировке включением. Разработайте «гибридную» программу, которая использует быструю сортировку для обработки больших подсписков (списков, полученных с помощью предиката разбить),но переключается на другой метод (сортировка включением) при значительном уменьшении длины подсписка. Подсказка: поскольку разбитьдолжен просмотреть все элементы списка, то он может заодно подсчитать и длину списка.
7.8. Использование базы данных: random, генатом, найтивсе
Во всех программах, которые рассматривались до сих пор, база данных использовалась лишь для хранения фактов и правил, с помощью которых определяются предикаты. Можно использовать базу данных и для хранения обычных структур, т. е. таких, которые порождаются при выполнении программы. До сих пор для передачи таких структур от одного предиката к другому мы применяли механизм аргументов. Однако существуют доводы в пользу хранения этой информации в базе данных. Иногда некоторый элемент информации может потребоваться во многих частях программы. Передача его через механизм аргументов может привести к появлению одного – двух дополнительных аргументов у большинства предикатов. Другим доводом является возможность сохранения информации при возвратном ходе. В этом разделе мы рассмотрим три предиката, которые позволяют хранить в базе данных структуры, время жизни которых превышает то, что может быть обеспечено с помощью переменных. Вот эти три предиката: random,вырабатывающий при каждом вызове псевдослучайное целое, найтивсе,порождающий список всех структур, обеспечивающих истинность данного предиката, и генатом,порождающий атомы с различающимися именами.
Цель random(R, N)конкретизирует Nцелым числом, случайно выбранным в диапазоне от 1до R. Метод выбора случайного числа основан на конгруэнтном методе с использованием начального числа («затравки») инициализируемого произвольным целым числом. Каждый раз, когда требуется случайное число, ответ вычисляется на основе существующего начального значения, и при этом порождается новое начальное число, которое сохраняется до тех пор, пока вновь не потребуется вычислить случайное число. Для хранения начального числа между вызовами randomмы используем базу данных. После того как начальное число использовано, мы убираем (с помощью retract)из базы данных старую информацию о начальном числе, вычисляем его новое значение, и засылаем в базу данных новую информацию (с помощью asserta).Исходное начальное значение – это просто факт в базе данных, с функтором seedимеющим одну компоненту – целое значение начального числа.
seed(13).
random (R,N):-seed(S),N is (S mod R) + 1,retract(seed(S)),NewSeed is (125 * S + 1) mod 4096,asserta(seed(NewSeed)),!.
Используя семантику retractможно упростить определение randomследующим образом:
random(R,N):-retract(seed(S)),N is (S mod R)+1,NewSeed is (125 * S +1) mod 4096,asserta(seed(NewSeed)),!.
Для того, чтобы напечатать последовательность случайных чисел, расположенных в диапазоне между 1 и 10, которая обры-вается после того, как будет порождено значение 5, нужно задать следующий вопрос:
?- repeat, random(10,X), write(X), nl, X=5.
Предикат генатомпозволяет порождать новые атомы Пролога. Если у нас есть программа, которая воспринимает информацию об окружающем мире (например, путем анализа описывающих его предложений на английском языке), то в случае появления в этом мире нового объекта возникают трудности с его обозначением. Естественно представлять объект атомом Пролога. Если объект ранее не встречался, мы должны убедиться в том, что тот атом, который мы ему сопоставляем, случайно не совпал с другим атомом, уже представляющим какой-то другой объект. Иными словами, нам необходимо иметь возможность формировать новые атомы. Мы можем также потребовать, чтобы созданный атом имел также некоторое мнемоническое значение: это облегчит понимание информации выводимой нашей программой. Если бы атомы представляли, скажем, студентов, то целесообразно было быназвать первого студента – студент1,второго – студент2, третьего – студентЗи т. д. Если к тому же нам нужно было бы работать с объектами представляющими еще и преподавателей, то можно было бы выбрать для их представления атомы преподаватель1, преподаватель2, преподавательЗи т. д.
Функция программы генатомсостоит в том, чтобы порождать новые атомы от заданных корней (таких как студенти преподаватель).Для каждого корня программа запоминает, какой номер был использован в последний раз. Поэтому, когда в следующий раз от нее требуется породить атом с данным корнем можно гарантировать, что он будет отличаться от тех, что были порождены ранее. Так, когда вопрос
?- генатом(студент,X).
задан впервые, ответом будет
X = студент1
В следующий же раз ответом будет
X = студент2
и т. д.
Заметим, что эти различающиеся решения при возвратном ходе не порождаются ( генатом(Х, Y)нельзя согласовать вновь), они порождаются последующими целями, включающими этот предикат.
В определении генатомиспользуется вспомогательный предикат тек_номер. Контроль за тем, какой номер использовать следующим для данного корня, осуществляется программой генатомпутем записи в базу данных фактов вида тек_номери удаления фактов, которые стали ненужными. Факт тек_номер (Корень, Номер)означает, что последний номер, использованный с корнем Корень,был Номер.Иными словами, последний атом, порожденный для этого корня, состоял из литер, взятых из Корень,за которыми был приформирован номер, взятый из Номер.Когда Пролог пытается доказать согласованность цели генатом, обычно делается следующее: последний факт тек_номердля заданного корня удаляется из базы данных, к его номеру прибавляется 1, и новый факт тек_номерзапоминается в базе данных, заменяя исключенный факт. С этого момента новый номер может быть использован как основа для порождения нового атома. Хранить информацию о текущем номере в базе данных очень удобно. В противном случае каждый предикат, прямо или косвенно участвующий в выполнении генатом, должен был бы пересылать информацию о текущих номерах через дополнительные аргументы.
Последние несколько утверждений этой программы определяют предикат целое_имя,который используется для преобразования целого числа в последовательность литер-цифр. Атомы, порождаемые генатом,формируются с помощью встроенного предиката name,который формирует атом из литер корня, за которыми следуют цифры номера. В некоторых реализациях Пролога используется версия предиката name,которая выполняет также функции предиката целое_имя,однако весьма поучительно посмотреть, как его можно определить на Прологе. В этом определении неявно используется тот факт, что коды ASCII для цифр 0, 1, 2 и т. д. равны соответственно 48, 49, 50 и т. д. Поэтому, чтобы преобразовать число меньшее 10 в код ASCII соответствующей цифры, достаточно прибавить к этому числу 48. Перевести в последовательность литер число, большее 9, сложнее. Последнюю цифру такого числа получить легко, поскольку это просто остаток от деления на 10 (число mod 10).Таким образом, цифры числа легче формировать в обратном порядке. Мы просто циклически повторяем следующие операции: получение последней цифры, вычисление остальной части числа (результат его целого деления на 10). Определение этого на Прологе выглядит следующим образом:
цифры_наоборот(N,[С]):- N‹10,!, С is N+48.
цифры_наоборот(М,[С|Сs]):-С is (N mod 10) + 48,N1 is N/10,цифры_нaoбopот(N1,Cs).
Чтобы получить цифры в правильном порядке, применим трюк: в этот предикат добавим дополнительный аргумент – список «уже сформированных» цифр, С помощью этого аргумента мы можем получать цифры по одной в обратном порядке, но в итоговый список вставлять их в прямом порядке. Это делается следующим образом. Пусть у нас есть число 123. В начале список «уже сформированных» цифр есть []. Первым получаем число 3, которое преобразуется в литеру с кодом 51. Затем мы рекурсивно вызываем целое_имя,чтобы найти цифры числа 12. Список «уже сформированных» цифр, который передается в это целевое утверждение, содержит литеру, вставленную в исходный список «уже сформированных» цифр – это список [51]. Вторая цель целое_имявыдает код 50 (для цифры 2) и снова вызывает целое_имя,на этот раз с числом 1 и со списком «уже сформированных» цифр [50, 51]. Эта последняя цель успешно выполняется и, поскольку число было меньше 10, дает ответ [49,50,51]. Этот ответ передается через аргументы разных целей целое_имяи дает ответ на исходный вопрос – какие цифры соответствуют числу 123?
Приведем теперь всю программу полностью.
/* Породить новый атом, начинающийся с заданного корня, и оканчивающийся уникальным числом. */
генатом (Корень,Атом),выдать_номер(Корень,Номер), name(Корень,Имя1), целое_имя(Номер,Имя2), присоединить(Имя1,Имя2,Имя), name(Атом,Имя).
выдать_номер(Корень, Номер):-retract(тeк_номер(Корень, Номер1)),!,Номер is Номер 1 + 1, asserta(тек_номер(Корень, Номер)).
выдать_номер(Корень,1):- asserta(тек_номep(Kopeнь,l)).
/* Преобразовать целое в список цифр */
целое_имя(Цел,Итогспи):- целое_имя (Цел, [], Итогспи).
целое_имя(I,Текспи,[С|Текспи]:- I ‹10,!, С is I+48.
целое_имя(I,Текспи,Итогспи):-Частное is I/10, Остаток is I mod 10,С is Остаток+48.
целое_имя(Частное,[С|Текспи],Итогспи).
В некоторых прикладных задачах полезно уметь определять все термы, которые делают истинным заданный предикат. Например, мы могли бы захотеть построить список всех детей Адама и Евы с помощью предиката родителииз гл. 1(и располагая базой данных с фактами родителио родительских отношениях). Для этого мы могли бы использовать предикат по имени найтивсе, который мы определим ниже. Цель найтивсе(Х,G, L)строит список L, состоящий из всех объектов Xтаких, что они позволяют доказать согласованность цели G. При этом предполагается, что переменная Gконкретизирована произвольным термом, однако таким, что найтивсерассматривает его как целевое утверждение Пролога. Кроме того переменная Xдолжна появиться где-то внутри G. Таким образом Gможет быть конкретизирована целевым утверждением Пролога произвольной сложности. Для того, чтобы найти всех детей Адама и Евы, необходимо было бы задать следующий вопрос:
?- найтивсе(Х, родители(Х,ева,адам), L).
Переменная Lбыла бы конкретизирована списком всех X, для которых предикату родители(Х,ева,адам)можно найти сопоставление в базе данных. Задача найтивсезаключается в том, чтобы повторять попытки согласовать его второй аргумент, и каждый раз, когда это удается, программа должна брать значение X и помещать его в базу данных. Когда попытка согласовать второй аргумент завершится неудачно, собираются все значения X, занесенные в базу данных. Получившийся при этом список возвращается как третий аргумент. Если попытка доказать согласованность второго аргумента ни разуне удастся, то третий аргумент будет конкретизирован пустым списком. При помещении элементов данных в базу данных используется встроенный предикат asserta,который вставляет термы перед теми, которые имеют тот же самый функтор. Чтобы поместить элемент Xв базу данных, мы задаем его в качестве компоненты структуры по имени найдено.Программа для найтивсевыглядит следующим образом:
найтивce(X,G,_):-asserta(найденo(мapкep)), call(G), asserta(найденo(X)),fail.
найтивсе(_,_,L):- собрать_найденное([],М),!, L=M.
собрать_найденное(S,L):- взятьеще(Х),!,собрать_найденное([Х |S],L).
собрать_найденное(L,L).
взятьеще(Х):- retract(найдено(Х)),!, Х\==маркер.
Предикат найтивсе,начинает свою работу с занесения специального маркера, который представляет из себя структуру с функтором найденои с компонентой маркер.Этот специальный маркер отмечает место в базе данных, перед которым будут занесены (с помощью asserta)все X,согласующие Gс базой данных при данном запуске найтивсе.Затем делается попытка согласовать Gи каждый раз, когда это удается, Xзаносится в базу данных в качестве компоненты функтора найдено.Предикат failинициирует процесс возврата и попытку повторно согласовать G (assertaсогласуется не более одного раза). Когда попытка согласовать Gзавершается неудачей, процесс возврата приводит к неудаче первого утверждения из определения найтивсе,и делается попытка согласовать в качестве цели второе утверждение. Второе утверждение вызывает собрать_найденноедля выборки из базы данных всех структур найдено и включения их компонент в список. Предикат собрать_найденноевставляет каждый элемент в переменную, где хранится список «уже собранных» элементов. Этот прием мы рассматривали выше при разборе программы ге-натом. Как только встречается компонента маркер, взятьещезавершается неудачей, после чего выбирается второе утверждение для собрать_найденное.При сопоставлении егос текущей целью второй аргумент (результат) сцепляется с первым аргументом (с набранным списком)
Заметим, что присутствие в базе данных структуры найдено (маркер)указывает на некоторое конкретное употребление найтивсе. Это означает, что найтивсеможет вызываться рекурсивно – любое использование найтивсево втором аргументе другого найтивсебудет обработано правильно.
В разд. 7.9 мы разработаем программу, которая использует предикат найтивседля построения списка всех потомков узла в графе. Этот список необходим для реализации программы поиска по графу вширь.
Упражнение 7.7.Напишите Пролог-программу случайный_выбортакую, что цель случайный_выбор(L, Е)конкретизирует Е случайно выбранным элементом списка L. Подсказка: используйте генератор случайных чисел и определите предикат, который возвращает N-й элемент списка.
Упражнение 7.8.Задана цель найтивсе(Х,G, L). Что произойдет, если в Gимеются неконкретизированные переменные не сцепленные с X?
7.9. Поиск по графу
Граф – это сеть, состоящая из узлов, соединенных дугами. Например, географическую карту можно рассматривать как граф, где узлами являются населенные пункты, а дугами, соединяющие их дороги. Если вы хотите найти кратчайший маршрут между двумя населенными пунктами, вам предстоит решить задачу нахождения кратчайшего пути между двумя узлами графа.