Thumbnail
Access Restriction
Subscribed

Author Montanari, Ugo ♦ Martelli, Alberto
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Branch-and-bound ♦ And/or graphs ♦ Optimal decision table conversion ♦ Dynamic programming ♦ Heuristic search ♦ Decision tree ♦ Decision table
Abstract 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, quasioptimal 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 quasioptimal 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.
Description Affiliation: Consiglio Nazionale delle Ricerche, Pisa, Italy (Martelli, Alberto) || Univ. di Pisa, Pisa, Italy (Montanari, Ugo)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 12
Page Count 15
Starting Page 1025
Ending Page 1039


Open content in new tab

   Open content in new tab
Source: ACM Digital Library