A Textbook of Data Structures and Algorithms, Volume 3

20Greedy Method

This chapter discusses the greedy method and demonstrates the strategy over the Knapsack problem, Prim’s and Kruskal’s spanning tree extraction algorithms and Dijkstra’s Single Source Shortest Path problem.

20.1. Introduction

The greedy method is an algorithm design technique, which is applicable to problems defined by an objectivefunction that needs to be maximized or minimized, subject to some constraints. Given n inputs to the problem, the aim is to obtain a subset of n, that satisfies all the constraints, in which case it is referred to as a feasible solution. A feasible solution that serves to obtain the best objective function value (maximal or minimal) is referred to as the optimal solution.

The greedy method proceeds to obtain the feasible and optimal solution, by considering the inputs one at a time. Hence, an implementation of the greedy method-based algorithm is always iterative in nature. Contrast this with the implementation of Divide and Conquer based algorithms discussed in Chapter 19, which is always recursive in nature.

20.2. Abstraction

The abstraction of the greedy method is shown in Figure 20.1. Here, the function SELECT(A) makes a prudent selection of the input depending on the problem. Function FEASIBLE() ensures that the solution satisfies all constraints imposed on the problem and AUGMENT() augments the current input which is a feasible solution to the solution set. Observe how the for loop ensures consideration of inputs one by one, ...