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


	Программные системы и вычислительные методы Правильная ссылка на статью: Галочкин В.И. Перечисление решающих деревьев ограниченной стоимости на И-ИЛИ дереве // Программные системы и вычислительные методы. 2014. № 2. С. 191-196. URL: https://nbpublish.com/library_read_article.php?id=65262 Галочкин В.И. Перечисление решающих деревьев ограниченной стоимости на И-ИЛИ дереве Аннотация: Рассматриваются И-ИЛИ деревья с заданной стоимостью дуг либо вершин, широко применяемые в системах искусственного интеллекта. Описывается алгоритм типа ветвей и границ, позволяющий перечислить все решающие деревья, стоимость которых не превышает наперед заданной константы. Трудоемкость получения очередного решающего дерева составляет 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. Нильсон, Н. Искусственный интеллект. Методы поиска решений / Н. Нильсон. – М.: Мир, 1973. – 270 c. 2. Автоматизация поискового конструирования / А. И. Половинкин, Н. К. Бобков, Г. Я. Буш и др. Под редакцией А. И. Половинкина. – М.: Радио и связь, 1981. –344 с. 3. Братко, И. Программирование на языке Пролог для искусственного интеллекта / И. Братко – М.: Мир, 1990. – 560 с. 4. Кручинин, В.В. Методы построения алгоритмов генерации и нумерации комбинаторных объектов на основе деревьев И/ИЛИ / В.В. Кручинин. – Томск: В-Спектр, 2007. – 200 с. 5. Рейнгольд, Э. Н. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М.: Мир, 1980. – 476 с References 1. Nil'son, N. Iskusstvennyy intellekt. Metody poiska resheniy / N. Nil'son. – M.: Mir, 1973. – 270 c. 2. Avtomatizatsiya poiskovogo konstruirovaniya / A. I. Polovinkin, N. K. Bobkov, G. Ya. Bush i dr. Pod redaktsiey A. I. Polovinkina. – M.: Radio i svyaz', 1981. –344 s. 3. Bratko, I. Programmirovanie na yazyke Prolog dlya iskusstvennogo intellekta / I. Bratko – M.: Mir, 1990. – 560 s. 4. Kruchinin, V.V. Metody postroeniya algoritmov generatsii i numeratsii kombinatornykh ob'ektov na osnove derev'ev I/ILI / V.V. Kruchinin. – Tomsk: V-Spektr, 2007. – 200 s. 5. Reyngol'd, E. N. Kombinatornye algoritmy. Teoriya i praktika / E. Reyngol'd, Yu. Nivergel't, N. Deo. – M.: Mir, 1980. – 476 s

Журналы

Книги

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