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

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

Галочкин Владимир Иванович

кандидат технических наук

доцент, кафедра информатики и системного программирования, Поволжский государственный технологический институт

424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пр. Ленина, 3

Galochkin Vladimir Ivanovich

PhD in Technical Science

Associate Professor, Department of Computer Science and System Programming, Volga State Technological Institute

424000, Russia, respublika Marii El, g. Ioshkar-Ola, ul. Pr. Lenina, 3

vigaloch@mail.ru
Другие публикации этого автора
 

 

DOI:

10.7256/2454-0714.2016.4.20851

Дата направления статьи в редакцию:

25-10-2016


Дата публикации:

15-01-2017


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


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

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

УДК:

004.89:519.172

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:

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

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

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


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