Применения множественных выражений

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

В разд. 14.2 были рассмотрены три программы 14.8, 14.9 и 14.10 для обхода графа в глубину. Здесь обсуждаются эквивалентные программы для обхода графа в ширину.

connected (X,Y) ¬

Связь вершины X с вершиной Y в ориентированном ациклическом графе определяется предложением edge/2.

connected(X,Y) ¬ connected_bfs([X | Xs])\Xs,Y).

connected_bfs([ ] \ [ ], Y) ¬!, fail.

connected_bfs([X | Xs]\Ys, X).

connected_bfs([X | Xs] \ Ys, Y) ¬

find_all_dI(N,edge(X,N),Ys\Zs),

connected_bfs(Xs\Zs,Y).

Данные

edge(a,b). edge(a,c). edge(a,d). edge(a,e).

edge(f,i). edge(c,f). edge(c,g). edge(f.h).

edge(e.k). edge(d.j). edge(x,y). edge(y,z).

edge(z,x). edge(y.u). edge(z,v).

Программа 17.4. Программа и тестовые данные для проверки алгоритма обхода в ширину ориентированного ациклического графа.

Основным отношением является connected(X,Y), которое истинно, если вершины Х и Y связны. Это отношение определено в программе 17.4. Поиск в ширину реализуется посредством ведения такой очереди вершин, следуя которой происходит обход графа в ширину. Соответственно предложение connected вызывает отношение connected_bfs(Queue,Y), которое истинно, если Y принадлежит связному компоненту графа, представленному вершинами в очереди Queue.

При каждом обращении к предикату connectd_bfs текущая вершина извлекается из очереди, находится множество связанных с ней вершин, которые добавляются в конец очереди. Очередь представлена разностным списком. Кроме того, здесь используется множественный предикат find_all_dl. Если очередь пуста, то выполнение программы завершается отказом. Поскольку разностные списки являются неполными структурами данных, необходимо предусмотреть явную проверку пустоты очереди. В противном случае выполнение программы может не завершаться,

Рассмотрим факты edge в программе 17.4, представляющие граф, показанный на рис. 14.3 слева. Для них вопрос connected(a.X) дает решения b, с, d, e, f, g, j, k, h, i как результат обхода графа в ширину.

Программа 17.4, подобно программе 14.8, пригодна для обхода конечного дерева или ориентированного ациклического графа. В случае циклического графа выполнение программы не завершится.

connected(X. Y) ¬

Связь вершины Х с вершиной У в графе определяется предложением edge/ 2.

connected(X,Y) ¬ connected(X | Xs]\Xs, Y,[X]).

connected ([ ]\[ ], Y, Visited) ¬!, fail.

connected ([A | Xs]\Ys, A, Visited).

connected ([A | Xs]\Ys,B, Visited) ¬

set_of(N,edge(A,N),Ns),

filter([Ns, Visited, Visited],Xs\Ys,Xsl),

connected(Xsi, B, Visited1).

filter([N [ Ns], Visited, Visited l,Xs,Xsl)¬

rnember(N, Visited),

filter(Ns, Visited, Visitedl, Xs, Xs1).

filter([N|Ns],Visited,Xs\[N|Ys],Xs\Ys) ¬

not rnembcr(N,Visited),

filter(Ns,[N | Visited], Visitedl,Xs\Ys,Xsl).

filter([ ],V,V,Xs, Xs).

Программа 17.5. Проверка связности графа путем обхода в ширину.

По сравнению с программой 17.4 программа 17.5 более совершенна, в ней, в частности, ведется список просмотренных вершин графа. В конец очереди добавляются не все дочерние вершины, а только те, которые еще не просматривались, Такая проверка в программе 17.5 выполняется с помощью предиката filter.

На самом деле программа 17.5 является более мощной, чем ее эквивалент с обходом в глубину – программа 14.10. Она не только осуществляет корректный обход любого конечного графа, но с тем же успехом может использоваться и для обхода бесконечных графов. Полезно заметить, что расширения чистого Пролога необходимы для увеличения эффективности поиска на графах. Используя чистый Пролог, можно писать корректные программы поиска на конечных деревьях и ориентированных ациклических графах. Добавление отрицания позволяет реализовать корректный поиск на конечных графах с циклами, а множественные выражения необходимы для работы с бесконечными графами. На рис. 17.2 эти соображения представлены в сжатом виде.

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

(1) Конечные деревья и ориентированные ациклические графы. Чистый Пролог.

(2) Конечные графы.

Чистый Пролог + отрицание.

(3) Бесконечные графы.

Чистый Пролог + множественные выражения + отрицание.

Рис. 17.2. Средства Пролога для решения различных задач поиска на графах.

В последнем примере этого раздела решается задача поиска ключевых слов в контексте. И вновь объединение недетерминированного программирования с программированием второго порядка позволяет с помощью простой Пролог-программы решить сложную задачу.

Нахождение ключевых слов в контексте связано с поиском всех вхождений множества ключевых слов в определенный текст и выделением контекстов, в которых они встречаются. Здесь будет рассмотрен следующий вариант этой общей задачи: «Для данного списка заголовков сформировать упорядоченный список всех вхождений в данные заголовки множества ключевых слов вместе с их контекстами».

Пример входных и ожидаемых выходных данных для такой программы представлен на рис. 17.4. Контекст описывается как вращение заголовка, конец которого отмечен вертикальной чертой «|». В рассматриваемом примере использован следующий набор «нетривиальных» ключевых слов: algorithmic, debugging, logic, problem, program, programming, prolog и solving.

В данной задаче подлежит вычислению отношение kwic(Titles,KwicTit1es), где Tub's- список заголовков, из которых должны быть выделены ключевые слова, а КwicTitles – отсортированный список ключевых слов в их контекстах. Предполагается, что входной и выходной тексты представлены в виде списков слов. В более общей программе должны быть предусмотрены предварительный шаг преобразования входного текста в свободной форме в списки слов, а также выдача результатов в удобном для чтения виде.

Вход: programming in prolog logic for problem solving logic programming algorithmic program debugging

Выход: algorithmic program debugging |, debugging | algorithmic program, logic for problem solving |, logic programming, |, problem solving | logic for, program debugging | algorithmic, programming in prolog |. programming | logic, prolog | programming in, solving | logic for problem

Рис17.4. Вход и выход для задачи поиска вхождений ключевых слов в контексте.

Рассмотрим поэтапное представление программы. Основа программы – недетерминированное описание вращения списка слов. С помощью предиката append ему можно дать следующее элегантное определение:

rotate(Xs,Ys) ¬ append(As,Bs,Xs). append! Bs,As.Ys).

