23653

Логическое программирование задачи поиска пути на конечных графах пространства состояний

Лабораторная работа

Информатика, кибернетика и программирование

Рассмотрим ориентированный ациклический граф: Наличие ориентированной связи двух соседних вершин отображается в программе в виде фактовпредикатов edgex y. edgeac. edgecf. edgefh.

Русский

2013-08-05

680 KB

6 чел.

Аннотация

Оценка достижимости какой-либо цели при экспертном выборе решения часто сводится к поиску последовательности допустимых трансформаций состояния задачи. С математической точки зрения это задачи поиска пути на графе пространства состояний, если эти состояния логически связаны между собой. Они образуют вершины связного графа, в котором необходимо найти путь от исходной вершины до целевой, или от целевой до исходной. Если состояния задачи логически не связаны между собой, и, следовательно, не образуют логической сети, то трансформация состояний осуществляется с помощью не связанных между собой эвристических правил  по модели продукционной системы. Пролог реализует первую, детерминированную, логически “жесткую” модель. Вторая недетерминированная модель, основанная на эвристических правилах, может быть реализована на объектно-продукционном языке CLIPS. Но на нем можно программно реализовать и поиск пути на графе. Пример такой задачи для сравнения с Прологом включен в работу №1.

С помощью специальных приемов на Прологе можно программировать  экспертные системы с нечеткими правилами, преобразуемыми в нечеткие факты (предикаты с числовым коэффициентом достоверности),  позволяющие делать нечеткие выводы, и за счет этого сравнивать между собой “коэффициенты достоверности” различных гипотез. Примером является ЭС IMP, которая изучается на лекциях и самостоятельно по выдаваемой программе. Она не входит в описание данного лабораторного практикума,  отчетность по ней осуществляется отдельно.

Лабораторная работа № 1

                         

«Логическое программирование задачи поиска пути на конечных графах пространства состояний»

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

прямой и обратный методы поиска в пространстве состояний;

стратегии поиска  «в глубину» и «в ширину»;

ориентированный ациклический граф (дерево);

ориентированный граф с циклами;

неориентированный граф (сеть);

поиск в бинарном дереве по числовым ключам  вершин;

поиск кратчайшего пути на графе с транзитивными рёбрами;

логическая модель поиска на продукционном языке CLIPS.

Вначале  поясним термины «прямые и обратные рассуждения», «прямой и обратный поиск в пространстве состояний».  Интерпретатор Пролога всегда реализует дедуктивный метод или метод обратных рассуждений, т.е. от цели к фактам: голова любого правила - текущая цель, тело правила - в общем случае конъюнкция условий ее достижения.  Пытаясь доказать истинность главной цели, интерпретатор рассматривает каждое из  условий, превращая их,   часто  рекурсивно, в  текущие цели или подтверждая  их истинность фактами из рабочей памяти на терминальном уровне. Доказательство истинности главной цели сводится к виртуальному построению дерева целей и обратному ходу присвоения значений переменным.

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

Пространство состояний может быть конечным, заданным изначально фактами  связи соседних вершин, или “бесконечным”, порождаемым от начальной вершины (корня дерева) в соответствии с логикой возможных  трансформаций состояний. Хорошим примером являются игровые задачи (подробнее см. л.р. №3), но такие задачи требуют, как правило,  разработки эвристик, ограничивающих пространство поиска. Целью поиска в конечном пространстве состояний является определение «видимости» (достижимости) конечной (целевой) вершины Y из начальной X, необязательно корневой. Такой поиск можно рассматривать как доказательство, что из утверждения X логически следует утверждение Y. Фактически следует подтвердить принадлежность вершины Y дереву или поддереву, начинающемуся от вершины X. Часто при этом требуется вывести  путь   из X в Y (показать ход “рассуждений”). В таких простейших задачах  не используются ограничивающие эвристики, происходит полный перебор логически возможных вариантов.

Задание 1.1. Поиск пути в ориентированном ациклическом графе (дереве).

1.1.1. Прямой поиск (от исходной вершины до целевой вершины).

Рассмотрим ориентированный ациклический граф:

Наличие ориентированной связи двух соседних вершин отображается в программе в виде фактов-предикатов edge(x, y).

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

edge(c,g).   edge(a,d).     edge(d,j).

Семантика связи edge может быть различной и зависит от предметной области (ПО). Например, факты edge можно истолковать как отношение следования: из «a» следует «c». В программе эти факты будут рассматриваться последовательно по строкам.   Порядок  расположения  фактов влияет на последовательность шагов  программы, но не на результат.

Задача поиска пути допускает следующую  логическую формулировку. Чтобы найти путь, например, из вершины “а” в i, необходимо вначале решить более простую задачу: найти одну из вершин, с которой непосредственно связана “а”,  а затем искать путь от этой вершины к цели, пользуясь тем же самым правилом.  Задача решается рекурсивно. Цель при этом редуцируется (понижается). Разворачивание рекурсии идет до тех пор, пока очередная исходная вершина не совпадет с целевой. Такое программирование, когда дана цель и правила поиска (но не алгоритм!) называется декларативным, недетерминированным (поскольку в некоторых вершинах имеются варианты выбора продолжения пути), свойственным задачам искусственного интеллекта.

path(X,X,[X]).

path(X,Y,[X|P]):-edge(X,N),path(N,Y,P).

Первая переменная (аргумент) предиката path- заданная исходная вершина, второй аргумент - целевая вершина, третий аргумент - искомый список вершин пути. Первое предложение представляет собой условие окончания рекурсии. Его декларативный смысл:  существует (истинен) путь из вершины X в неё же саму, представляющий собой список из самой вершины [X]. Второе предложение  декларирует: путь из вершины X в вершину Y   представляет собой список [X|P] (с головным элементом Х в виде текущей  вершины), если существует  ребро edge от вершины X до  соседней вершины N и  поставлена рекурсивно цель: найти путь P из вершины N в вершину Y. Обратите внимание, что Р     является хвостом искомого списка в голове правила (обозначаются одинаковым символом).    

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

Протокол работы вышеприведенной программы с целью path(a,i,Path)   

(Определение. Цель – это любой предикат, у которого хотя бы один аргумент  является переменной).

        Цель вначале сопоставляется с первым предложением вышеприведенного правила, но она ему не подходит, поскольку в этом предложении правила два первых аргумента должны быть одинаковы,  а в цели они разные.   Подставляем  переменную Path и атомы а,i из цели в голову второго предложения:

path(a, i, Path):-edge(a, N),  path(N, i, P).

Но в голове, согласно    правилу, переменная Path  должна быть  списком  [X|P], где Х=a.  Поэтому в протоколе надо   написать:

         path(a, i, [a|P] ):-edge(a, N),  path(N, i, P).               % Path заменяем на [a|P].

 В теле получаем две подцели с переменными N и P. Сопоставление первой  подцели edge(a, N) с первым подходящим фактом edge(a,c) даёт унификацию N = c. Другие подходящие факты  интерпретатор отмечет указателями для возможности поиска с возвратом. Следующий предикат порождает новую подцель path(c,i,P), переменная и  атомы из которой должны подставляться в правило. Для этой цели   подходящим опять оказывается   второе предложение:

path(c, i, [c|P1]): - edge(c, N),  path(N, i, P1).

Но здесь  P = [c|P1], и мы вынуждены ввести в качестве хвоста новую переменную P1, так как списки P и P1 находятся теперь на разных “этажах” стека и отличаются друг от друга на элемент “а”. Обращение к фактам edge даёт N = f, и второй предикат формирует новую цель:

