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