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

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

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


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

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

Abstract: the article reviews AND-OR trees with defined cost of arcs or vertices, widely used in artificial intelligence systems. The author describes branch and bound algorithm allowing enumerating all decision trees with cost less or equaling to defined constant value. The complexity of producing another decision tree is O(N), where N is the number of vertices of the AND-OR tree. The article shows a way to use stack for information organization, reducing the memory consumption to O(N) without changing the previous complexity estimate. The article presents software realization of the described algorithm, proving the theoretical evaluation of complexity and amount of the required memory in tests. The effectiveness of search is increased by introduction of the concept of a minimal AND-OR tree cost-constraint subset, which ensures the existence of valid decision trees while descending the decision tree. The decision subtrees are not listed separately but organized in blocs of AND-OR subtress in which all options are possible.


Keywords:

artificial intelligence, algorithm, enumeration, AND-OR graph, AND-OR tree, decision tree, AND-OR tree version, cost, cost constraint


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

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

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

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


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