path(f, i, [f|P2]): - edge(f, N),  path(N, i, P2).

Здесь Р1 заменяется на [f|P2] по той же причине, что и в предыдущем случае, и мы вынуждены ввести переменную P2. Из сопоставления с фактами edge находим  N = h, и новая цель будет:

path(h, i, [h|P3]): - edge(h, N), path(N, i, P3)

Но в БД отсутствует факт edge с первым аргументом h,  и цель edge, а  вместе с ней всё  предложение терпит неудачу.  Интерпретатор Пролога осуществляет  возврат по указателю к предыдущему шагу рекурсии, отменяет последнюю унификацию N = h,   и находит другой факт связи для вершины f: edge(f, i), отсюда следует, что N = i, и новая цель:

path((i,i,P2)   % Возвращаемся к переменной Р2  из предыдущего шага.

Эта цель успешно разрешается путем сопоставления с первым предложением  правила path:

          path(X,X,[X])  при унификации X = i, откуда [X] =  P2 = [i].

На этом заканчивается  прямой ход рекурсии и далее происходит присваивание в обратном порядке значений переменным P1, P и Path, находящимся в  правилах, помещенных ранее на разных “этажах” стека:

Т.к. P2 = [i], то P1 = [f|P2] = [f, i],  P = [c|P1] = [c, f, i],  Path = [a|P] = [a, c, f, i]

Цель достигнута: переменная Path получила значение списка пути [a,c,f,i]. Как видно из протокола, фактический путь поиска был [a,c,f,h,f,i] и представлял собой участок обхода дерева от корня в глубину. В ответе неуспешный ход  [h,f] опускается.

Рассмотренный пример является прямым   поиском от X к   Y, который  задаётся тем, что переменная N в предикате edge является вторым аргументом, а  в вызывающем  предикате path(N,Y,P) - первым.   Это означает, что при сворачивании рекурсии, т.е. при работе правила “справа налево”, к хвосту (а вначале это целевая вершина) будут добавляться в обратном порядке пройденные головные вершины пути. В итоге список пути окажется прямым и будет находиться в голове правила, откуда он и передается в цель path(a,i,Path) для получения ответа о значении переменной Path.

Самостоятельная часть работы

  •   Составьте протокол поиска другой целевой вершины.
  •   Поменяйте порядок расположения фактов. Убедитесь, что порядок обхода, но не результат, зависит от порядка расположения фактов в  программе.
  •   Добавьте   транзитивные рёбра, например, edge(d,i), и убедитесь, что программа отыскивает все  альтернативные пути. Объясните, как это происходит .
  •    Введите цель   в тексте программы посредством команды Goal   path(a,i,L). Как увидеть теперь результат на экране? Как вывести все альтернативные решения?

1.1.2. Обратный поиск (от целевой вершины к исходной).

Приведенная ниже программа обратного поиска rev_search на первый взгляд очень напоминает предыдущую, изменено только имя предиката:

rev_search(X,X,[X]).

rev_search(X,Y,[Y|P]):-edge(Z,Y), rev_search(X,Z,P).

 

Отличие заключается, во-первых, в порядке расположения аргументов предиката edge. Здесь свободная переменная Z является 1-м аргументом, т.к. отыскивается родительская вершина для текущей  вершины Y. Поэтому программа будет отыскивать по фактам edge вершину Z, являющуюся прямым предшественником  данной  вершины Y (а не потомком вершины Х, как было ранее).

Во-вторых, изменён порядок аргументов в вызывающем предикате rev_search(X,Z,P): на первом месте - заданная начальная вершина X (так как  ищем путь к ней от Y). Второй аргумент - найденная с помощью факта edge очередная родительская вершина Z искомого обратного пути.

В-третьих, в головном предикате rev_search (X,Y,[Y|P]) в список добавляется вершина Y, а не X, как было в прямом поиске.

Рассмотрим протокол поиска, задав на том же графе (см. п.1.1.1.) аналогичную цель поиска rev_search(a,i,L). Первое предложение не подходит, потому что ai.

По второму предложению правила rev_search, подставляя в него каждый раз значения  переменных и констант из очередной цели, а вместо переменной Z - её значение из фактов  edge, имеем:

rev_search(a, i, [i|P]): - edge(f, i),  rev_search(a, f, P).

rev_search(a, f, [f|P1]): - edge(c, f),  rev_search(a, c, P1).

rev_search(a, c, [c|P2]): - edge(a, c),  rev_search(a, a, P2).

  Теперь подходит первое предложение:

rev_search(a,a,[a])., т.е. P2=[a].

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

P1 = [c|P2] = [c, a];  P = [f|P1] = [f, c, a];  L = [i|P] = [i, f, c, a].

Список пути получается  обратным. При выводе на печать   можно преобразовать его в прямой, но эту задачу  решите самостоятельно.

Преимущества обратного поиска заключаются в том, что граф не надо обходить: у каждой вершины дерева только одна родительская вершина-предшественница и, идя от цели Y, мы сразу отыскиваем кратчайший   к вершине X (если таковой существует, разумеется).

Если граф имеет транзитивные рёбра, и как минимум у одной из вершин окажется более одной предшествующей, программа   должна отыскать все альтернативные пути из Y в X.

Самостоятельная часть работы.

  •  Напишите протокол поиска пути от Y к Х.

Введите в граф  транзитивные рёбра, например, edge(d, i).

Попытайтесь повысить полезность программы lab1_1.pro, придав ей следующие дополнительные функции:

  •  определения корневой вершины графа;
  •   вывода на печать прямого списка пути.

Задание №1.2. Поиск пути в ориентированном графе с циклом.

Рассмотрим циклический граф и соответствующий список фактов:

                                                                                                      edge(x,y).

                                                                                                      edge(y,z).

                                                                                                      edge(z,x).

                                                                                                      edge(y,u).

                                                                                                      edge(z,v).

 

Если поставить цель path(x, v, Path) и применить программу из задания №1.1, то решение найдено не будет, так как возникает цикл x,y,z,x,y,z..., ведущий к переполнению стека. В данном случае решение можно получить, если факт edge(z,x) поставить в конец списка. Но такой прием не всегда очевиден, особенно при большом графе и не  единственном цикле.

Общее решение состоит во введении в предикат path четвертого аргумента Vis, представляющего собой список посещенных в процессе поиска вершин (visited). При этом в тело правила рекурсии path следует ввести проверку дополнительного условия о не членстве очередной проверяемой вершины N в этом списке c помощью правила member. Правила будут выглядеть теперь следующим образом:

way(X, Y, P): - path(X, Y, P, [X]).

path(X, X, [X],_).

path(X, Y, [X|P], Vis,]): -   edge(X, N), not(member(N, Vis)), path(N, Y, P, [N|Vis]).

member(X, [X|_]).

member(X, [_|Ys]): - member(X, Ys).

Целевым здесь является предикат way. Поставим цель: way(x, v, Path).

Первое предложение  приведенного набора правил переопределяет цель, вводя четвёртый аргумент - список посещённых вершин - и задаёт его начальное значение Vis = [X].

