ЕСТЬ ЕСТЬПодача модуль 0.3-0.35 Ü;2-3 И ЕСТЬ характер обработки по сплошному металлу ЕСТЬ обрабатываемый материал чугун ЕСТЬ 1 модуль 2-3
ЕСТЬ Подача 0.22-0.25 Ü; И ЕСТЬ характер обработки по предварительно обработанному зубу ЕСТЬ обрабатываемый материал сталь 45 ЕСТЬ ЕСТЬ модуль Подача 4- 8 0.35 Ü; И ЕСТЬ характер обработки по предварительно обработанному зубу ЕСТЬ обрабатываемый материал чугун ЕСТЬ модуль 4- 8
Рис. 21. Пример представления таблицы с условиями
Множество таких таблиц образует сеть, обработку которых можно выполнить на основе алгоритма обратного вывода, который рассматривался, как алгоритм обхода сети (см. рис. 13). Поэтому приведём здесь несколько изменённый алгоритм вывода и рассмотрим процедуру обработки узла, которая и составляет оператор 10, упомянутый в комментариях к рис. 13 (рис. 22, рис. 23).
1. Установить вершину начала обхода
2. Dimension Stk(255), Stv(255), Stt(255), Zakl=’’, Uk=0
3. Установить направле- ние обхода NO=.T.
4. Начало цикла. i = 0
5. нет NO =.T.?
да
6.(Uk = uk+1) Занести ключ узла в Stk(uk).Тип вершины в Stt(uk)
7.Есть нет указатель на левое 10. Обработать узел 11.Установить нап поддерево? P = OUDV() обхода NO=.T.
да 8. (i=i+1) Занести в стэк 13. Перейти на правое да 12. узлов указатель на поддерево NPPP() =.T. текущий узел
нет 9.Перейти на левое 15. Перейти 14.Установить поддерево по указателю направление стека узлов обхода.F.
16. Удалить из стэка узлов головную вершину (i = i-1) 17.Окончание цикла 5 (i = 0)
конец
Рис. 22. Алгоритм обратного вывода
да 2. Stt(lUk)= “C”
нет нет 5. lUk=Uk да 4. Stt(lUk)=”V” да
нет
7. Stt(lUk)=”L” да
нет
да 10. Stt(lUk)=”P”
нет
да нет 13. Stt(lUk)=”I” 14. Stk(Uk) =True
нет да
Выход
Рис. 23. Aлгоритм обработки узла дерева вывода OUDV()
Комментарии к алгоритму, изображённому на рис. 22. Оператор 1. Установление вершины начала обхода. В качестве начала обхода может быть принята любая вершина сети. Начало может быть установлено путем передачи в программу номера записи, с которой начинается обход. Оператор 2. Инициализируются массивы, выполняющие роль стеков имен вершин и ключей вершин, т.е. ассоциированных с вершинами данных. Кроме того инициализируются целые переменные, выполняющие роли указателей вершин стеков. Оператор 3. Установить направление обхода True Предполагается инициализация логической переменной, которой присваивается значение.T. и которое указывает на направление обхода от корня к листьям. Оператор 4. Начало цикла. (Имеется в виду команда DO WHILE.T. xBASE) Оператор 6. Занести ключ вершины в строку ключей. Это действие выполняет роль процедуры обработки узла дерева при прямом обходе. При выполнении данного оператора выбирается из базы данных ассоциированное с вершиной данное, которое может иметь различную семантику: · быть заключением, для импликативной вершины; · быть знаком логической операции или именем предиката для предикативной вершины; · быть именем переменной, в которую запрашивается ввод внешнего аргумента для терминальной вершины; · быть константой, т.е. некоторым данным из базы данных, выполняющим роль образца для сравнения. Для упрощения анализа примем, что эта информация содержится непосредственно в поле CHTO. Оператор 7. Есть указатель на левое поддерево? Означает проверку возможности перехода к вершине-сыну по отношению к текущей вершине. Оператор 8. Занести в СТЭК вершин указатель на текущую вершину. Означает, что необходимо увеличить указатель головы стека на 1 и занести номер записи текущей вершины в массив, выполняющий роль стека. Оператор 9. Перейти на левое поддерево. Означает переход на запись, соответствующую вершине-сыну относительно текущей вершины. Оператор 10. Обработать вершину. Обработка вершины выполняется при уходе из нее и состоит в анализе данных, накопленных к данному моменту в стеке ключей и выполнении над ними определенных действий, результат которых будет соответствовать процессу логического вывода над базой правил. Алгоритм реализуется в виде функции пользователя. FUNCTION OUDV() (рис. 23). Оператор 11. Установить направление обхода Тrue. Т.е. восстановить первоначальное направление обхода. Оператор 12. NPPP() =.T. Означает проверку возможности и Необходимости Перехода на Правое Поддерево. Реализуется функцией пользователя NPPP(), которая возвращает True или False соответственно. Возможность перехода определяется непустым указателем на правое поддерево, а необходимость - следующими условиями: если голова стека ключей содержит знак дизъюнкции и индикатор истинности вывода содержит False или голова стека ключей содержит любой другой символ и индикатор истинности вывода содержит True. Оператор 13. Перейти на правое поддерево. Означает переход на запись, соответствующую вершине-брату относительно текущей вершины. Здесь следует напомнить, что речь идет о двоичном представлении произвольного дерева. В таком представлении на общепринятом жаргоне может идти речь о вершине-отце, вершине-сыне и вершине-брате. Других вершин в двоичном представлении нет. Оператор 14. Установить направление обхода False. Изменяет первоначальное направление обхода на обратное. Оператор 15. Перейти по указателю СТЭКА вершин. Это действие означает чтение головы стека вершин и перехода по выбранному из него указателю на вершину - отец относительно текущей вершины. Оператор 16. Удалить из СТЭКА вершин головную вершину. Означает просто уменьшение указателя СТЭКА вершин на 1. Оператор 17. Окончание цикла соответствующее команде ENDDO (xBase, Visual Basic). Комментарии к алгоритму обработки узла дерева вывода (рис. 23). Оператор 1. Инициализируется локальный указатель стека ключей, принимая значение внешнего указателя головы стека. Инициализируется указатель арности предиката или логической операции. Оператор 2. Анализируется голова стека типов вершин. Если тип вершины есть константа, то осуществляется переход на оператор 3, где уменьшается на единицу локальный указатель стека. Оператор 4. Если тип вершины есть переменная, и значение локального указателя головы стека не изменялось, т.е. имя переменной находится в голове стека, то происходит переход на оператор 6, где запрашивается ввод соответствующего значения или последнее выбирается из дескрипторной или классификационной компоненты системы. Полученное значение замещает имя переменной в стеке ключей. Соответственно замещается и значение типа в стеке типов вершин. Оператор 7. Если тип вершины есть логическая операция NOT, OR или AND то в операторе 8 определяется число аргументов, над которыми следует выполнить эту операцию. Затем в операторе 9 выполняется соответствующая логическая операция над n аргументами из стека ключей, расположенными справа от локального указателя. Результат операции заносится в стек ключей по месту локального указателя. Также производится и соответствующая замена в стеке типов. Оператор 10. Если тип вершины есть предикат, в частности, одна из операций сравнения: =, >, >=, <, <=, IN, LIKE, а также “следует”, “предшествует”, “находится в интервале” и т.п., то в операторе 11 определяется число аргументов этого предиката. Они находятся в стеке в виде результатов предшествующей обработки. После чего в операторе 12 выполняется обработка соответствующего предиката. Результат операции заносится по месту локального указателя стека. Также производится и соответствующая замена в стеке типов. Оператор 13. Если тип элемента по месту локального указателя есть импликация, то в операторе 14 проверяется значение элемента, находящегося непосредственно правее анализируемого в стеке ключей. Если последний представляет собой логическую константу False, то проводится упреждающая (с учетом оператора 19) корректировка переменной n. После чего в операторе 16 результат импликации замещается в стеке логической константой False. Оператор 17. Формируется заключение, как результат доказательства на основе вывода, выполненного путём обхода всего поддерева с корнем в текущем узле. Оператор 18. Выполняет соответствующую корректировку стека типов и затем оператор 19 корректирует внешний указатель головы стека ключей. Анализ только что приведённых комментариев удобно проводить на примере сети, представляющей информационно-логическую таблицу и изображённой на рис 2.20. В результате совместной работы алгоритмов обратного вывода и обработки узла состояние стека будет изменяться следующим образом.
False False
По сплошному металлу
2-3 True True True True Zakl= “подача есть 0.3-0.35” В случае введения понятия “факт” можно значительно упростить дерево вывода (рис. 24). Таблица подач при чистовой обработке на зубодолбежных станках
ИЛИ ЕСТЬ Подача И ЕСТЬ характер обработки по сплошному металлу ЕСТЬ обрабатываемый материал сталь 45
|
начало
начало
