Использование алгоритма Rete при выводе геометрических соотношений в графических редакторах

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Использование алгоритма Rete при выводе геометрических соотношений в графических редакторах

Митин А.А.

The article describes a declarative means of specifying relationships. Interactive graphical applications give the rise to varying kinds of constraints, and researchers. Several approaches have been proposed for inferring constraints from unfinished drawing.

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

Одним из алгоритмов, позволяющих осуществлять вывод геометрических соотношений в графических редакторах, является алгоритм Rete [1,2].

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

В качестве фактов рассматриваются атрибуты графических объектов редактора. Имея в своем распоряжении словарь символов и грамматику, регламентирующую порождение символических структур, можно представить в машинном виде исходное состояние графических объектов. Эти представления соответствуют аксиомам канонической системы - они представляют собой некоторую символическую структуру, которую нужно преобразовывать, применяя имеющиеся правила в определенном порядке [3]. В правилах условия должны соответствовать допустимым символическим структурам, а действия - содержать специальные операторы манипулирования такими структурами[4].

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

Затем, когда запись в отношении проходит операцию SELECT, отношение подвергается операции PROJECT, которая выделяет поле или поля, содержащие соответствия или связывания.

После прохождения записи через операции SELECT, PROJECT и операцию переименования, она добавляется к отношению, связанному с условием правила.

Альфа-узел в сети Rete - узел, в котором хранится отношение для определенного условия каждого правила. Отношение каждого альфа-узла накапливает все факты или утверждения, формирующиеся посредством операции SELECT.

Каждое добавление к отношению альфа-узла вызывает попытку объединить добавленную запись, представленную в виде отношения с единственной записью, с другим отношением. Необходимо отметить, что операция JOIN выполняется совместно с определением, является ли связывание переменной, выраженное в добавляемой записи, соответствующим связыванию переменной, уже установленному в другом отношении.

Бета-узел сети Rete - узел, хранящий результат объединения отношений. Отношение, хранящееся в бета-узле, включает записи пар связываний для переменных, которым удовлетворяют условия правила.

Так, пополнение отношения А₁ или отношения А₂ (рисунок 1) влечет за собой операцию JOIN, которая может добавить одну или несколько записей в отношение B₁₂, отражая связывания переменных, которые удовлетворяют первым двум условиям правила одновременно. При добавлении второй записи к отношению A₂ происходит циклический процесс. Новая запись, представленная отношением, объединяется с отношением A₁, формируя вторую запись для отношения B₁₂. Далее следующий факт инициирует цикл добавления записей в узлы сети Rete и пополняет записью, например, отношение A₃. Добавление записи в отношение A₃ приводит к объединению добавленной записи с отношением B₁₂ Операция JOIN выполняется совместно с определением того, является ли связывание переменной, выраженное в добавляемой записи, соответствующим связыванию переменной, уже установленному в отношении B₁₂. Результат генерируется в отношении B_23. Выполняя операцию PROJECT для записи по одной из переменных, в результате получается возможное связывание для переменной в выполняемой части правила.

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

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

Для формирования сети Rete используется следующий алгоритм:

1. Для каждого шаблона условия, которое содержится в правиле, сформировать операцию SELECT, которая проверяет новые факты.

2. Для каждого правила:

2.1 для каждого условия:

2.1.1 сформировать альфа-узел и связать его с соответствующей операцией SELECT, выполненной ранее.

3. Для каждого альфа-узла, за исключением первого:

3.1 cформировать бета-узел;

3.2 если бета-узел является первым бета-узлом, присоединить его к первому и второму альфа-узлам;

3.3 в противном случае, присоединить бета-узел к соответствующему альфа-узлу и предыдущему бета-узлу.

4. Применить операцию PROJECT к результирующему бета-узлу.

При использовании алгоритма Rete применяется следующая последовательность действий:

1. Для каждого факта выполнить операцию SELECT, проведя факт по сети Rete к соответствующему альфа-узлу.

2. Для каждого альфа-узла, получившего факт, использовать операцию PROJECT, чтобы выделить соответствующие связывания переменной. Провести эти новые связывания по сети Rete к соответствующим бета-узлам.

3. Для каждого бета-узла, получившего новые связывания переменной, применить операцию JOIN для формирования новых множеств связывания переменной. Провести эти новые множества связывания переменной к следующему бета-узлу или к заключительной операции PROJECT.

4. Для каждого правила использовать операцию PROJECT, чтобы выделить связывания переменной, необходимые для определения выполняемой части правила.

Для примера работы алгоритма Rete рассмотрим одно из используемых в системе правил, записанных на языке CLIPS. В частности, правило, отражающее соотношение длин между отрезками 1:2, выглядит следующим образом:

(defrule otr_proporc

(otrez ?Id ?x1 ?y1 ?x2 ?y2)

(newotrez ?Iden ?x3 ?y3 ?x4 ?y4)

(proporc_1_2 =(= (/ (sqrt (+ (** (- ?x2 ?x1) 2) (** (- ?y2 ?y1) 2))) (sqrt (+ (** (- ?x4 ?x3) 2) (** (- ?y4 ?y3) 2)))) 2.0))

=>

(bind ?len1 (sqrt (+ (** (- ?x2 ?x1) 2) (** (- ?y2 ?y1) 2))))

(bind ?len2 (sqrt (+ (** (- ?x4 ?x3) 2) (** (- ?y4 ?y3) 2))))

(printout t "The line " ?Iden " in 2 times is more than a line " ?Id crlf)

(printout t "The length of line " ?Id "=" ?len1 " and the length of line " ?Iden "=" ?len2 crlf crlf))

