7.4 Greedy search strategy

7.4 Greedy search strategy

7.4.1 Greedy search assumptions

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.

7.4.2 Greedy search control structure

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