Eng During last 365 days Approved articles: 1919,   Articles in work: 328 Declined articles: 648 
Library

Galochkin V.I. Enumeration of cost-constraint based decision trees on AND-OR tree

Published in journal "Software systems and computational methods", 2014-2 in rubric "Knowledge Base, Intelligent Systems, Expert Systems, Decision Support Systems", pages 191-196.

Resume: 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

DOI: 10.7256/2305-6061.2014.2.11925

This article can be downloaded freely in PDF format for reading. Download article

Bibliography:
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.

Correct link to this article:
just copy this link to clipboard