Alberto Martelli
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.
- 1 Bayes, A.J. A dynamic programming algorithm to optimize decision table code, Australian Comptr. J. 5, 2 (May 1973), 77-79.Google Scholar
- 2 Bellman, R., and Dreyfus, S. Applied Dynamic Programming. Princeton U. Press, Princeton, N.J., 1962.Google Scholar
- 3 Dijkstra, E. A note on two problems in connection with graphs. Numer. Math. 1 (1959), 269-271.Google ScholarDigital Library
- 4 Lawler, E., and Wood, D. Branch and bound methods: A survey. Oper. Res. 14, 4 (July-Aug. 1966), 699-719.Google Scholar
- 5 Martelli, A. On the complexity of admissible search algorithms. Artif. lntell. 8 (1977), 1-13.Google Scholar
- 6 McCluskey, E.J. Introduction to the Theory of Switching Circuits. McGraw-Hill, New York, 1965.Google Scholar
- 7 Martelli, A., and Montanari, U. On the foundations of dynamic programming. In Topics in Combinatorial Optimization, S. Rinaldi, Ed., Springer-Verlag, 1975, pp. 145-163.Google Scholar
- 8 Martelli, A., and Montanari, U. Programmazione dinamica e punto fisso. Atti Convegno di Informatica Teorica, Mantova, Nov. 1974, pp. 1-19 (in Italian).Google Scholar
- 9 Martelli, A., and Montanari, U. From dynamic programming to search algorithms with functional costs, Proc. Fourth Int. Joint Conf. Artif. Intell. Tbilisi, Sept. 1975, pp. 345-350.Google Scholar
- 10 Martelli, A., and Montanari, U. Additive AND/OR graphs. Proc. Third Int. Joint Conf. Artif. Intell., Stanford, Calif., Aug. 1973, pp. 1-11.Google Scholar
- 11 Montanari, U. Heuristically guided search and chromosome matching. Artific. Intell. 1, 4 (1970), 227-245.Google ScholarCross Ref
- 12 Nilsson, N.J. Problem Solving Methods in Artificial Intelligence, McGraw-Hill, New York, 1971. Google ScholarDigital Library
- 13 Nilsson, N. Searching problem-solving and game-playing trees for minimal cost solutions. Information Processing 68, Vol. 2, North- Holland Pub. Co., 1968, pp. 1556-1562.Google Scholar
- 14 Pooch, U.W. Translation of decision tables. A CM Computing Surveys 6, 2 (June 1974), 125-151. Google ScholarDigital Library
- 15 Reinwald, L.T., and Soland, R.M. Conversion of limited-entry decision tables to optimal computer programs I: Minimum average processing time. J. ACM 13, 3 (July 1966), 339-358. Google ScholarDigital Library
- 16 Schumacher, H., and Sevcik, K.C. The synthetic approach to decision table conversion, Comm. A CM 19, 6 (June 1976), 343-351. Google ScholarDigital Library
Index Terms
- Optimizing decision trees through heuristically guided search
Recommendations
A two-phase intensification tabu search algorithm for the maximum min-sum dispersion problem
AbstractIn this paper, we study the maximum min-sum dispersion problem (Max-Minsum DP for short) which is a classical binary optimization problem proven to be NP-hard and with numerous real-world applications. For solving this computationally ...
Highlights- An intensification solution-based tabu search to reduce the wrong identification of tabu status.
A heterogeneous cooperative parallel search of branch-and-bound method and tabu search algorithm
In this study, we present a heterogeneous cooperative parallel search that integrates branch-and-bound method and tabu search algorithm. These two algorithms perform searches in parallel and cooperate by asynchronously exchanging information about the ...
Anytime pack search
Heuristic search is one of the fundamental problem solving techniques in artificial intelligence, which is used in general to efficiently solve computationally hard problems in various domains, especially in planning and optimization. In this paper, we ...
Comments