Точно Не проект 2 / Не books / Источник_1
.pdfЯзык Пролог |
361 |
|
|
что подзадача “a” разрешима, если решены подзадачи “c” и “d”. Терминальные вершины будем задавать с помощью фактов:
цель(t1). цель(t2). цель(t3).
Рассмотрим программирование процедуры поиска в глубину. При этом воспользуемся следующими фактами:
а) если рассматриваемая вершина является терминальной, то решение соответствующей подзадачи известно;
б) если рассматриваемая вершина – это вершина ИЛИ типа, то необходимо решить одну из подзадач;
в) если рассматриваемая вершина – это вершина И типа, то необходимо решить все подзадачи.
Определим предикат ао_поиск(Верш, РешДер), который аналогичен процедуре Depth_first-AO2, рассмотренной в § 2.3.1. Воспользуемся встроенным механизмом поиска решений пролог-системы. Дерево вывода, формируемое пролог-системой, является И/ИЛИ деревом. Оно строится методом поиска в глубину. Если какая-либо из подзадач не решена, то прологсистема автоматически возвращается к имеющейся альтернативной подзадаче и продолжает ее решение. Это существенно упрощает программирование предиката ао_поиск(Верш, РешДер), где переменная Верш соответствует вершине И/ИЛИ дерева, а переменная РешДер – поддереву решения, расположенному ниже этой вершины. Дерево решений будем представлять следующим образом [7]:
а) если Верш – терминальная вершина, то дерево решений тривиально (оно представляется вершиной Верш);
б) если Верш – это вершина ИЛИ типа, то дерево решений будет иметь вид Верш ---> Поддерево, где переменная Поддерево будет представлять одно из возможных поддеревьев решений для задачи, заданной переменной Верш;
в) если Верш – это вершина И типа, то дерево решений будет иметь вид Верш---> и: Поддеревья, где Поддеревья – список поддеревьев решений И-подзадач.
Тогда программа поиска в глубину запишется так [7]:
ао_поиск(Верш, Верш): – |
% правило а) |
цель(Верш). |
|
ао_поиск(Верш, Верш---> Дер): – |
% правило б) |
Верш---> или : Вершины, элемент(Верш1, Вершины), ао_поиск(Верш1, Дер).
ао_поиск(Верш, Верш---> и: Деревья): – % правило в)
Язык Пролог |
363 |
|
|
который можно рассматривать как вектор признаков. В этом случае операция обобщения будет выполняться простой заменой константы на переменную. Так, вектор признаков
[средний, красный, Х]
представляет все объекты среднего размера и красного цвета. Этот вектор признаков будет охватывающим для вектора [средний, красный, круг].
Определим отношение охватывает(P,Q), устанавливающее идентичность векторов признаков P и Q или выясняющее, охватывает ли вектор признаков Р вектор Q [77]:
охватывает([ ], [ ]). |
% пустые векторы идентичны |
охватывает([H1|T1], [H2|T2]): – % переменные Н1 и Н2 var(H1), var(H2), %охватывают друг друга охватывает(Т1, Т2).
охватывает([H1|T1], [H2|T2]): – %переменная охватывает var(H1), atom(H2), % константу охватывает(Т1,Т2).
охватывает([H1|T1], [H2|T2]): – % отношение имеет место, atom(H1), atom(H2), H1=H2, %если константы сопоставимы охватывает(T1, T2).
Алгоритм Митчелла требует выяснения, будет ли некоторое понятие строго более общим, чем другое. Это можно сделать с помощью правила:
более_общее(X, Y): – not охватывает(Y, X), охватывает(X, Y).
В ходе поиска необходимо выполнять операции обобщения и специализации. Определим для этого соответствующие предикаты. Предикат обобщения
обобщить(Гипотеза, Пример, Обобщение),
выполняющий поиск значения переменной Обобщение, которое минимально обобщает понятие-кандидат, представляемое аргументом Гипотеза, и охватывает понятие, заданное аргументом Пример. С этой целью рекурсивно сопоставляются элементы векторов признаков Гипотеза и Пример. Если соответствующие элементы двух векторов признаков сопоставимы, то в результирующий вектор Обобщение помещается элемент вектора Гипотеза. Если соответствующие элементы векторов не сопоставимы, то в соответствующую позицию вектора Обобщение помещается анонимная переменная [77]:
Язык Пролог |
367 |
|
|
исключ_понятий_кандидатов([G], [S], _ ): – охватывает(G, S), охватывает(S, G), write('искомое понятие – '), write(G), nl.
исключ_понятий_кандидатов(G, S, Подстановки): – write('G='), write(G), nl, write('S='), write(S), nl, write('Введите пример:'), read(Пример), v_поиск(Пример, G, S, Нов_G, Нов_S, Подстановки),
иключ_понятий_кандидатов(Нов_G,Нов_S,Подстановки).
Проиллюстрируем работу программы с помощью следующего вызова
? – исключ_понятий_кандидатов([[ _, _, _]], [ ], [[маленький, средний, большой], [желтый, зеленый, красный],.
[круг, квадрат, треугольник]]).
G=[[ _0048, _0050, _0058]] S=[ ]
Введите пример: положит([средний, круг, красный]). G=[[ _0048, _0050, _0058]]
S=[[средний, круг, красный]
Введите пример: отрицат([средний, квадрат, зеленый]). G=[[ _07С0, круг, _07D0], [ _ 0748, 0750, красный]] S=[[средний, круг, красный]
Введите пример: положит([большой, круг, красный]). G=[[ _07С0, круг, _07D0], [ _ 0748, 0750, красный]] S=[[ _13F8, круг, красный]]
Введите пример: отрицат([средний, треугольник, красный]). G=[[ _07С0, круг, _07D0]]
S=[[ _13F8, круг, красный]]
Введите пример: отрицат([средний, круг, зеленый]). Искомое понятие – [ _231C, круг, красный]
Yes.
Здесь числовые кодовые комбинации, начинающиеся с символа подчеркивания, – переменные. Поэтому сформированный программой вектор признаков [ _231C, круг, красный] соответствует понятию “красный круг”.
6.11.5. Поиск в сети фреймов
Рассмотрим сеть иерархически упорядоченных фреймов, представляющих графические объекты (рисунок 6.12).
Фрейм на языке Пролог можно представить совокупностью предикатов
фрейм(Имя-фрейма,Имя-слота,Фацет,Значение), каждый из которых опре-
деляет значение соответствующего фацета (аспект) слота. Например, корневой графический объект можно описать предикатом
Язык Пролог |
369 |
|
|
В этом случае процедуры-демоны должны представляться в виде предикатов:
имя_процедуры_демона(Фрейм, Слот, Значение):- . . .
Например:
площадь-прямоугольника(Фрейм. Слот, Значение):- определить-значение(Фрейм, сторона-х, Х), определить-значение(Фрейм, сторона-y, Y), Значение is X * Y, !.
Вопросы для самопроверки
1.Приведите примеры следующих основных понятий языка Пролог: константа, переменная, список, факт, правило, терм.
2.Сформулируйте правила сопоставления термов, используемые в Прологе.
3.Объясните на примере декларативный и процедурный смысл прологпрограммы.
4.Постройте дерево вывода для целевого утверждения member(c,[a, d, c]).
5.Как в пролог-программе объявить оператор? Как специфицируются типы операторов?
6.Объясните на примере порядок вычисления арифметического выражения, представив его в виде древовидной структуры.
7.Каким образом выполняется оператор is?
8.Какие формы записи списков используются в Прологе?
9.Приведите общую схему предиката, выполняющего обработку каждого элемента списка.
10.Определите на языке Пролог предикаты удалить и реверс, обрабатывающие списки рекурсивно.
11.Объясните на примере назначение предиката отсечения.
12.Что в языке Пролог называют группой?
13.Как в Прологе реализуется отрицание? Приведите примеры.
14.Что называют метапеременными (метаусловиями)?
15.Определите с помощью метапеременных конструкцию “если-то-иначе”. Приведите пример её использования.
16.Как в Прологе организовать итерационный цикл? Определите предикат все_решения(Условие,X), обеспечивающий поиск всех значений X, при которых выполняется метаусловие Условие(X).
17.Перечислите и объясните процедурный смысл встроенных предикатов, осуществляющих ввод-вывод.
18.Определите на Прологе предикат, осуществляющий ввод арифметического выражения с клавиатуры (из файла) и вывод его значения на экран (в файл).
19.Объясните следующие встроенные предикаты: var, nonvar, atom, atomic, integer.
20.Объясните предикаты: name(A,L), functor(T,F,A), arg(N,T,A), T=..L.
21.Объясните предикаты: assert(X), asserz(X), retract(X), consult(F), save(F), restore(F).