Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

Galochkin V.I. Enumeration of decision trees on the AND-OR tree with monotonous restrictions

Abstract: The author reviews widely used in artificial intelligence systems AND-OR trees with specified parameters in the terminal arcs or vertices. The parameters are defined recursively on the decision trees with the use of continuous convolution functions monotone in each argument. The author solves a problem of enumerating convolution functions satisfying the system of restrictions on the parameters. Earlier a linear complexity and memory algorithm for the case of a single additive index was presented. But even for two parameters there is no polynomial-time algorithm for solving the problem. The author suggests two “branch and bound”  algorithms . The first algorithm implements a consistent selection of subtrees for allowable solutions using restrictions on separate parameters. The second algorithm can effectively cut off the unacceptable subtrees. The basis of the both algorithms is the concept of the minimum AND-OR tree subsest on monotonic restriction. The first algorithm is more applicable in the presence of a large number of solutions of the system of inequalities because it allows to choose the solutions as sets of AND-OR tree subtrees. The second algorithm is applicable in a case where the system of inequalities has a small number of solutions.


Keywords:

system of constraints, system of inequalities, decision tree, AND-OR tree, AND-OR graph, enumeration, algorithm, artificial intelligence systems, monotonic function, complexity of algorithm


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


References
1. Galochkin V. I. Perechislenie reshayushchikh derev'ev ogranichennoy stoimosti na I-ILI dereve // Programmnye sistemy i vychislitel'nye metody. 2014. ¹ 1. S. 191 – 196. DOI: 10.7256/2305-6061.2014.2.11925.
2. Nikolaev S.A. Metod vetvey i granits dlya poiska tekhnicheskikh resheniy. // Avtomatizirovannye podsistemy poiskovogo konstruirovaniya: Mezhvuzovskiy sbornik. Gor'kiy: GGU, 1981. S. 139-144.
3. Kormen T. Kh. Algoritmy: postroenie i analiz, 2-e izd.: Per. s angl. / T. Kormen Ch. Layzerson, R. Rivest, K. Shtayn. M.: Izdatel'skiy dom ”Vil'yams”, 2005. 1296 s.
4. Reyngol'd, E. N. Kombinatornye algoritmy. Teoriya i praktika / E. Reyngol'd, Yu. Nivergel't N. Deo. M.: Mir, 1980. 476 s.
5. 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.
6. Bratko, I. Programmirovanie na yazyke Prolog dlya iskusstvennogo intellekta / I. Bratko. M.: Mir, 1990. 560 s.
7. Nil'son N. Iskusstvennyy intellekt. Metody poiska resheniy / N. Nil'son. M.: Mir, 1973. 270 s.
8. Avtomatizatsiya poiskovogo konstruirovaniya / A.I. Polovinkin, N.K. Bobkov, G.Ya. Bush i dr. Pod red. A.I. Polovinkina. M.: Radio i svyaz', 1981. 344 s.