Второе предложение является обычным условием окончания рекурсии. Третье предложение – основное рекурсивное правило поиска. Правило member проверяет членство текущей вершины N в списке Vis. Если её нет в этом списке, member терпит неудачу, а выражение not(member(N, Vis)) принимает значение «истина». Вершина N добавляется в голову списка Vis последним предикатом path в теле основного правила, и идет рекурсивное обращение к голове того же правила в том случае, если  очередная проверяемая вершина N не совпадёт с конечной вершиной пути Y. Если такое совпадение происходит, то идет обращение к условию окончания рекурсии (предложению 2 набора правил). Аргументы этого правила принимают значения (в данном примере) path(v,v,[v],Vis), где Vis есть список всех посещенных вершин на пути из x в v. Все правило принимает значение «истина», и  прямой ход рекурсии на этом заканчивается. Далее идёт возврат рекурсии, при этом в голову списка [Х|P] на каждом “этаже” стека по очереди добавляются в обратном порядке пройденные вершины, а список Vis, наоборот, укорачивается до начальной вершины [X], в данном случае до [x]. Тело первого предложения правила в итоге принимает значение «истина», а значит, истинна и цель way(x, v, Path), где в переменной Path будет содержаться искомый путь.

Самостоятельная часть работы

  •   Составьте протокол работы правила member с какой-нибудь целью, например, member(c, [a,b,c,d]) .
  •   Введите  транзитивное ребро, убедитесь, что программа отыскивает все альтернативные варианты пути. Что происходит со списком посещенных вершин при   поиске с участием транзитивных ребер?

Задание №1.3. Поиск пути в неориентированном графе.

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

                                                                                                 edge(y,z).

                                                                                                 edge(y,x).

                                                                                                 edge(y,v).

                                                                                                 edge(z,v).

                                                                                                 edge(x,v).

                                                                                                 edge(x,u).

                                                                                                 edge(v,u).

В неориентированном (циклическом по природе) графе отношения между вершинами симметричны, т.е. если из вершины x можно попасть в v, то и из v можно попасть в x.

Расширять вдвое список фактов симметричными фактами не  самое хорошее решение.  Лучше дополнить предыдущую программу правилом con, устанавливающим симметрию отношений связанных вершин:

con(A,B):-edge(A,B).

сon(A,B):-edge(B,A).

Правило con заменит собой правило edge в предыдущей программе.

Самостоятельная часть работы

Введите третьим аргументом в факты edge веса ребер. Измените программу таким образом, чтобы она выводила суммарный вес каждого из найденных альтернативных путей. Если не справитесь самостоятельно, объясните работу программы 1_3_mod.pro.

Задание №1.4. Поиск в псевдо бинарном дереве.

Псевдо бинарное дерево не является, в отличие от настоящего бинарного дерева, рекурсивной структурой. Его можно представить в виде совокупности фактов-предикатов с тремя аргументами, например, tree(X,L,R), где X - корневая вершина дерева (поддерева), L,R - поддерживающие её левая и правая вершины, являющиеся в свою очередь корневыми вершинами для нижележащих поддеревьев. Таким образом, псевдо бинарное дерево  описано не как единая структура, а как набор фактов. Терминальные узлы отличаются тем, что L и R -пустые поддеревья. Их можно обозначить одним символом, например, v (void - пустой). Псевдо бинарное  сбалансированное дерево с 15-ю вершинами потребует для своего отображения 7 фактов для внутренних вершин, и 8 фактов для терминальных вершин. Оно не поддерживает функцию вставки или удаления вершины  дерева, как это делает  рекурсивная структура, но поддерживает поиск заданной вершины  или ускоренный поиск в случае индексации вершин (задание 1.5):

                    tree(a,b,c).                tree(i,v,v).

                    tree(b,d,e).                tree(h,v,v).

                    tree(c,f,g).                 tree(p,v,v).

                    tree(d,i,h).                 tree(n,v,v).

                    tree(e,p,n).                tree(m,v,v).

                    tree(f,m,k).                tree(k,v,v).

                    tree(g,l,s).                  tree(l,v,v).

                                                                  tree(s,v,v).

Простейшей задачей является прямой поиск заданной вершины (Y) в дереве, начинающемся в вершине X (необязательно корневой). Рекурсивное правило поиска состоит из трёх предложений:

treemember(X, X):- tree(X,_,_).

treemember(X, Y):- tree(X, L,_),  treemember(L, Y).

treemember(X, Y):- tree(X,_,R),  treemember(R, Y).

        Первое предложение - условие завершения рекурсии (вершина X тождественно принадлежит дереву, начинающемуся от X). Второе и третье - рекурсивный поиск Y соответственно в левом и правом поддеревьях. Целевой предикат, например, treemember(a,i) приведёт к ответу «Да», если путь есть. Тот же предикат с аргументами (b,f) приведёт к ответу «Нет».   Изобразите дерево, воспользовавшись приведенным списком фактов, и на примере написания протокола убедиться, что данное правило реализует метод прямого поиска   и приводит к обходу части дерева в глубину. Поиск в бинарном дереве с помощью приведенных фактов и правил не дает преимуществ, в сравнении с представлением дерева фактами edge и правилом path из Задания 1.1. Преимущество можно получить, если немного изменить правило. Идея состоит в том, чтобы при каждом вызове второго предложения, которое будет реализовать обход дерева в глубину   по левой ветви, проверять, не является ли соответствующая ей правая вершина целевой. Таким образом, это некоторая комбинация поиска в глубину и в ширину.

Самостоятельная часть работы

Изобразите бинарное дерево по приведенным фактам tree.

Дополните  программу lab1_4м.pro операторами write, чтобы проследить весь путь обхода графа при поиске заданной вершины; сокращается ли обход по сравнению с представлением дерева бинарными фактами?

Дополните программу для возможности вывода пути из Y в X (методом обратного поиска по аналогии с  первым заданием).

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

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

Задание №1.5. Ускоренный поиск в псевдо бинарном дереве  с индексацией вершин.

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

                                                                          m(9)

Представим себе числовую ось с №№ с 1 по 15. Выберем примерную середину оси (8) и присвоим это значение корневой вершине (а). Тогда в левом поддереве номера вершин  должны быть меньше 8, а в правом - больше. С каждым полученным интервалом (1-8) и (8-15) поступим аналогично, т.е. найдём примерные их середины (пусть это будут 4 и 12) и присвоим эти  индексы   вершинам   «b» и «c» соответственно. Теперь на числовой оси стало 4 интервала. Найдём их примерные середины. Пусть это будут 2, 6, 10 и 14, и присвоим эти  индексы соответственно вершинам d, e, f и g третьего уровня графа. Остальные  индексы расставим у терминальных вершин соблюдая условие: индекс левого поддерева меньше, а правого – больше, чем индекс их корня. В итоге  получим модель   индексированного бинарного дерева (в среде Visual Prolog такие деревья строятся автоматически и называются  В+ деревьями).

Полученное дерево с  индексами вершин можно представить  в виде совокупности фактов-предикатов tree(X, K, L, R) по аналогии с предыдущим заданием, где X-данная корневая вершина, K - её  индекс, L, R- поддерживающие вершины слева и справа. Для терминальных вершин, как и в предыдущей программе, L и R-пустые поддеревья, обозначаемые как v.

Целевой предикат - wtreemember(K, X, Y), где K -  индекс (ключ) искомой вершины, X-корневая вершина  дерева, в котором ведётся поиск, Y- искомая вершина. Ниже приведено правило поиска заданной вершины Y с использованием индексов, а также простейшего вывода вершин на пути от X к Y (с помощью оператора write).

wtreemember(K, X, X): - tree(X, K,_,_),  write(X, «;»), nl.

wtreemember(K, X, Y):-tree(X, FK, L,_), K < FK, write(X, «,»),  wtreemember(K, L, Y).

