An Efficient Algorithm for Finding Certain Minimum-Cost Procedures for Making Binary Decisions

This paper is concerned with a class of procedures for making true-false decisions which depend on the outcome of eo sequence of elementary, binary tests. Certain of these procedures, calJed s-procedures, are conveniently represented by Boolean expressions (whose variables represent the elementary, bil~ary tests) and are easily carried out. If we are given the cost of applying each elementary, bina.ry test and the (a priori) prob'~bility of its outcome, the (average) cost of a procedure may be computed. Th.e genera! problem treated is to find efficiently a minimum-cost procedure equiv,~dent to a given s-procedure with known costs and probabilities for its elementt~ry, binary tests. Among the facts proved are two theorems showing that, under certain1 coi~ditions, the s-procedure found by a specified, efficient algorithm has mhfimum cost. The theorems and the etticient algorithm are used to solve illustrative problems in ti, e areas of computer programming, solving mat}mmatical problems, personnel selection, and medical diagnosis.