Этап сопоставления

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

Операция сопоставления требует значительных вычислений, т.к. для определения конфликтного набора надо проверить условия всех активных правил на всех сочетаниях активных данных.

В связи с тем, что скорость работы является одной из главных проблем ЭС, необходимо обеспечить эффективность операции сопоставления.

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

В более эффективных формах индексирования с каждым образцом в правиле связывается счетчик. В начале работы значения всех счетчиков равны 0. При введении некоторого элемента в рабочую память функция "индексирования" определяет, какие образцы сопоставляются с этим элементом, и добавляет к их счетчикам по 1. При устранении некоторого элемента из рабочей памяти единица вычитается из тех счетчиков, образцы которых сопоставлялись с этим элементом. При выполнении сопоставления интерпретатор рассматривает только те правила, в условии которых все образцы имеют ненулевые значения счетчиков.

Далее, рассмотрим эффективный алгоритм (Rete) сопоставления, который можно характеризовать как индексирование, не требующее последующей интерпретации. Неэффективность простейших алгоритмов сопоставления обусловлена тем, что в каждом цикле работы интерпретатора для получения конфликтного набора заново осуществляется просмотр рабочей памяти и памяти правил. Очевидно, что значительная часть означиваний, полученных на предыдущем цикле, может быть сохранена и использована далее. Чтобы избежать лишних просмотров рабочей памяти, необходимо запомнить определенную информацию и передавать ее от цикла к циклу. Повторных просмотров можно избежать, связав с каждым образцом список элементов, с которыми он сопоставляется. Этот список должен модифицироваться при каждом изменении рабочей памяти. Если некоторый набор вводится в рабочую память или модифицируется, то интерпретатор находит все образцы, которые сопоставляются с этим элементом, и добавляет его к спискам соответствующих образцов. При удалении элемента из рабочей памяти соответственно удаляются элементы и из списков. Таким образом, интерпретатор, запоминающий указанную информацию, никогда не просматривает рабочую память. Алгоритм Rete получает на вход информацию об изменении рабочей памяти и формирует те изменения, которые надо произвести над конфликтным набором. Описания изменений рабочей памяти, поступающие в Rete-алгоритм, называют признаками. Задача алгоритма состоит в том, чтобы определить, какие правила будут удовлетворены поступившими на вход признаками. Простейшее решение - это сопоставление признаков со всеми правилами. При таком подходе будет много лишних просмотров. Для того, чтобы избежать лишних сопоставлений, образцы правил организуются в сетевую структуру, которая выполняет функции индексирования правил. Сеть образцов представляет собой разновидность дискриминационной сети. В вершинах дискриминационной сети проверяются характеристики элементов. В зависимости от результатов проверок признак, поступивший на вход сети, пройдет через сеть по тому или иному пути, и, как результат, сообщит, какие правила удовлетворяют этому признаку. Сеть составляется специальной программой на основе анализа условий правил, хранимых в рабочей памяти.

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