wtreemember(K, X, Y):-tree(X, FK,_,R), K > FK, write(X, «,»),  wtreemember(K, R, Y).

Первое предложение  - условие окончания рекурсии, означающее, что мы спустились вниз по дереву до вершины, ключ которой FK совпал с заданным значением К в цели. Тогда эта вершина  Х   передается в третий аргумент wteemember как найденная целевая. 2-е и 3-е предложения - рекурсивные процедуры поиска соответственно в левом и правом поддеревьях. Вначале всегда рассматривается правило для левого поддерева путём сравнения ключа поиска K с ключом FK текущего факта tree. Если условие выполнено, происходит рекурсивный вызов правила с вершиной левого поддерева L. Это означает, что целевая вершина находится в левом поддереве. Если условие не выполнено, т.е. K > FK, переходим к третьему предложению, которое рекурсивно вызовет правило с вершиной правого поддерева R. Это значит, что цель находится в правом поддереве. Но предикат wtreemember(K, R, Y) опять будет  обращаться ко второму предложению, т.е. пытаться осуществить поиск сначала в левом поддереве дерева с корнем  R.

Таким путем решается задача выбора  кратчайшего пути к целевой вершине, в котором находится искомый ключ. Напишите протокол поиска, задавшись, например, целью wtreemember(9,a,Y), и Вы убедитесь, что в каждой развилке программа выбирает кратчайший  путь к искомой  вершине с помощью сравнения ключа с индексом.   В нашем примере по ключу 9 найдём вершину Х = m, значение которой будет передано в цель как искомое по ключу 9 значение Y. Это один из самых быстрых методов поиска, и он является аналогом поиска в  В+ деревьях в БД на Visual Prolog.

Самостоятельная часть работы

Объясните на примере протокол  работы программы.

Задайте цель в виде запроса  tree(X,9,_,_). Запустите программу в режиме трассировки, чтобы посчитать число последовательных сопоставлений со списком фактов, которое потребовалось   программе для ответа.  

Задание 1.6. Поиск пути в ориентированном ациклическом графе

с обходом вершин  «в ширину».

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

         Рассмотрим пока без программы, как происходит процесс генерации новых путей и поиск заданной конечной вершины (см. рис.ниже).

Вначале рассматривается единственная вершина 1-го уровня - исходная. Это вершина «а». С помощью фактов edge(x,y) определяются все вершины, связанные с «a», в данном случае это «b», «c» и «d», и формируются  инверсные списки пути от этих вершин в «a»:   [b,a], [c,a], [d,a]. Все пути собираются в общий список списков:  [[b,a], [c,a], [d,a]].  Далее идет поиск целевой вершины в головном списке списков. При этом отделяется головной список   [b,a],

а в нем в свою очередь отделяется головной элемент, в данном случае «b», и сравнивается с заданной целевой вершиной:

      [[b|a]|[c,a],[d,a]]

Если совпадение произошло, то  выводится искомый путь: [b,a].  Если же совпадения не произошло, то по фактам edge определяются продолжения путей от «b» на следующий уровень графа. Это вершина «e». Она добавляется в голову неуспешного списка [b, a] и получаем новый инверсный путь от вершины «e» к «a», т.е. список  [e,b,a], который заменяет собой предыдущий [b,a], так как вершина «b» не целевая, и ставится в конец  обновленного списка списков путей, который образуется путем объединения  хвоста  1-го списка списков, т.е. [[c,a],[d,a]],  с новым путем [e,b,a], который ставится в конец. Получается новый список путей:

[[c,a],[d,a],[e,b,a]]

На первое место в этом списке вышла следующая вершина рассматриваемого уровня графа  «c». Применим то же правило, отделив головной список, а в нем головной элемент:

        

         [[c|a]|[d,a],[e,b,a]]

Допустим, головной элемент «c» опять не совпадает с заданной целевой вершиной. Тогда от «c» следует образовать продолжения путей на следующий уровень графа. По фактам edge вершина «c» связана с «f» и «g». В этом случае  порождаются два новых инверсных пути [f,c,a] и [g,c,a].  Они заменяют собой путь [c,a] и ставятся  в конец  нового списка  списков, который образуется путем объединения хвоста предыдущего списка, т.е.  [[d,a][e,b,a]],  с новыми путями [f,c,a] и [g,c,a]. Получим список списков:

         

           [[d,a],[e,b,a],[f,c,a],[g,c,a]]

Теперь, как видим, на первое место выходит элемент «d» - последний в списке вершин 2-го уровня, образованном от «a». Следующими будут рассмотрены вершины «e», «f», «g» , т.е. вершины 3-го уровня. Такой процесс продолжится, пока в голове одного из списков  не обнаружится конечная вершина пути. Этот список и будет искомым путём. В противном случае появится сообщение, что пути нет.

