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