|
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Bayes, A.J. A dynamic programming algorithm to optimize decision table code, Australian Comptr. J. 5, 2 (May 1973), 77-79.
|
| |
2
|
Bellman, R., and Dreyfus, S. Applied Dynamic Programming. Princeton U. Press, Princeton, N.J., 1962.
|
| |
3
|
Dijkstra, E. A note on two problems in connection with graphs. Numer. Math. 1 (1959), 269-271.
|
| |
4
|
Lawler, E., and Wood, D. Branch and bound methods: A survey. Oper. Res. 14, 4 (July-Aug. 1966), 699-719.
|
| |
5
|
Martelli, A. On the complexity of admissible search algorithms. Artif. lntell. 8 (1977), 1-13.
|
| |
6
|
McCluskey, E.J. Introduction to the Theory of Switching Circuits. McGraw-Hill, New York, 1965.
|
| |
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.
|
| |
8
|
Martelli, A., and Montanari, U. Programmazione dinamica e punto fisso. Atti Convegno di Informatica Teorica, Mantova, Nov. 1974, pp. 1-19 (in Italian).
|
| |
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.
|
| |
10
|
Martelli, A., and Montanari, U. Additive AND/OR graphs. Proc. Third Int. Joint Conf. Artif. Intell., Stanford, Calif., Aug. 1973, pp. 1-11.
|
| |
11
|
Montanari, U. Heuristically guided search and chromosome matching. Artific. Intell. 1, 4 (1970), 227-245.
|
| |
12
|
|
| |
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.
|
 |
14
|
|
| |
15
|
|
| |
16
|
|
CITED BY 22
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Teruaki Aizawa , Terumasa Ehara , Noriyoshi Uratani , Hideki Tanaka , Naoto Kato , Sumio Nakase , Norikazu Aruga , Takeo Matsuda, A machine translation system for foreign news in satellite broadcasting, Proceedings of the 13th conference on Computational linguistics, p.308-310, August 20-25, 1990, Helsinki, Finland
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
INDEX TERMS
Primary Classification:
H.
Information Systems
H.4
INFORMATION SYSTEMS APPLICATIONS
H.4.2
Types of Systems
Subjects:
Decision support (e.g., MIS)
Additional Classification:
G.
Mathematics of Computing
G.2
DISCRETE MATHEMATICS
I.
Computing Methodologies
I.2
ARTIFICIAL INTELLIGENCE
I.2.8
Problem Solving, Control Methods, and Search
Subjects:
Heuristic methods;
Dynamic programming
General Terms:
Algorithms,
Design,
Management,
Performance,
Theory
Keywords:
AND/OR graphs,
branch-and-bound,
decision table,
decision tree,
dynamic programming,
heuristic search,
optimal decision table conversion
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf