Галочкин В.И. Перечисление решающих деревьев на И-ИЛИ дереве по монотонным ограничениям

Аннотация: Рассматриваются широко применяемые в системах искусственного интеллекта И-ИЛИ деревья с заданными значениями показателей в терминальных дугах либо вершинах. Показатели рекурсивно определены на решающих деревьях с помощью непрерывных и монотонных по каждому аргументу функций свертки. Ставится задача перечисления решающих деревьев, удовлетворяющих системе ограничений на показатели. Для случая единственного аддитивного показателя ранее предложен линейный по сложности и памяти алгоритм, но уже для двух показателей не существует полиномиальных алгоритмов решения задачи. Предлагаются два алгоритма типа ветвей и границ. Первый алгоритм реализует последовательное выделение поддеревьев допустимых решений по ограничениям на отдельные показатели. Второй алгоритм позволяет эффективно отсекать недопустимые поддеревья. В основе обоих алгоритмов лежит введенное понятие минимальной оболочки И-ИЛИ дерева по монотонному ограничению. Первый алгоритм более применим при наличии большого числа решений системы неравенств, поскольку позволяет выбирать допустимые варианты не по отдельности, а блоками в виде поддеревьев И-ИЛИ дерева. Второй алгоритм ориентирован на случай, когда система неравенств имеет небольшое число решений.

Ключевые слова:

Abstract: The author reviews widely used in artificial intelligence systems AND-OR trees with specified parameters in the terminal arcs or vertices. The parameters are defined recursively on the decision trees with the use of continuous convolution functions monotone in each argument. The author solves a problem of enumerating convolution functions satisfying the system of restrictions on the parameters. Earlier a linear complexity and memory algorithm for the case of a single additive index was presented. But even for two parameters there is no polynomial-time algorithm for solving the problem. The author suggests two “branch and bound”  algorithms . The first algorithm implements a consistent selection of subtrees for allowable solutions using restrictions on separate parameters. The second algorithm can effectively cut off the unacceptable subtrees. The basis of the both algorithms is the concept of the minimum AND-OR tree subsest on monotonic restriction. The first algorithm is more applicable in the presence of a large number of solutions of the system of inequalities because it allows to choose the solutions as sets of AND-OR tree subtrees. The second algorithm is applicable in a case where the system of inequalities has a small number of solutions.

Keywords: