Статья 'Перечисление решающих деревьев ограниченной стоимости на И-ИЛИ дереве' - журнал 'Программные системы и вычислительные методы' - 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.2014.2.11925

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

22-07-2014


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

05-08-2014


Аннотация: Рассматриваются И-ИЛИ деревья с заданной стоимостью дуг либо вершин, широко применяемые в системах искусственного интеллекта. Описывается алгоритм типа ветвей и границ, позволяющий перечислить все решающие деревья, стоимость которых не превышает наперед заданной константы. Трудоемкость получения очередного решающего дерева составляет O(N), где N – количество вершин И-ИЛИ дерева. Указывается способ стековой организации информации, позволяющий свести затраты памяти к величине O(N) без изменения прежней оценки трудоемкости. Выполнена программная реализация описанного алгоритма, подтвердившая при тестировании полученные теоретические оценки трудоемкости и объема необходимой памяти. Эффективность поиска повышена благодаря введенному понятию минимальной оболочки И-ИЛИ дерева по ограничению стоимости, что позволяет гарантировать наличие допустимых решающих деревьев при спуске по дереву решений. Решающие поддеревья перечисляются не по отдельности, а блоками в виде поддеревьев И-ИЛИ дерева, в которых все варианты допустимы.


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

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

УДК:

004.89:519.172

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

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


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