How do you formulize a greedy technique?

Answer 1

In order to develop an algorithm based on the greedy technique to solve a general optimization problem, we need the following data structures and functions:

i) A set or list of give / candidate values from which choices are made, to reach a solution. For example, in the case of Minimum Number of Notes problem, the list of candidate values (in rupees) of notes is

{1, 2, 5, 10, 20, 50, 100, 500, 1000}. Further, the number of notes of each denomination should be clearly mentioned. Otherwise, it is assumed that each candidate value can be used as many times as required for the solution using greedy technique. Let us call this set as

GV : Set of Given Values

ii) Set (rather multi-set) of considered and chosen values: This structure contains those candidate values, which are considered and chosen by the algorithm based on greedy technique to reach a solution. Let us call this structure as

CV : Structure of Chosen Values

The structure is generally not a set but a multi-set in the sense that values may be repeated. For example, in the case of Minimum Number of Notes problem, if the amount to be collected is Rs. 289 then

CV = {100, 100, 50, 20, 10, 5, 2, 2}

iii) Set of Considered and Rejected Values: As the name suggests, this is the set of all those values, which are considered but rejected. Let us call this set as

RV : Set of considered and Rejected Values

A candidate value may belong to both CV and RV. But, once a value is put in RV, then this value can not be put any more in CV. For example, to make an amount of Rs. 289, once we have chosen two notes each of denomination 100, we have

CV = {100, 100}

At this stage, we have collected Rs. 200 out of the required Rs. 289. At this stage RV = {1000, 500}. So, we can chose a note of any denomination except those in RV, i.e., except 1000 and 500. Thus, at this stage, we can chose a note of denomination 100. However, this choice of 100 again will make the total amount collected so far, as

Rs. 300, which exceeds Rs. 289. Hence we reject the choice of 100 third time and put 100 in RV, so that now RV = {1000, 500, 100}. From this point onward, we can not chose even denomination 100.

Next, we consider some of the function, which need to be defined in an algorithm using greedy technique to solve an optimization problem.

iv) A function say SolF that checks whether a solution is reached or not. However, the function does not check for the optimality of the obtained solution. In the case of Minimum Number of Notes problem, the function SolF finds the sum of all values in the multi-set CV and compares with the desired amount, say Rs. 289. For example, if at one stage CV = {100, 100} then sum of values in CV is 200 which does not equal 289, then the function SolF returns. 'Solution not reached'. However, at a later stage, when CV = {100, 100, 50, 20, 10, 5, 2, 2}, then as the sum of values in CV equals the required amount, hence the function SolF returns the message of the form 'Solution reached'.

It may be noted that the function only informs about a possible solution. However, solution provided through SolF may not be optimal. For instance in the Example above, when we reach CV = {60, 10, 10}, then SolF returns 'Solution, reached'. However, as discussed earlier, the solution 80 = 60 + 10 + 10 using three notes is not optimal, because, another solution using only two notes, viz., 80 = 40 + 40, is still cheaper.

v) Selection Function say SelF finds out the most promising candidate value out of the values not yet rejected, i.e., which are not in RV. In the case of Minimum Number of Notes problem, for collecting Rs. 289, at the stage when RV = {1000, 500} and CV = {100, 100} then first the function SelF attempts the denomination 100. But, through function SolF, when it is found that by addition of 100 to the values already in CV, the total value becomes 300 which exceeds 289, the value 100 is rejected and put in RV. Next, the function SelF attempts the next lower denomination 50. The value 50 when added to the sum of values in CV gives 250, which is less than 289. Hence, the value 50 is returned by the function SelF.

vi) The Feasibility-Test Function, say FeaF. When a new value say v is chosen by the function SelF, then the function FeaF checks whether the new set, obtained by adding v to the set CV of already selected values, is a possible part of the final solution. Thus in the case of Minimum Number of Notes problem, if amount to be collected is

Rs. 289 and at some stage, CV = {100, 100}, then the function SelF returns 50. At this stage, the function FeaF takes the control. It adds 50 to the sum of the values in CV, and on finding that the sum 250 is less than the required value 289 informs the main/calling program that

{100, 100, 50} can be a part of some final solution, and needs to be explored further.

vii) The Objective Function, say ObjF, gives the value of the solution. For example, in the case of the problem of collecting Rs. 289; as

CV = {100, 100, 50, 20, 10, 5, 2, 2} is such that sum of values in CV equals the required value 289, the function ObjF returns the number of notes in CV, i.e., the number 8.

After having introduced a number of sets and functions that may be required by an algorithm based on greedy technique, we give below the outline of greedy technique, say Greedy-Structure. For any actual algorithm based on greedy technique, the various structures the functions discussed above have to be replaced by actual functions.

These functions depend upon the problem under consideration. The Greedy-Structure outlined below takes the set GV of given values as input parameter and returns CV, the set of chosen values. For developing any algorithm based on greedy technique, the following function outline will be used.