Each test divides the current candidate set into a tested subset and its complement: failure places the defective item inside the subset, whereas success places it outside. A sequence of tests is therefore a binary decision tree, and minimizing its expected depth is the Huffman coding problem with weights .
Combine the smallest two current weights repeatedly. One choice of merges is , , , , , , , , . It gives this explicit prefix code:At any node, test the candidate items whose next code digit is one. Assign failure to digit one and success to digit zero, and repeat until only a single codeword remains. This specifies every test, including the first subset . Huffman coding minimizes the weighted codeword lengths, so the optimal expected number isThe sum of the successive merged weights is another check on the numerator .
There is a genuinely different optimal procedure. Exchange the codewords assigned to items three and four. Both have code length four, so each item's length, and hence the expected number of tests , remains unchanged. The first tested subset now contains item three instead of item four, so this changes the tested groups rather than merely reversing the names of the two test outcomes. The new prefix code still identifies every item uniquely and retains the minimum Huffman coding expectation.
The procedure in part (i) sometimes needs five tests, for items one or two. A binary decision tree of height has at most leaves, so distinguishing ten possibilities requires .
Articles by others on the same topic
There are currently no matching articles.