The greedy search strategy is analogous to the greedy method taught in introductory algorithms classes. The greedy method works in stages, considering one input element at a time. At each stage, the method decides whether an input is part of an optimal solution. The choice of the input element to examine at any stage is based on an optimization measure.
This strategy assumes that the program is divisible into segments that can be tested for responsibility for the defect. A procedure can be divided into its statements, code blocks, or loop nests. The procedures in a program can be divided into groups in which the procedures are all invoked by a common procedure.
The next code sample shows the control structure for the greedy search strategy.
Set P to the set of all code segments in question Set S to the empty set Do while P has elements remaining Pick an element E from P and remove it from P If E isn’t responsible for the problem Then Set S = Union(S, {E}) End-if End-do S is the set of code segments that causes the bug
The key to the greedy strategy is finding a selection method that maximizes the benefit and minimizes the cost for each iteration of the strategy.
The following are measures of the benefit:
The number of lines of code validated
The number of procedures validated
The number of paths through the code validated
The following are measures of the cost:
The CPU time it takes to execute the validated code
The wall-clock time it takes to execute the validated code
The labor required to set up the validation exercise