Статья 'Перечисление решающих деревьев на И-ИЛИ дереве по монотонным ограничениям ' - журнал 'Программные системы и вычислительные методы' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > Требования к статьям > Политика издания > Редакция > Порядок рецензирования статей > Редакционный совет > Ретракция статей > Этические принципы > О журнале > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала
ГЛАВНАЯ > Вернуться к содержанию
Программные системы и вычислительные методы
Правильная ссылка на статью:

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

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


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

Системы искусственного интеллекта, Алгоритм, Перечисление, И-ИЛИ граф, И-ИЛИ дерево, Решающее дерево, Система неравенств, Система ограничений, Монотонная функция, Сложность алгоритма

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:

system of constraints, system of inequalities, decision tree, AND-OR tree, AND-OR graph, enumeration, algorithm, artificial intelligence systems, monotonic function, complexity of algorithm


Эта статья может быть бесплатно загружена в формате PDF для чтения. Обращаем ваше внимание на необходимость соблюдения авторских прав, указания библиографической ссылки на статью при цитировании.

Скачать статью

Библиография
1.
2.
3.
4.
5.
6.
7.
8.
References
1.
2.
3.
4.
5.
6.
7.
8.
Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.