PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Martelli A., Montanari U. Optimizing decision trees through heuristically guided search. Internal note IEI-B76-22, 1976.
 
 
Abstract
(English)
Optional decision table conversion has been attached in the literature using two approaches, dynamic programming and branch and bound. The former technique is quite effective, but its time and space requirements are indipendent of how "easy" is the given table. Furthermore it cannot be used to produce good, suboptimal solutions. The branch and bound technique uses a good heuristic to direct the search, but is clobbered by an enormous search space, since the number of solutions increases with the number of test variables according to a double exponential. In this paper we suggest an heuristically guided, top-down, search algorithm which recognises identical subproblems and which can be used to find both optimal and suboptimal solutions, thus joining the positive aspects of the above techniques. Compressed tables with a large number of variables can be handled without deriving extended tables first.
Subject


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional