Введение в экспертные системы
Обход дерева
В самых общих чертах алгоритм выполнения иерархического построения и проверки гипотез (НАТ-алгоритм) может быть представлен следующим образом. Предположим, имеется дерево гипотез, которые могут быть активизированы на основе части имеющихся данных. Активизированные гипотезы предполагают наличие и других данных, помимо тех, что были использованы для их отбора, которыми мы можем располагать или которые можно дополнительно затребовать.
НАТ-алгоритм
(1) Считать исходные данные.
(2) Для каждой исследуемой гипотезы сформировать оценку, которая показывает, какая часть исходных данных учитывается этой гипотезой.
(3) Определить ту гипотезу (узел) л, которая имеет наивысшую оценку.
(4) Если п— терминальный узел, то завершить выполнение алгоритма. В противном случае выделить в пространстве гипотез два подпространства К и L Подпространство К должно содержать дочерние узлы п, а подпространство L — узлы-конкуренты п на том же уровне дерева.
(5) Собрать дополнительные данные, которые можно использовать для анализа гипотез в подпространстве К, и провести оценку гипотез на основе этих дополнительных данных. Пусть k— наивысшая оценка гипотез из К, а l— наивысшая оценка гипотез из L
(6) Если k выше, чем /, то положить п = k. В противном случае положить n = /.
(7) Перейти к п. 4.