Имея в распоряжении факты или утверждения, можно представить их в табличном виде. На языке отношений факты записаны в отношение, названное “Данные”, где столбцы обозначены как Field₁, Field₂, Field₃, Field₄, Field₅, Field₆.

Таблица 1 - Отношение «Данные», представляющее множество фактов

Чтобы определить, какие значения переменных активизируют правило, сначала необходимо определить, какие записи отношения соответствуют первому условию правила, otrez ?Id ?x1 ?y1 ?x2 ?y2. То есть, необходимо найти такие записи, в которых значение поля Field₁ равно otrez. Таким образом, операция реляционной алгебры SELECT выделяет записи с заданным значением поля из одного отношения для формирования нового отношения с несколькими записями - SELECT from Данные where Field₁=otrez. Результатом будет являться новое отношение:

Таблица 2 - Отношение, соответствующее первому условию правила

Теперь необходимо знать, какие связывания переменных формируют записи отношения. В соответствие с этим используется другая операция реляционной алгебры PROJECT, чтобы выделить соответствующие поля - PROJECT Result over Field₂, Field₃, Field₄, Field₅, Field₆. В этот момент поля Field₂, Field₃, Field₄, Field₅, Field₆ переименовываются соответственно в Id, x₁, y₁, x₂,y₂, чтобы определить соответствия для переменных. В результате получается такое отношение:

Таблица 3 - Отношение A₁, определяющее соответствия для переменных

На следующем этапе необходимо определить, какие записи в отношении данных «Данные» соответствуют второму условию правила, newotrez ?Iden ?x3 ?y3 ?x4 ?y4. Для этого нужно выбрать те записи, у которых значение поля Field₁ равно newotrez, SELECT from Данные where Field₁=newotrez. Затем выполняя операцию PROJECT Result over Field₂, Field₃, Field₄, Field₅, Field₆ получим следующую таблицу:

алгоритм rete геометрический графический

Таблица 4 - Отношение A₂, соответствующее второму условию правила

На следующем этапе определяется, какие записи отношения данных соответствуют третьему условию правила, proporc_1_2 =(= (/ (sqrt (+ (** (- ?x2 ?x1) 2) (** (- ?y2 ?y1) 2))) (sqrt (+ (** (- ?x4 ?x3) 2) (** (- ?y4 ?y3) 2)))) 2.0). Так как, в третьем условии правила вычисляется отношение пропорции, то из исходного отношения данных выбираются записи, у которых значение поля Field₁ равно proporc_1_2 - SELECT from Данные where Field₁=proporc_1_2. Получается отношение, представленное в таблице 5.

Таблица 5 - Отношение A₃,соответствующее третьему антецеденту правила

Так как в третьем условии правила используется логическое выражение, то из отношений A1 и A2 выбираются только те записи, в которых значения соответствующих переменных делают истинным логическое выражение, определенное в третьем условии правила. Сначала происходит объединение отношений A₁ и A₂. Результирующее отношение B₁₂ имеет такой вид:

Таблица 6 - Отношение B₁₂ как результат объединения отношений A₁ и A₂

Полученное отношение объединяется с отношением A₃. В результате получается такое отношение:

Таблица 7 - Отношение B₂₃ как результат объединения отношений B₁₂ и A₃

Из полученного отношения можно видеть, что всем трем условиям правила удовлетворяет лишь единственная запись.

Из нее можно определить значения переменных - идентификаторов отрезков, координаты концевых точек отрезков. Соответственно в выполняемой части правила формируется заключение, что на отрезки с данными идентификаторами накладывается отношение пропорции их длин 1:2.

Сеть Rete, соответствующая данному правилу, представлена на рисунке 1.

Рисунок 1 - Сеть Rete для правила, проверяющего соотношение пропорции 1:2 между двумя отрезками

Одной из проблем рассмотренного алгоритма является большое количество вычислений. Так, если правило содержит n условий, то требуется n операций SELECT и PROJECT для формирования отношений A наряду с числом операций JOIN и PROJECT, равным n-1, формирующим отношения B. Если количество правил составляет m и правило проверяется каждый раз, когда новый факт добавляется к отношению данных, то необходимо выполнить m*n операций SELECT, m*(2*n-1) операций PROJECT и m*(n-1) операций JOIN каждый раз, когда добавляется новый факт.

ЛИТЕРАТУРА

1. Myers B.A. Creating Interaction Techniques by Demonstration //

2. IEEE Computer Graphics and Applications.-1987.- P.51-60.

3. Myers B.A. Creating User Interfaces by Demonstration. - Boston:

4. Academic Press. -1988.

5. Borning A., Duisberg. Constraint-Based Tools for Building User

6. Interfaces //ACM Transactions on Graphics,1986.-Vol.5.-N.4.-P.345-374.

7. Питер Джексон “Введение в экспертные системы”. Пер. с англ.: Уч. Пособие. - М.: Издательский дом “Вильямс”, 2001. - 624 с.

Размещено на Allbest.ru