
	Software systems and computational methods Reference: Galochkin V.I. Enumeration of cost-constraint based decision trees on AND-OR tree // Software systems and computational methods. 2014. № 2. P. 191-196. URL: https://en.nbpublish.com/library_read_article.php?id=65262 Galochkin V.I. Enumeration of cost-constraint based decision trees on AND-OR tree 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 This article can be downloaded freely in PDF format for reading. Download article This article written in Russian. You can find original text of the article here . 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

Journals

Books

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