Home → Magazine Archive → November 1972 (Vol. 15, No. 11) → The conversion of limited-entry decision tables to... → Abstract

The conversion of limited-entry decision tables to optimal and near-optimal flowcharts: two new algorithms

By M. Verhelst

Communications of the ACM, Vol. 15 No. 11, Pages 974-980

Two new algorithms for deriving optimal and near-optimal flowcharts from limited entry decision tables are presented. Both take into account rule frequencies and the time needed to test conditions. One of the algorithms, called the optimum-finding algorithm, leads to a flowchart which truly minimizes execution time for a decision table in which simple rules are already contracted to complex rules. The other one, called the optimum-approaching algorithm, requires many fewer calculations but does not necessarily produce the optimum flowchart. The algorithms are first derived for treating decision tables not containing an ELSE-rule, but the optimum-approaching algorithm is shown to be equally valid for tables including such a rule. Both algorithms are compared with existing ones and are applied to a somewhat large decision table derived from a real case. From this comparison two conclusions are drawn. (1) The optimum-approaching algorithm will usually lead to better results than comparable existing ones and will not require more, but usually less, computation time. (2) In general, the greater computation effort needed for applying the optimum-finding algorithm will not be justified by the small reduction in execution time obtained.

The full text of this article is premium content


No entries found