Рассмотрим программную реализацию изложенного алгоритма. Правило верхнего уровня:

         search(BN, EN, Result): - widesearch ([[BN]], EN, Result).

        Первые два аргумента целевого предиката search являются задаваемыми начальной (BN) и конечной (EN) вершинами искомого пути. Третий аргумент Result - возвращаемый список вершин искомого пути (если, конечно, таковой имеется).

        Первый аргумент предиката widesearch - список инверсных путей от всех текущих, еще не рассмотренных на предмет совпадения с целью, вершин данного уровня графа к исходной вершине. Этот аргумент описан как список списков. Остальные аргументы имеют тот же смысл что и в search. При первом вызове widesearch рассмотренного правила первый аргумент состоит только из исходной вершины BN.

        Основное правило поиска состоит из 2-х предложений:

      widesearch([[Node|Path]|_], EN, [Node|Path]: - Node = EN,!.

      widesearch([[Node|Path]|Paths], EN, Result):-findall(X,nextpath(Node, Path, X),NextPaths),

      append(Paths, NextPaths, NewPaths),!, widesearch(NewPaths, EN, Result).   

        Первое предложение служит для опознавания одного из путей [Node|Path], стоящего в голове списка списков, как искомого, если голова Node этого  пути совпадет с заданной конечной вершиной EN. В этом случае он как третий аргумент предиката widesearch будет передан переменной Resault запроса. Поиск успешен.  

         Если совпадения  Node и EN не произошло, подключается 2-ое предложение  widesearch, которое выполняет всю основную работу по формированию новых путей от вершины  “а” на следующий уровень. Вначале предикат findall вызывает правило nextpath:

    nextpath(Node, Path, [NextNode, Node|Path]): -  edge(Node,  NextNode).

        Это правило добавляет в голову списка Node|Path = [а]  одну вершину следующего уровня  [NextNode,Node|Path], определяя ее с помощью факта edge. В вызывающий предикат nextpath  правила findall  этот новый путь [NextNode,Node|Path] возвращается на место свободной переменной X. В рассмотренном выше примере это будет список [b, a]. Затем предикат findall повторяет вызов правила nextpath для поиска других возможных продолжений от  Node вниз на следующий уровень, т.е. с и d, и собирает полученные списки  в своем третьем аргументе NextPaths. В нашем примере переменная NextPaths получит значение [[b, a], [c, a], [d, a]]. Следующий предикат append вызывает правило объединения двух списков в третий, выходной  список. Аргументы append должны быть описаны как списки списков. Первый аргумент — хвост предыдущего списка путей Paths, в нашем случае он пока пустой, второй — новые  пути NextPaths, третий — результат их объединения в список NewPaths, т.е. в NewPaths получим список [[b, a], [c, a], [d, a]]. Этот  список списков передается последнему предикату widesearch в качестве 1-го аргумента и происходит рекурсивный вызов правила widrsearch. Первое предложение этого правила опять проверит выполнимость условия окончания поиска по совпадению головного элемента головного списка, в данном случае, b  с заданной конечной EN. Если совпадения не произошло, то второе предложение widesearch будет искать продолжения пути от неуспешной вершины b на следующий уровень в том же порядке, какой был описан выше.

Самостоятельная часть работы.

  •     Объясните на примере с выбранной целевой вершиной работу программы с указанием значений переменных на каждом шаге;
  •     Выпишите  из текста программы правило append. Поставьте цель типа append([a, b], [d, c], L) и составьте протокол работы правила.  

        Задание 1.7. Поиск «в ширину» на графе, не имеющем транзитивных ребер

        Граф представлен с помощью фактов edge(x,y). Цель поиска задается в виде предиката path(X,Y). Программа проверяет возможность достижения заданной конечной вершины Y из заданной начальной X, используя прямой метод поиска с перебором вершин «в ширину». Если задача решена, программа определяет путь из Y в X методом обратного поиска (от целевой вершины к исходной). Такой метод эффективен, так как не требует обхода графа (см. Задание №1.1.2) и хранения в стеке  путей во все вершины данного уровня графа. При печати список вершин пути выводится в обратном порядке, т.е. от X к Y, и получается прямой список.

        Правило верхнего уровня разбивается на два предложения:

        path(X,X):-write(«Из»,X, «в»,X, «путь есть  =[‘ ”,X, “ ’]”),!.

        path(X,Y):- not(path1(X,Y)), write («Из»,X, «в»,Y, «путь есть  = »),

        revers_path(X,Y,Path), write(«[»),write_list(Path),write(«]»).

        Первое предложение предусматривает случай совпадения начальной и конечной вершин в запросе. Если исключить это предложение, то на подобный запрос 2-ое предложение даст ответ, что из X в X пути нет. Второе предложение организует, путём вызова подчиненного правила path1, проверку достижимости вершины Y из вершины X. Правило path1 выполняет поиск «в ширину»:

        path1(X,Y):-findall (Next, edge (X, Next), Next_point),

                             next_level (Next_point, Y).

Предикат findall, используя факты edge, срабатывает многократно и собирает все вершины Next, порождённые от рассматриваемой вершины X, в список Next_point вершин следующего уровня. Так как X - исходная вершина 1-го уровня, то Next_point - список вершин 2-го уровня. Этот список передаётся в качестве 1-го аргумента  предикату next_level, который вызывает соответствующее правило:

next_level([  ], Y): - !.

next_level (NEW, Y): - search_in_l (Y, NEW, NEW1), next_level (NEW1, Y).

Задача правила next_level состоит в том, чтобы получить в переменную Y целевую вершину,  в переменную NEW - список вершин следующего уровня, и с помощью предиката search_in_l  вызвать соответствующее правило  поиска целевой вершины Y среди вершин списка текущего уровня NEW. В случае неуспешного поиска правило search_in_l вернет в переменной NEW1 список вершин следующего уровня графа и передаст его последнему предикату для рекурсивного вызова того же правила, но уже со списком вершин следующего уровня. Таким образом правило path1 отыскивает список только вершин второго уровня в начале работы программы. Списки вершин следующих уровней определяет правило search_in_l. Оно же отыскивает целевую вершину. Вот его текст:

  search_in_l(A,[],[]):-!.

  search_in_l(A,[A|_],_):-!,fail.

  search_in_l(A,[EL|Tail],Next_p):-

                 search_in_l(A,Tail,Next_p1),

                 findall(Next,edge(EL,Next),Next_p_find),

                 append(Next_p1,Next_p_find,Next_p),!.

В первый аргумент А вызывающий предикат search_in_l (Y, NEW, NEW1)  передает заданную целевую вершину Y, а во второй – список вершин текущего уровня. Третья переменная пока свободна.

Вызывающий предикат search_in_l  с указанными значениями аргументов поочерёдно сопоставляется с каждым из вышеприведенных предложений. Первое предложение может стать истинным в случае, если список во 2-ом аргументе вызывающего предиката search_in_l  пуст. Тогда и третий аргумент  в предикате search_in_l  первого предложения рассматриваемого правила получит значение  пустого списка. Но в начале список NEW не пустой, поэтому первая строка пропускается.

Второе предложение может стать истинным в случае совпадения заданной целевой вершины Y  с головой списка, содержащегося во 2-ом аргументе. Это означает успех поиска, однако, fail в конце предложения определяет  неудачу в целом правила search_in_l , а с ним и  правил next_level и path1. Но поскольку в  правиле path предикат path1 записан с отрицанием, выражение not(path1(X,Y)) станет истинным. Такая конструкция из not и fail позволяет предотвратить ненужный следующий вызов правила search_in_l   в случае успеха поиска. Правило path напечатает сообщение “Путь из X в Y есть”, и передаст управление предикату revers_path с означенными начальной и конечной вершинами и свободной переменной Path, в которую требуется вернуть путь из Х в Y. Мы вернемся к этим правилам позднее.

Третье предложение правила search_in_l вступает в действие, когда первые два не истинны. Оно отделяет голову списка вершин текущего уровня и рекурсивно вызывает само себя с хвостом этого списка. Сопоставление вновь идет с первыми двумя предложениями, и если список хвоста не пуст и его головной элемент не совпадает с целевой вершиной, то  список вершин уровня продолжает укорачиваться до тех пор, пока либо не произойдёт совпадения А с очередной головой списка (этот случай уже рассмотрен), либо хвост списка Tail не окажется пустым списком. В этом случае срабатывает 1-ое предложение search_in_l, и его третий аргумент получает значение пустого списка. Разворачивание рекурсии заканчивается и список Next_p1 в теле правила  также получает начальное значение []. В этом момент переменная El  имеет значение последней вершины списка вершин уровня.  C этого же момента вступает в действие предикат findall, который, используя факты edge, соберёт в список Next_p_find все вершины следующего уровня Next, непосредственно связанные с El. Далее правило append объединит списки Next_p1 =[] и Next_p_find  в список Next_p  и передаст его в голову рассматриваемого правила. Список Next_p1 в теле правила получит то же значение, т.е. списки Next_p и Next_p1 будут одинаковы и отвечать данному значению переменной El.  Далее действует механизм возврата (return), при котором в переменую El будут поочерёдно в обратном порядке возвращаться отделявшиеся ранее головные элементы списка вершин уровня. С каждым из этих элементов будет проделана та же работа, и список вершин следующего уровня будет постепенно пополняться, пока не превратится в окончательный список вершин следующего уровня графа Next_p. Этот список означит собой третий аргумент правила search_in_l, который и будет возвращен в переменную NEW1 вызывающего предиката search_in_l правила next_level. Кстати, в этот момент во 2-ом  аргументе головного предиката search_in_l  (El|Tail) восстановится исходный список вершин предыдущего уровня. Эти значения аргументов и будут возвращены в вызывающий предикат search_in_l  правила next_level. Далее работа продолжится вышеописанным образом.

Теперь вернемся к обработке результата успешного поиска. Мы остановились на передаче управления правилу поиска списка пути из найденной целевой вершины Y в исходную вершину Х. Эта задача решается с помощью правила revers_path, аналогичного правилу из задания № 1.1.2:

        revers_path(Y,Y,[Y]).

        revers_path( X,Y,[Y|P]):- edge(N,Y), revers_path(X,N,P).

Правило рекурсивно и отыскивает инверсный путь из найденной конечной вершины Y в исходную X методом обратного поиска. В данном случае оно работает независимо от основной программы, в чём можно убедиться, задав цель revers_path(x,y,P). Здесь x и y - конкретные вершины дерева. В итоге работы рассматриваемого правила в третьем аргументе [Y|P] собирается путь от Y к X. Этот путь и означит переменную Path в вызывающем предикате revers_path правила path. Последняя операция заключается в вызове правила write_list(Path) для печати в обратном порядке списка  Path:

        write_list([]):-!.

        write_list([H|Tail]):- write_list(Tail), write(«  »,H).

Самостоятельная часть работы.

Рассмотрите работу программы в шаговом режиме, чтобы убедиться в том, что поиск идет в ширину, а не в глубину.

Проверьте с помощью трассировки, что произойдет, если заставить правило search_in_l вызывать себя рекурсивно со значением во втором аргументе найденного списка вершин следующего уровня?

Как программа реагирует на введение в список фактов транзитивных ребер, например, (edge a, d)?

Задание № 1.8. Поиск «в ширину» кратчайшего пути в графе с транзитивными рёбрами.

        Следующая программа SHIR также осуществляет прямой    поиск с обходом вершин в ширину, однако, позволяет обрабатывать графы с транзитивными рёбрами, когда возможен не один  путь в найденную вершину, и нужно выводить кратчайший  из них. Предыдущая программа в задании № 1.7 этим свойством не обладала. Поясним сказанное на примере. На рисунке слева изображён граф с альтернативными путями из вершины x в вершины h и z, на рисунке справа - граф кратчайших путей в эти вершины.

      

 По одному из 2-х возможных на рисунке слева путей в вершину h эта вершина принадлежит  3-му уровню, по другому - 4-му. Вершина z по одному пути - на 4-ом уровне, по другому - на 5-ом. Для вывода кратчайшего (по числу рёбер) пути программа запоминает все рассмотренные вершины данного уровня и в качестве продолжения пути предлагает только не рассмотренные на предыдущем уровне графа вершины. Так, при рассмотрении вершин 3-го уровня в этот список войдут d, h, e и i на рисунке слева. При поиске вершин 4-го уровня для продолжения пути от «d» и «e»  вершины соответственно «h» и «i»  уже не будут приняты во внимание, так как содержатся в списке  рассмотренных. Поэтому рёбра «d - h» и «e - i» исключаются из возможных путей (см.рис. справа). Отсюда следует, что путь из «x» в «z» будет «x - c - i - z», а не более длинный «x - a - e - i - z», казавшийся возможным на рисунке слева.   А путь из «x» в «h» будет «x - a - h», а не «x - a - d - h», казавшийся также возможным на рисунке слева. В итоге на правом рисунке получим граф кратчайших путей. Ребра кратчайших путей заносятся в БД с помощью предиката minedge.

        Рассмотрим предлагаемую программу. Правило верхнего уровня:

        shir(X,Y):-retractall(minedge(_,_)), put([X],[X],Y,[]), otvet(X,Y,[Y]).

        Основное правило поиска вызывается предикатом  put(L,V,Y,N), где L - список вершин текущего уровня (вначале он [X]), V -список всех рассмотренных (посещённых) вершин (вначале он равен [X]), Y - заданная концевая вершина пути, N - список вершин следующего уровня графа (вначале он [  ]).

        put([], All, Y, Level) : - write(«Level»), writelist (Level), nl, write («NewAll»),

                                               writelist(All), nl, put1 (All,Y,Level).

        put([X|Tail], Allvisit, Y, Level) : -    findall(Top, newtop(X, Allvisit, Top), Tops),

                                                    append(Tops, Level, Newlevel), append(Tops, Allvisit, NewAll),

                                                    put(Tail, NewAll, Y, Newlevel).

        Первое предложение обрабатывает крайний случай, когда список вершин текущего уровня становится пустым (таким его делает второе предложение данного правила). Тогда программа выводит списки вершин следующего уровня (Level) и всех посещённых вершин (All) и передаёт управление правилу put1(All,Y,Level), которое будет проверять условия окончания поиска вершины Y в списке текущего уровня Level. Его мы рассмотрим позднее. Второе предложение правила put отыскивает все возможные продолжения пути для вершины X (головы списка вершин текущего уровня графа). Для этого предикат findall  неоднократно обращается к правилу newtop:

        newtop(X,Allvisit,Top):-edge(X,Top), not(member(Top,Allvisit)),

        asserta(minedge(X,Top)).

        Правило newtop получает от правила put в качестве 1-го аргумента значение головного элемента списка вершин текущего уровня Х, в качестве 2-го аргумента Allvisit ему передается список всех посещенных вершин, а переменная Top свободна. Она должна получить значение соседней с Х вершины следующего уровня при условии, что эта вершина отсутствует в списке посещенных вершин Allvisit. В результате findall в правиле put соберёт в список Tops все вершины Top, связанные с X отношением edge и при этом не содержащиеся в списке рассмотренных (посещённых) вершин Allvisit. Одновременно правило newtop  вносит во временную БД каждый найденный факт связи вершины X c вершиной Top в виде предиката minedge в том случае, если вершина Top не рассматривалась в списке вершин предыдущего уровня. Поэтому все рёбра  minedge(X, Top) в БД будут принадлежать только кратчайшим путям (см. пояснение выше).

        Вернёмся ко второму предложению правила put. С помощью 1-го вызова правила append происходит объединение списков порождённых вершин Tops и вершин следующего уровня Level (вначале он пуст) в новый список следующего уровня Newlevel. Второе применение правила append объединяет список Tops со списком посещённых вершин Allvisit в новый список посещённых вершин Newall. Далее правило put рекурсивно вызывает само себя для аналогичного поиска продолжений от следующей вершины рассматриваемого уровня. Так происходит до тех пор, пока не будет исчерпан список вершин текущего уровня и первый аргумент put получит значение [ ]. Этот случай, который приводит к срабатыванию 1-го предложения правила put, уже рассмотрен выше, но не до конца. Правило put  вызовет правило put1, которое будет проверять присутствие целевой вершины в списке вершин текущего уровня Tops:

        put1(_,_,[]):-write(«Пути нет»),nl,!.

        put1(_,Y,Tops):-member(Y,Tops), write («Путь есть. Ответ:»),!.

        put1(All,Y,Tops): - put(Tops,All,Y,[]).

        Первое предложение срабатывает, когда список вершин следующего уровня (третий аргумент) пуст, т.е. цель не достигнута, а нового уровня нет, а значит, нет и пути. Второе предложение срабатывает, когда искомая вершина Y содержится в списке вершин данного уровня Tops. Третье предложение срабатывает, когда вершина Y не найдена, но возможности поиска ещё не исчерпаны - список Tops не пустой, и он становится списком текущего уровня. В этом случае вновь вызывается правило put. Обратите внимание на то, что при вызове put  4-ый аргумент - исходный список вершин следующего уровня - пуст, как и при первом вызове; Tops - вершины предыдущего уровня, от которых put будет отыскивать продолжения пути; All - все посещённые вершины; Y - искомая вершина.

        Окончание поиска происходит, если срабатывают (становятся истинными) 1-ое или 2-ое предложения put1 и правило put в целом также становится истинным.. Следующим будет рассмотрен последний предикат otvet в правиле shir:

        otvet(X,X, [X]).

        otvet(X, Y, [Y|P) : - minedge(Z,Y), otvet(X, Z, P).

Это правило аналогично правилам из заданий №1.1.2 или №1.7, но использует базу фактов кратчайших путей. Правило осуществляет обратный поиск кратчайшего пути из терминальной вершины Y в исходную X. Напомним, что рёбра minedge во временной БД принадлежат только кратчайшим путям и задача  состоит в отыскании на каждом шаге поиска единственной вершины Z, предшествующей вершине Y в факте minedge(Z,Y). Когда предшествующая вершина Z совпадёт с исходной X, сработает 1-ое предложение правила otvet и начнется обратный ход рекурсии. В результате третий аргумент будет содержать обратный список пути из Y в Х и передаст его в третий аргумент целевого предиката shir.

Самостоятельная часть работы

Изобразите граф по приведенным фактам edge и убедитесь, что программа выводит кратчайший из возможных путей, если у целевой вершины есть транзитивные ребра.

Проверьте на примере, сможет ли Ваша программа работать с графом, имеющим цикл.

Объясните на примере работу программы

Задание № 1.9. Программирование поиска в глубину на конечном графе пространства состояний на языке CLIPS

Возможности среды и языка программирования CLIPS шире тех, которые принято рассматривать в технической документации и литературе по экспертным системам. CLIPS, в частности, может поддерживать модель поиска пути на графе пространства состояний, хотя и не является языком логического программирования, как Пролог. В отличие от Пролога, правила здесь логически не связаны между собой (независимы) и не образуют сети вывода. Любое из них может быть запущено на выполнение, если удовлетворены условия этого правила и оно имеет в данный момент высший приоритет. Как же обеспечить приоритет одного и того же правила поиска связи соседней вершины с только что найденной для поиска пути в графе,  учитывая, что правило на CLIPS’е не может рекурсивно вызывать само себя или другое правило по имени? Для этого предусмотрена стратегия depth (в глубину): из числа активизированных и имеющих равный приоритет правил выбирается то, условия которого удовлетворены самым “свежим” (с наибольшим индексом) фактом в списке фактов. CLIPS нумерует факты по мере поступления. При каждом своем помещении в список факт получает наивысший индекс, т.е. становится самым свежим. Теперь представим себе, что правило поиска пути само же обновляет   факт связи текущей вершины с  соседней,  помещая в список с новым индексом. Тогда данное правило будет запускаться повторно  этим свежим фактом, отыскивая следующую соседнюю вершину искомого пути. Произойдет обход графа в глубину. Такой способ можно назвать псевдо рекурсивным, поскольку управление осуществляется через данные. Для его реализации в меню Execution/Options должна быть установлена  стратегия depth (в глубину). Обычно она стоит по умолчанию. Однако этого еще не достаточно. Необходимо разработать правило возврата к предыдущей развилке графа, если поиск не успешен, т.е. реализовать процедуру, которая на Прологе называется backtracking и уже заложена в механизм логического вывода.

Рассмотрим пример программы (полный текст содержится в файле mypath.clp) поиска пути на графе, заданном множеством фактов связи двух соседних вершин (edge <имя_начальной_вершины> <имя_конечной_вершины>). Такие факты не симметричны, описывают направленный ориентированный граф (дерево).

(deffacts  edges

       (edge d  j)

       (edge a  c)

       (edge c  g)

       (edge f  h)

       (edge f  i)

       (edge c  f)

       (edge a  d)

)

Факты в конструкторе deffacts с именем edges специально записаны в произвольном порядке. При загрузке программы и выполнении  команды (reset) факты помещаются в список и каждый получает свой порядковый индекс f-0, ….f-7.

Отметим, что в начале списка стоит факт с индексом f-0  (initial-fact), который всегда помещается в список по команде (reset) для возможности однократного запуска какого-либо стартового безусловного правила. Таким в данном случае является правило input. Условия-запросы остальных правил пока не удовлетворены из-за отсутствия в списке подходящих фактов. Правило input служит для считывания с экрана имен начальной и конечной вершин поиска и помещения в список новых фактов с помощью функции assert. Предположим, мы ввели в качестве начальной вершины “a”, конечной – “i”. В список будут добавлены факты (top-from  a) и (top-to  i) с индексами соответственно f-8 и f-9.

Разобраться в работе программы можно с помощью ее выполнения по шагам в режиме Step. Для этого запустите CLIPS (файл CLIPSWin.exe). Выберите в меню Execution комаyду Watch и в открывшейся панели пометьте окошки Facts и Rules. Затем выполните команды File/Load/mypath.clp/Открыть. При отсутствии ошибок в программе на экране появится список всех конструкторов и приглашение CLIPS>. Вновь зайдите в меню Execution и выполните команду Reset. Появится список всех исходных фактов с индексами (см. рис. выше). Вновь зайдите в меню Execution и выполните команду Step. По приглашению введите с экрана начальную, а затем конечную вершины. Пусть это будут а и i соответственно. Наблюдайте далее за выполнением программы с помощью команд Execution/Step. На экране будет отображаться, какое правило активизировано (FIRE), от каких фактов, и какие изменения происходят в списке фактов при выполнении правила. Некоторые пояснения к работе программы даны ниже.  

Интерпретатор (МЛВ)  просматривает сверху вниз список всех правил, сопоставляя  их левую часть (образцы) с фактами в списке, и пытаясь отыскать те правила, условия которых удовлетворены какими-либо фактами. Будет найдено одно такое правило start, которое при своем запуске поместит в текущий список факт (way  a) с индексом f-10.

В следующем цикле может сработать только правило search, предназначенное для поиска  пути. Запрос из его левой части (way  ?x) будет удовлетворен самым свежим фактом f-10 и переменная ?x получит значение “a”. Следующие логические подзапросы получат значение TRUE, так как нет фактов с именем out, а запрос (edge a  ?z) будет удовлетворен фактом (edge a  d), имеющим индекс f-7, а не аналогичным фактом (edge a  c) с меньшим индексом f-2. Таким образом ?z получит значение d, и с помощью функции assert в список будет помещен факт (way  d), который получит индекс f-11. Тем самым будет совершен шаг ‘в глубину’ на пути к целевой вершине.

На следующем шаге опять может активизироваться только правило search. Правило step-back, предназначенное для возврата, не может быть активизировано, поскольку не выполнено ни одно из условий or. Итак, правило search активизируется самым свежим фактом (way  d), запрос (edge d  ?z) будет удовлетворен фактом (edge d  j), и в список будет помещен факт (way  j) с индексом f-12. Тем самым будет сделан второй шаг поиска. Следующая попытка запустить то же правило search окажется неудачной, поскольку в списке нет фактов связи j со следующей вершиной. Поиск не успешен и надо совершить возврат. Посмотрим на условия правила step-back. Запрос (way  ?x) удовлетворяется свежим фактом  (way  j) и переменная ?x получит значение j. В подзапросе or удовлетворяется первая строка, а в подзапросе (edge ?z  ?x) переменная ?z получит значение d по факту f-1 ( поскольку ?x = j). Далее в условной части правила факты (way  d) и (way  j) связываются каждый (с помощью левой стрелки) соответственно с указателями адресов f1  и  f2 для возможности последующего своего удаления. В правой части правила выполняются следующие действия. В список помещается факт, исключающий повторное обращение к вершине j  (out  j) с индексом f-13, удаляются из списка факты (way  j) и (way  d) c индексами соответственно f-12 и f-11, и вновь добавляется факт (way  d), но уже с индексом f-14. Тем самым будет выполнен один шаг назад к вершине d.

При следующем сопоставлении условий правил с фактами опять оказываются удовлетворены условия только правила step-back  Запрос (way  ?x) будет удовлетворен самым свежим фактом (way  d) и переменная ?x получит значение d. В подзапросе or окажутся удовлетворены условия строки and: подзапрос (edge ?x  ?y) будет удовлетворен фактом (edge d  j) и тем, что в списке есть факт (out  j) c индексом f-13. В следующем подзапросе (edge ?z  ?x) сработает факт (edge  a  d) и переменная ?z получит значение “a”. Далее факты (way  a)  и  (way  d) готовятся к удалению, связываясь с указателями их адресов f1 и f2. В правой части правила выполняются следующие действия. В список добавляется факт (out  d), чтобы программа не возвращалась к вершине d, удаляются факты (way  d) и (way  a) с индексами f-14 и f-10 соответственно, и добавляется факт (way  a) с новым индексом f-16. Как мы видим, программа вернулась к исходной вершине а. Теперь условия правила step-back окажутся не выполнены, так как вершина “a” связана с “с” и нет факта (out  c). Но теперь окажутся выполнены условия правила search. Запрос (way  ?x) будет удовлетворен свежим фактом (way  a) с индексом f-16 и переменная ?x получит значение “а”. Факта (out  a) нет, в подзапросе (edge a  ?z) переменная ?z получит значение “с” по сопоставлению с фактом (edge a  c), и факта (out  c) нет в списке. В правой части правила будет добавлен факт (way  c) с индексом f-17. Как видим, поиск продолжился по другой ветви графа.

Далее вновь будет выбрано правило search, которое в запросе (edge c  ?z) из двух возможных вариантов использует факт с большим индексом (edge c  f). В список будет помещен факт (way f) с индексом f-18. Этот факт вновь активизирует правило search, которое из двух фактов (edge f  h) или (edge f  i) выберет последний как имеющий больший индекс f-5. Но вершина i является целевой. В списке уже имеется факт (top-to i) и теперь появился факт (way  i) с индексом f-19. Окажутся удовлетворены условия правил stop и print, но правило print имеет более высокий приоритет по свойству salience и поэтому будет запущено на выполнение. В этом правиле запрос (way  ?x)  будет удовлетворен фактом c наибольшим индексом, т.е. (way  i). В правой части будет выполнена печать этого факта: (way  i). Но правило print будет вызвано еще раз и запрос (way  ?x) будет удовлетворен следующим по “свежести” фактом f-18: (way f). На печать будет выведен факт (way  f). Аналогичным образом на следующем этапе на печать будут  последовательно выведены факты с индексом f-17: (way  c) и с индексом f-16: (way  a). Больше правило print запускаться не будет, так как остальные факты (way) либо удалены в ходе поиска, либо содержатся в списке (out), что не допускается одним из условий правила print. Но оно уже вывело вершины пути из i в а в виде фактов (way i) (way f)  (way  c)  (way  a).

Теперь появилась возможность активизации  правила stop, которое по команде halt останавливает поиск. Решение уже выведено на печать. Но если дать команду (run) или (step), то дальнейший, теперь уже бессмысленный, поиск будет продолжен с полным обходом оставшихся ветвей дерева и выводом сообщения “No way”. Это сделает правило fail, предусмотренное на тот случай, если искомого пути в графе нет.

Самостоятельная часть работы

  •  Изучите работу программ, пользуясь ее текстом и режимом трассировки.
  •  Как программа будет реагировать на транзитивные ребра?


 

А также другие работы, которые могут Вас заинтересовать

50053. Изучение команд меню Corel Draw10 117.5 KB
  Команда предназначена для загрузки в активный документ векторного растрового или текстового файла. Существует возможность загрузки нескольких десятков форматов и этот набор охватывает большинство наиболее распространенных графических и текстовых форматов. Позволяет сохранить информацию активного документа в различных форматах векторных растровых и текстовых. Текстовая информация может быть экспортирована либо вся либо из текущей страницы при включенном режиме Export this pge only Экспортировать лишь текущую страницу.
50054. Определение теплоемкости твердого тела 116 KB
  Цель работы: 1 измерение зависимости повышения температуры исследуемого образца в муфельной печи от времени; 2 вычисление по результатам измерений теплоемкости исследуемого образца. В любой момент времени количество тепла поступившее от электронагревателя идет на нагрев установки и на излучение в окружающую среду: [2] Величина Qпотерь пропорциональна разнице температур между печью и окружающим воздухом и может быть принята равной нулю в начальный момент времени. Прямое определение величин в уравнении [2] в начальный момент...
50055. Измерение параметров емкостей в цепи переменного тока 195.5 KB
  Плеханова технический университет Кафедра Общей и технической физики лаборатория электромагнетизма Измерение параметров ЕМКОСТЕЙ в цепи переменного тока Методические указания к лабораторной работе № 6 САНКТПЕТЕРБУРГ 2009 УДК 531 534 075. Цель работы: Определение импеданса сдвига фаз и измерение емкости на разных частотах в резистивноемкостной цепи. При работе на переменном токе с реактивными элементами в цепи индуктивность емкость следует обязательно учитывать их реактивный характер проводимости. Кроме того реактивные элементы...
50057. ОПРЕДЕЛЕНИЕ МОМЕНТА ИНЕРЦИИ МАХОВОГО КОЛЕСА МЕТОДОМ КОЛЕБАНИЙ 286.5 KB
  Цель работы: Ознакомление с методом измерения моментов инерции тел обладающих осевой симметрией. Основные теоретические положения к данной работе (основополагающие утверждения: формулы, схематические рисунки)
50058. ВЫБОР СПЕЦОДЕЖДЫ, СПЕЦОБУВИ И ДРУГИХ СРЕДСТВ ИНДИВИДУАЛЬНОЙ ЗАЩИТЫ 108.5 KB
  Изучить Правила обеспечения работников специальной одеждой специальной обувью и другими средствами индивидуальной защиты принятыми Постановлением Министерства труда и социального развития РФ от 18 декабря 1998 г. Составить личную карточку учета выдачи средств индивидуальной защиты по представленной форме в соответствии с заданием. Типовые отраслевые нормы бесплатной выдачи специальной одежды специальной обуви и других средств индивидуальной защиты выдаются преподавателем или берутся из справочника по охране труда в сельском хозяйстве...
50059. Рефрактометр Рэлея 260.5 KB
  Элемент щели dx посылает в направлении φ волну с амплитудой пропорциональной dx. При этом будем считать что угол φ достаточно мал sin φ ≈ φ и что в правой щели искусственно создана дополнительная разность хода Δ одинаковая для всех ее элементов это позволит написать смещение интерференционных полос используемое для измерений в интерферометреРэлея. Интегрируя 3 найдем 4 где а расстояние между щелями b ширина щели. Первый из них описывает распределение интенсивности в дифракционной картине Фраунгофера от одной щели.
50060. Техніка пересувань футболістів у нападі та захисті 21 KB
  Футболіст пересувається короткими кроками і завжди повинен бути готовий до миттєвої зупинки або зміни темпу й напрямку руху. Найважливіше під час вистрибування вибрати відповідне місце відштовхування врахувавши швидкість та висоту руху м’яча. Ефективний спосіб пересувань – зміна напрямку руху. Для того щоб змінити напрямок руху з мінімальною втратою часу футболісти застосовують повороти: переступанням стрибком на опорній нозі.