19 October 1987 Fast Algorithm To Generate Near Optimal Binary Decision Programs
Author Affiliations +
Binary decision (BD) programs have widespread applicability in diverse areas. In many situations, problems are defined in terms of Boolean expressions, which must be converted to decision programs for evaluation. Since the construction of optimal BD programs is NP-complete, absolute optimization appears computationally intractable. This paper presents a fast heuristic algorithm for constructing near-optimal decision programs and provides an optimality metric. The algorithm involves two steps: preprocessing and optimization. The preprocessor builds a sub-optimal (in some conditions near-optimal) decision program in linear time. If sub-optimal programs are generated, the optimizer is invoked, producing a near-optimal program, using decision tables, in 0(n2) time, where n is the size of the reduced decision table generated in the first step.
© (1987) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
P. C. Baracos, P. C. Baracos, L. C. Vroomen, L. C. Vroomen, L. J. Vroomen, L. J. Vroomen, } "Fast Algorithm To Generate Near Optimal Binary Decision Programs", Proc. SPIE 0853, IECON '87: Industrial Applications of Control and Simulation, (19 October 1987); doi: 10.1117/12.942936; https://doi.org/10.1117/12.942936

Back to Top