Optimizing Decision Trees Through Heuristically Guided Search

Optimal decision table conversion has been
tackled 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 independent of how "easy" the
given table is.  Furthermore, it cannot be used 
to produce good, quasi optimal solutions.  The branch-and-bound
technique uses a good heuristic to direct 
the search, but is cluttered up 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 a heuristically 
guided top-down search algorithm which, like dynamic
programming, recognizes identical subproblems but 
which can be used to find both optimal and quasi optimal
solutions.  The heuristic search method introduced 
in this paper combines the positive aspects of the above
two techniques.  Compressed tables with a large 
number of variables can be handled without deriving expanded tables first. 

CACM December, 1978

Martelli, A.
Montanari, U.

Decision table, optimal decision table conversion,
decision tree, heuristic search, AND/OR graphs, 
dynamic programming, branch-and-bound

3.59 3.66 5.42 8.3

CA781206 DH January 18, 1979  3:56 PM

3033	4	3033
3113	4	3033
2856	5	3033
3033	5	3033
3033	5	3033
3033	5	3033