14. Вывод на И - ИЛИ графе
Имеется множество исходных гипотез Г1, Г2, ... Отмечаются истинные гипотезы Гi - метками TRUE(Гi). Остальные (они могут быть ложными или о них ничего неизвестно) никак не отмечаются. Дается И-ИЛИ граф, которое связывает гипотезы. При этом гипотезы образуют вершины И-ИЛИ графа. Далее, различаются узлы типа И и типа ИЛИ.
Узел типа И представляется AND(Г1,Г11) AND(Г2,Г11) ... , что означает: гипотеза Г11 истинна, если истинны все гипотезы Г1, Г2,... Будем говорить, что гипотезы Г1, Г2, ... являются входными для узла типа И, а Г11 - результирующей.
Узел типа ИЛИ представляется OR(Г5,Г12) OR(Г6,Г12) ... , что означает: гипотеза Г12 истинна, если истинна хотя бы одна из гипотез Г5, Г6,... Будем говорить, что гипотезы Г5, Г6, ... являются входными для узла типа ИЛИ, а Г12 - результирующей.
Требуется: на основе отмеченных гипотез найти все истинные гипотезы.
Пример 14.1. Пример И-ИЛИ графа - сведения о болезнях.
AND("Плохое самочувствие",Б1)
AND("Болит горло",Б1)
AND("Насморк",Б2)
AND("Болит горло",Б2)
OR(Б1,"Человек болен")
OR(Б2,"Человек болен")
Данный И-ИЛИ граф означает, что человек болен, если у него плохое самочувствие и болит горло, или же если у него насморк и болит горло. В первых экспертных системах пробовали использовать И-ИЛИ графы для принятия решений. Однако, такие графа оказывались черезчур громоздкими. Их трудно строить - нужно предусмотреть все варианты. Здесь нет обобщающих правил. Поэтому стали строить оболочки для экспертных систем.
14.1. Реализация вывода на продукциях:
BEG(/91+)
START:IF THEN
T:US1() {= перевешивает метки TRUE(Гi) с одних гипотез на другие =}
B:HALT();
{== Переход по узлам типа ИЛИ ==}
US1():IF TRUE(X1) OR(X1,X2) N:TRUE(X2) THEN TRUE(X2);
{== Переход по узлам типа И ==}
US1():IF TRUE(X1) AND(X1,X2) N:[AND(X3,X2) N:TRUE(X3)]
N:TRUE(X2) THEN TRUE(X2);
END(/92+) @BL(91-,92-)
Первая продукция US1 перевешивает фрагменты (метки) TRUE(Гi) в соответствии с правилом: результирующая гипотеза X2=Гi узла типа ИЛИ истинна, если истинна X1=Гj, которая является входной для узла OR(Гj,Гi).
Вторая продукция US1 перевешивает метки TRUE(Гi) в соответствии с правилом: результирующая гипотеза X2=Гi узла типа И истинна, если истинны все гипотезы X3=Гj, которые являются входными для узла AND(Гj,Гi). Вначале перебираются истинные гипотезы X1=Гj, связанные с узлом типа AND(X1,X2). Далее анализируется гипотеза X2=Гi, чтоб в узле "не было такой входной гипотезы, которая не была бы отмечена как истинная". Тогда гипотеза Гi объявляется истинной - TRUE(Гi).
Пример 14.2. Пусть дополнительно к примеру 14.1 отмечены истинные гипотезы - в БЗ помещены фрагменты (параметры, определяющие исходное состояние больного):
TRUE("Болит горло")
TRUE("Насморк")
Тогда первая продукция US1 вначале не сработает, так как нет входных истинных гипотез (это Б1 и Б2) для узлов типа ИЛИ.
У второй продукция US1 будет означено X1="Болит горло" и выбран первый узел типа И - AND("Болит горло",Б1). По AND("Плохое самочувствие",Б1) будет проверяться наличие в БЗ метки TRUE("Плохое самочувствие"). Так как ее нет, то выбирается AND("Болит горло",Б2) и проверяться наличие TRUE("Насморк"). Такая метка есть в БЗ, в связи с чем к БЗ добавляется TRUE(Б2). Других вариантов применения второй продукции US1() нет. Но так как она была применима и вызывалась T:US1(), то снова делается попытка ее применения - вначале первой продукции. Она применима для случая X1=Б2. Будет сформирована - TRUE("Человек болен").
Предыдущий раздел|Следующий раздел