У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ Страница 44

Последние несколько утверждений этой программы определяют предикат целое_имя, который используется для преобразования целого числа в последовательность литер-цифр. Атомы, порождаемые генатом, формируются с помощью встроенного предиката 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. Поиск по графу

Граф – это сеть, состоящая из узлов, соединенных дугами. Например, географическую карту можно рассматривать как граф, где узлами являются населенные пункты, а дугами, соединяющие их дороги. Если вы хотите найти кратчайший маршрут между двумя населенными пунктами, вам предстоит решить задачу нахождения кратчайшего пути между двумя узлами графа.

Проще всего описать граф в базе данных с помощью фактов, представляющих дуги между узлами графа. На рис, 7.3 приведен пример графа и его представления с помощью фактов. Чтобы пройти от узла g к узлу а, мы можем пойти по пути g, d, e, а или по одному из многих других возможных путей. Если мы представляем ориентированный граф, то предикат а следует понимать так, что а(Х, Y) означает, что существует дуга из X в Y, но из этого не следует существование дуги из Y в X. В данном разделе мы будем иметь дело только с неориентированными графами, у которых все дуги двунаправленные. Это допущение совпадает с тем, которое мы делаем в разд. 7.2 при поиске в лабиринте.