By Alberto Martelli, Ugo Montanari
Communications of the ACM,
December 1978,
Vol. 21 No. 12, Pages 1025-1039
10.1145/359657.359664
Comments
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.
The full text of this article is premium content
No entries found
Log in to Read the Full Article
Need Access?
Please select one of the options below for access to premium content and features.
Create a Web Account
If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.
Join the ACM
Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
Subscribe to Communications of the ACM Magazine
Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.
Purchase the Article
Non-members can purchase this article or a copy of the magazine in which it appears.