Декларативно: Ys – вращение Xs, если Xs состоит из As, за которым следует Bs, а Ys состоит из Bs, за которым следует As.

Следующий этап связан с идентификацией отдельных слов как потенциальных ключевых слов. Это выполняется посредством выбора слова в первом вызове предиката append. Отметим, что следующее новое правило является примером предыдущего правила rotate:

rotate(Xs,Ys) ¬ append(As.[Key | Bs],Xs), append([Key | Bs].As,Ys).

Кроме того, это определение лучше предыдущего, поскольку в нем предусмотрено удаление одинаковых решений, когда один из расщепленных списков пуст, а другой – полон.

Следующее улучшение связано с более детальной проверкой потенциального ключевого слова. Предположим, что каждое ключевое слово Word определяется фактом вида keyword(Word). Решения в процессе rotate могут быть отфильтрованы так, чтобы воспринимались только те слова, которые идентифицированы как ключевые. Соответствующая версия рассматриваемого предложения имеет вид

rotate_and_filter(Xs,Ys) ¬

append(As,[Key | Bs],Xs), keyword(Key), append([Key | Bs],As,Ys).

Операционное поведение данной процедуры: она рассматривает все ключевые слова, отфильтровывая нежелательные альтернативы. Для максимизации эффективности программы в данном случае важен порядок целей.

В программе 17.7, окончательной версии интересующей нас программы, предусмотрены дополнительные средства для распознавания ключевых слов. Любое слово Word считается ключевым, если оно не специфицировано с помощью факта вида insignificant(Word) как незначащее. Кроме того, в процедуре выполняется вставка в конец заголовка маркера «|», отмечающего контекстную информацию. Это реализуется добавлением дополнительного символа во втором обращении к предикату append. Соответствующее предложение rotate_and_filter содержится в программе 17.7.

Наконец, для получения всех решений использован множественный предикат. Квантификация необходима повсем возможным заголовкам. Явным преимуществом использования предиката set_of является сортировка ответов. Полная программа для решения рассматриваемой задачи (программа 17.7) элегантный пример выразительной мощности Пролога. Для тестирования в программе использован предикат test_kwic/2.

kwic(Tites, КWTitles) ¬

КWTities – KWIC-индекс списка заголовков Titles.

kwic(Titles.KWTilles)¬

set_of(Ys,Xs ­ (member(Xs, Titles),

rotate_and_fiIter(Xs,Ys)),KWTitles).

rotate_and_filter (Xs, Ys) ¬

Ys – вращение списка Xs, такое, что первое слово Ys значимо, и знак '|' вставлен после последнего слова Xs.

rotate_and_filter(Xs,Ys) ¬

append (As, [Key | Bs],Xs),

not insignificant(Key),

append([Key,’|’ | Bs],As,Ys).

Словарь незначимых слов

insignificant(a). insignificant(the).

insignificant(in). insignificant (for).

Предложения и данные для тестирования

test_kwic(Books,Kwic) ¬

titles(Books,Titles),kwic(Titles,Kwic).

titles(lp, [[logic, for, problem,solving],

[logic, programming],

[algorithmic, program, debugging],

[programming, in, prolog]]).

Программа 17.7. Создание индекса в задаче поиска ключевых слов вместе с их контекстами.

Дата добавления: 2014-01-07