5. Характеристика машины логического вывода
Машина логического вывода обеспечивает формирование цепочек рассуждений. Цепочки рассуждений строятся на основе некоторого набора стратегий. Набор стратегий позволяет рассматривать альтернативные возможности в ходе работы и обеспечивать переход при неудаче от одной стратегии к другой. Существует два способа использования правил для построения цепочек рассуждений. Один называется прямой цепочкой рассуждений, другой обратной цепочкой рассуждений. При реализации прямой цепочки рассуждений правила последовательно просматриваются, до тех пор, пока не встречается правило, которое, во-первых, содержит всю необходимую информацию для применения; во-вторых, порождает новые фактические знания. После применения данного правила и порождения нового знания машина логического вывода может либо начать просмотр правил с начала, либо продолжить просмотр. Заканчиваться прямая цепочка рассуждений может следующими вариантами: во-первых, рассмотрели все правила, которые можно использовать при данном фактическом материале; во-вторых, вывели требуемое фактическое знание. Пример прямой цепочки рассуждений. Имеется база знаний.Правила Факты
( Процедурные (Начальные
знания ) знания )
F & I -> A C , D
C & I -> Z
B & C -> E
D -> F
F & C -> I
D & I -> B
В качестве окончания прямой цепочки рассуждения принимается вариант вывода требуемого фактического знания. Требуемое фактическое знание “Z”. Машина логического вывода, действуя в соответствии с прямой цепочкой рассуждений, рассмотрит все правила базы знаний и выберет правило “D->F“. Применение этого правила позволит породить факт “F”. После порождения факта “F”, фактические знания будут включать уже три факта “C,D,F“. Независимо от того, будет ли продолжаться просмотр с очередного правила или просмотр будет продолжаться с начала базы знаний, вторым будет выбрано правило “F&C->I“. Данное правило порождает факт “I”. Фактические знания расширяются до набора “C,D,F,I“. Выбор третьего правила зависит от того, какой вариант просмотра будет использоваться. Если просмотр будет продолжаться с очередного правила, то будет выбрано правило “D&I->B“. Если просмотр будет продолжаться с начала базы знаний, то будет выбрано правило “F&I->A“. Далее разбирается вариант продолжения просмотра с очередного правила. После применения правила “D&I->B“ будут включать “C,D,F,I,B“. Данное правило является последним в базе знаний и поэтому, просмотр будет продолжаться с начала базы знаний. Четвертым будет применено правило “F&I->A“. Применение данного правила приведет к расширению набора имеющихся фактических знаний до состава “C,D,F,I,B,A“. Последним будет применено правило “C&I->Z“. Данное правило позволит породить требуемое фактическое знание (терминальный факт) “Z”. На этом работа машины логического вывода будет завершена. Таким образом, цепочка применимых правил будет выглядеть: D — > F F & C -> I D & I -> B F & I -> A C & I -> Z Цепочка порожденных фактов будет иметь вид:F , I , B , A , Z .
Однако, если бы условием завершения работы машины логического вывода было бы требование порождения всех возможных фактов, то было бы применено еще одно правило “B&C®E“ и породился бы еще один факт. Рассмотрим алгоритм прямой цепочки рассуждений, реализованный в среде DELPHI. Алгоритм предусматривает повторяющийся просмотр всех правил, входящих в базу знаний. Отказ от повторения просмотра и завершение алгоритма предусматривается в двух случаях: во-первых, найден терминальный факт; во-вторых, при просмотре всех правил не было порождено ни одного нового факта и повторение просмотра бессмысленно. Просмотр правил выполняется последовательно. Предусматривается возможность прерывания просмотра при нахождении терминального факта. Анализ каждого правила начинается с проверки необходимости порождения факта, порождаемого этим правилом. Если порождаемый факт уже есть среди фактических знаний, то анализ данного правила прекращается. Если порождаемый факт отсутствует среди имеющихся знаний, то выполняется проверка на возможность его порождения. Для этой цели, последовательно рассматриваются все порождающие факты анализируемого правила. Каждый порождающий факт сравнивается с совокупностью фактических знаний. Если все факты, необходимые для порождения нового факта есть в наличии, то порождается новый факт и строится цепочка логического вывода. Алгоритм прямой цепочки рассуждений, реализованный в среде Delphi, может иметь следующий вид:Procedure TFrmExpert.CmdDirectClick(Sender: TObject);
{ПРЯМАЯ ЦЕПОЧКА ЛОГИЧЕСКОГО ВЫВОДА}
Var
KA: Integer; {Ключ возможности порождения нового факта}
KEnd: Integer; {ключ нормального завершения}
KIZ: Integer; {Ключ обнаружения зацикливания}
I,J,K,L: Integer; {Рабочие переменные}
Begin
With Baseknow Do
Begin
KEnd:= 0;
KIZ:= 0;
NS:=0;
While (KEnd=0) And (KIZ=0) Do
Begin
{ Организация обработки базы знаний до тех пор, пока
не будет порожден заданный целевой(терминальный) факт
или не станет ясна невозможность его получения}
KIZ:=1; {Если ключ не изменится, то выполнится
выход из цикла из-за обнаружения зацикливания}
I:= 1;
While (I<=NR) And (KEND=0) Do
Begin
{Просмотр всех правил до порождения целевого факта}
KA:= 0;
{Проверка: нужно ли порождать факт?}
K:= 1;
While (KA=0) And (K<=NF) Do
Begin
If Rule[I].FactOut=Fact[K] THEN
KA:= 1; {Факт входит в состав имеющихся}
K:= K+1;
End;
{Проверка: можно ли породить факт?}
J:= 1;
While(J<=Rule[I].Quant) And (KA =0) Do
Begin
{Анализ порождающих фактов}
KA:= 1; K:= 1;
While (K<=NF) And (KA=1) Do
Begin
{Проверка наличия порождающего факта}
If Rule[I].FactIn[J]=Fact[K] Then
KA:= 0; {Факт найден}
K:= K+1;
End; {While K}
{Если при выходе из цикла KA = 1, то в базе знаний
нет факта необходимого для порождения}
J:= J+1;
End; {While J}
If KA =0 then
Begin
{Все факты, необходимые для порождения
нового факта есть в наличии}
NF:= NF+1; {Порождение нового факта}
Fact[NF]:=Rule[I].FactOut;
{Засылка нового факта в цепочку логического вывода}
NS:=NS+1;
Spis[NS]:= Rule[I].FactOut;
{Если необходимо формировать цепочку логического
вывода из номеров правил, то используется
оператор вида
Spis[Ns]:=I;}
KIZ:= 0;
{Проверка: Является ли порожденый факт целевым?}
For L :=1 To NT Do
If Rule[I].FactOut=TermFact[L] Then KEnd:= 1;
End; {If KA=0}
I:= I+1;
End; {While I And KEnd}
End; {While KEnd And KIZ}
If KEnd=1 Then
{Выдача результата}
Begin
LblRez.Caption:= ‘Цепочка логического вывода’;
LblRez.Visible:= True;
GridRez.RowCount:= NS+1;
For I:=1 To NS Do
GridRez.Cells[0,I]:=IntToStr(Spis[I]);
GridRez.Visible:=True;
End
Else
Begin
{выдача сообщения о невозможности порождения}
LblRez.Caption:= ‘Терминальный факт породить не удалось’;
LblRez.Visible:= True;
End;
End; {With}
End;
Прямая цепочка рассуждений достаточно просто позволяет вывести необходимые знания при ограниченном количестве процедурных правил. В реальной базе знаний количество правил исчисляется тысячами или десятками тысяч. В этом случае, при нахождении требуемых знаний, выполняется большое число правил, порождающих избыточные знания. Поэтому, если целью цепочки рассуждений является порождение какого-либо определенного знания, то более эффективной может оказаться обратная цепочка рассуждений. Обратная цепочка рассуждений предполагает выполнение только тех правил, которые относятся к установлению заданного факта. При обратной цепочке рассуждений в правилах анализируются порождаемые факты и отбираются те правила, которые необходимы для получения требуемых знаний. После включения правила в обратную цепочку рассуждений определяются знания, которые необходимы для его выполнения. В дальнейшем определяются правила, которые необходимы для получения требуемых знаний. Алгоритм построения обратной цепочки можно разделить на два этапа. Первый этап, накопление требований к правилам и знаниям. Второй этап, реализация накопленных требований. Пример обратной цепочки рассуждений. Имеется база знаний.Правила Факты ( Процедурные (Начальные знания) знания)
F & I -> A C , D
C & I -> Z
B & C -> E
D -> F
F & C -> I
D & I -> B
Необходимо породить знание “Z“. Машина логического вывода, действуя в соответствии с обратной цепочкой рассуждений, просмотрит все правила базы знаний и выберет правило, порождающее факт “Z”. Правилом, порождающим факт “Z “ является правило “C&I®Z“. Для применения этого правила требуется наличие данных “С,I“. Знание “С“ является начальным, а знание “I“ требуется породить. Следовательно, требуется найти правило, которое породит знание “I“. Таким правилом является правило “F&C->I“. Для применения данного правила не хватает знания “F“. Поэтому, ищется правило, которое должно породить знание “F“. Просмотр базы знаний позволяет выявить требуемое правило, а именно “D->F“. Знание “D” является начальным и на этом первый этап обратной цепочки рассуждений завершается. На втором этапе, отобранные правила располагаются в порядке, позволяющем порождать новые знания на основе имеющихся фактов. Для этого отобранные правила переписываются в обратном порядке. Цепочка применяемых правил при использовании обратной цепочки рассуждений будет выглядеть :D — > F
F & C -> I
C & I — > Z
Цепочка порождаемых фактов будет иметь вид: F ,I, Z . Реализованный в системе Delphi алгоритм обратной цепочки рассуждений представлен в виде метода с именем TFrmExpert.CmdInvClick Алгоритм предусматривает использование массива «STACK», имеющего стековую организацию памяти. При работе с массивом STACK в первую очередь будет обрабатываться элемент, который был заслан последним. Первоначально в STACK засылается терминальный факт. Предусматривается поочередная засылка в STACK терминальных фактов, до тех пор, пока, либо не будет построена цепочка логического вывода, либо не будут рассмотрены все терминальные факты. После засылки терминального факта в массив STACK осуществляется циклический анализ стека. В процессе анализа в стек будут как засылаться факты, так и выбираться для анализа. Факт выбранный для анализа пересылается из стека в переменную ANFACT. Анализируемый факт проверяется на возможность порождения. Если существует правило, которое порождает анализируемый факт, то проверяется наличие порождающих фактов. Если какого-либо порождающего факта нет в наличии, то он засылается в массив STACK для анализа. Если не существует правило, которое порождает анализируемый факт, то полагается, что анализируемый факт породить невозможно. В этом случае, цепочка вывода прерывается. При выполнении второго этапа, в том случае, если удается построить цепочку логического вывода, то она преобразуется. В процессе преобразования последние элементы становятся первыми и наоборот. Алгоритм обратной цепочки рассуждений, реализованный в среде Delphi, может иметь следующий вид:Procedure TFrmExpert.CmdInvClick(Sender: TObject);
{ОБРАТНАЯ ЦЕПОЧКА ЛОГИЧЕСКОГО ВЫВОДА}
Var
KEnd: Integer; {Ключ нормального завершения}
KVPF: Integer; {Ключ возможности порождения факта}
KVPC: Integer; {Ключ возможности порождения цепочки}
AnFact: Integer; {Анализируемый факт}
KA: Integer; {Ключ наличия порождающего факта}
Stack: Array [1..20] Of Integer; {Стек порождаемых фактов}
NST: Integer; {Текущий индекс стека}
I,J,K,L,RAB,NS1: Integer; {Рабочие переменные}
Begin
With BaseKnow Do
Begin
KEnd:= 0;
L:= 1;
While (L<=NT) And (KEnd=0)Do
Begin
{Организация просмотра всех целевых фактов
до тех пор, пока не подтвердится возможность
порождения какого-либо из них}
NS:= 0;
NST:= 1;
Stack[1]:= TermFact[L];
KVPC:= 1;
While (NST>0) And (KVPC=1) Do
Begin
{Анализ содержимого стека на возможность
порождения фактов}
KVPF:= 0;
AnFact:= Stack[NST];{Выбор факта для анализа}
NST:= NST-1;
NS:= NS+1;
Spis[NS]:= AnFact;{Занесение анализируемого факта
в список фактов}
I:= 1;
While (I<=NR) And (KVPF=0) Do
Begin
{Анализ возможности порождения выбранного факта}
If AnFact=Rule[I].FactOut Then
Begin
{Требуемый факт является порождаемым}
KVPF:= 1;
{Если необходимо формировать цепочку
логического вывода из номеров правил,
то задается следующий набор операторов
NS:= NS +1;
SPIS[NS]:= I; }
For J:= 1 To RULE[I].QUANT Do
Begin
{Проверка наличия порождающих фактов}
KA:= 0;
K:= 1;
While (K<=NF) And (KA=0) Do
Begin
If Rule[I].FactIn[J]=Fact[K] Then
KA:=1;
K:= K+1;
End;
If KA=0 Then
Begin
{Порождающего факта нет среди имеющихся.
Его необходимо породить}
NST:= NST+1;
Stack[NST]:= Rule[I].FactIn[J];
End; {If}
End; {For J}
End; {If}
I:= I+1;
End; {While I}
If KVPF=0 Then
KVPC := 0 ;
{Требуемый факт породить невозможно.
Цепочка не может быть построена.}
End; {While NST}
If KVPC=1 Then
{Найдена цепочка, которую можно построить
Анализируемый целевой(терминальный) факт
возможно породить}
Begin
KEnd:= 1;
{Преобразование порождающей цепочки}
NS1:= NS div 2;
For K:= 1 To NS1 Do
Begin
RAB:= Spis[K];
Spis[K]:= Spis[NS-K+1];
Spis[NS-K+1]:= RAB;
End; {For}
{Выдача результата}
LblRez.Caption:= ‘Цепочка логического вывода’;
LblRez.Visible:= True;
GridRez.RowCount:= NS+1;
For I:=1 To NS Do
GridRez.Cells[0,I]:=IntToStr(Spis[I]);
GridRez.Visible:=True;
End;{If}
L:= L+1;
End;{While L}
If KEND=0 Then
Begin
{Ни один из целевых фактов не может быть порожден.
Выдача сообщения о невозможности порождения}
LblRez.Caption:= ‘Терминальный факт породить не удалось’;
LblRez.Visible:= True;
End;
End;{With}
End;