Программирование на языке Пролог для искусственного интеллекта - Иван Братко

3.16. Определите отношение

mах( X, Y, Мах)

так, чтобы Мах равнялось наибольшому из двух чисел X и Y.

3.17. Определите предикат

максспис( Список, Мах)

так, чтобы Мах равнялось наибольшему из чисел, входящих в Список.

3.18. Определите предикат

сумспис( Список, Сумма)

так, чтобы Сумма равнялось сумме чисел, входящих в Список.

3.19. Определите предикат

упорядоченный( Список)

который принимает значение истина, если Список представляет собой упорядоченный список чисел. Например: упорядоченный [1, 5, 6, 6, 9, 12] ).

3.20. Определите предикат

подсумма( Множ, Сумма, ПодМнож)

где Множ это список чисел, Подмнож подмножество этих чисел, а сумма чисел из ПодМнож равна Сумма. Например:

?- подсумма( [1, 2, 5, 3, 2], 5, ПМ).

ПМ = [1, 2, 2];

ПМ = [2, 3];

ПМ = [5];

...

3.21. Определите процедуру

между( N1, N2, X)

которая, с помощью перебора, порождает все целые числа X, отвечающие условию N1≤X≤N2.

3.22.    Определите операторы 'если', 'то', 'иначе' и ':=" таким образом, чтобы следующее выражение стало правильным термом:

если X > Y то Z := X иначе Z := Y

Выберите приоритеты так, чтобы  'если' стал главным функтором. Затем определите отношение 'если' так, чтобы оно стало как бы маленьким интерпретатором выражений типа 'если-то-иначе'. Например, такого

если Вел1 > Вел2 то Перем := Вел3

иначе Перем := Вел4

где Вел1, Вел2, Вел3 и Вел4 — числовые величины (или переменные, конкретизированные числами), а Перем — переменная. Смысл отношения 'если' таков: если значение Вел1 больше значения Вел2, тогда Перем конкретизируется значением Вел3, в противном случае — значением Вел4. Приведем пример использования такого интерпретатора:

?- X = 2, Y = 3,

 Вел2 is 2*X,

 Вел4 is 4*X,

 Если Y > Вел2 то Z := Y иначе Z := Вел4.

 Если Z > 5 то W := 1 иначе W :=0.

X = 2

Y = 3

Z = 8

W = 1

Вел2 = 4

Вел4 = 8

Резюме

• Список — часто используемая структура. Он либо пуст, либо состоит из головы и хвоста, который в свою очередь также является списком. Для списков в Прологе имеется специальная нотация.

• В данной главе рассмотрены следующие операции над списками: принадлежность к списку, конкатенация, добавление элемента, удаление элемента, удаление подсписка.

• Операторная запись позволяет программисту приспособить синтаксис программ к своим конкретным нуждам. С помощью операторов можно значительно повысить наглядность программ.

• Новые операторы определяются с помощью директивы op, в которой указываются его имя, тип и приоритет.

• Как правило, с оператором не связывается никакой операции; оператор это просто синтаксическое удобство, обеспечивающее альтернативный способ записи термов.

• Арифметические операции выполняются с помощью встроенных процедур. Вычисление арифметических выражений запускается процедурой is, а также предикатами сравнения <, =< и т.д.

• Понятия, введенные в данной главе:

 список, голова списка, хвост списка

 списковая нотация

 операторы, операторная нотация

 инфиксные, префиксные и постфиксные операторы

 приоритет операторов

 арифметические встроенные процедуры 

Глава 4

Использование структур: примеры

Структуры данных вместе с сопоставлением, автоматическими возвратами и арифметикой представляют собой мощный инструмент программирования. В этой главе мы расширим навыки использования этого инструмента при помощи следующих учебных программных примеров: получение структурированной информации из базы данных, моделирование недетерминированного автомата, планирование маршрута поездки и решение задачи о расстановке восьми ферзей на шахматной доске. Мы увидим также, как в Прологе реализуется принцип абстракции данных.

4.1. Получение структурированной информации из базы данных

Это упражнение развивает навыки представления структурных объектов данных и управления ими. Оно показывает также, что Пролог является естественным языком запросов к базе данных.

База данных может быть представлена на Прологе в виде множества фактов. Например, в базе данных о семьях каждая семья может описываться одним предложением. На рис. 4.1 показано, как информацию о каждой семье можно представить в виде структуры. Каждая семья состоит из трех компонент: мужа, жены и детей. Поскольку количество детей в разных семьях может быть разным, то их целесообразно представить в виде списка, состоящего из произвольного числа элементов. Каждого члена семьи в свою очередь можно представить структурой, состоящей из четырех компонент: имени, фамилии, даты рождения и работы. Информация о работе — это либо "не работает", либо указание места работа и оклада (дохода). Информацию о семье, изображенной на рис. 4.1, можно занести в базу данных с помощью предложения:

семья( членсемьи( том, фокс, дата( 7, май, 1950),

 работает( bbс, 15200) ),

 членсемьи( энн, фокс, дата( 9, май, 1951), неработает),

 [членсемьи( пат, фокс, дата( 5, май, 1973), неработает),

 членсемьи( джим, фокс, дата( 5, май, 1973), неработает) ] ).

Рис. 4.1. Структурированная информация о семье.

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

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

семья( членсемьи( _, армстронг, _, _ ), _, _ )

Символы подчеркивания обозначают различные анонимные переменные, значения которых нас не заботят. Далее можно сослаться на все семьи с тремя детьми при помощи терма:

семья( _, _, [ _, _, _ ])

Чтобы найти всех замужних женщин, имеющих по крайней мере троих детей, можно задать вопрос:

 ?-  семья( _, членсемьи( Имя, Фамилия, _, _ ), [ _, _, _ | _ ]).

Главным моментом в этих примерах является то, что указывать интересующие нас объекты можно не только по их содержимому, но и по их структуре. Мы задаем одну структуру и оставляем ее аргументы в виде слотов (пропусков).

Рис. 4.2. Описания объектов по их структурным свойствам: (а) любая семья Армстронгов; (b) любая семья, имеющая ровно трех детей; (с) любая семья, имеющая по крайней мере три ребенка. Структура (с) дает возможность получить имя и фамилию жены конкретизацией переменных Имя и Фамилия.

Можно создать набор процедур, который служил бы утилитой, делающей взаимодействие с нашей базой данных более удобным. Такие процедуры являлись бы частью пользовательского интерфейса. Вот некоторые полезные процедуры для нашей базы данных:

муж( X) :-     % X - муж

 семья( X, _, _ ).

жена( X) :-    % X - жена

 семья( _, X, _ ).

ребенок( X) :- % X - ребенок

 семья( _, _, Дети),

 принадлежит( X, Дети).

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

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

 принадлежит( X, L).

существует( Членсемьи) :-

 % Любой член семьи в базе данных

 муж( Членсемьи);

 жена( Членсемьи);

 ребенок( Членсемьи).

дата рождения( Членсемьи( _, _, Дата, _ ), Дата).

доход( Членсемьи( _, _, _, работает( _, S) ), S).

 % Доход работающего

доход( Членсемьи( _, _, _, неработает), 0).

 % Доход неработающего

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

• Найти имена всех людей из базы данных:

  ?-  существует( членсемьи( Имя,Фамилия, _, _ )).

• Найти всех детей, родившихся в 1981 году:

  ?-  ребенок( X), датарождения( X, дата( _, _, 1981) ).