5.2. The Greedy Approach¶
Algorithm utilizing the greedy approach proceed step by step. On each step, the best option is selected based on the information available at that time (locally optimal choice). It is good to note that there are often multiple ways to define what is the optimal choice. For example, we need to visit a set of cities and we want to develop an algorithm that selects the route between the cities so that the total distance is as small as possible. The locally optimal choice might be a) the nearest city from the current city, or b) the nearest two cities that are not part of the route yet or are end points of the existing route. Depending on the choice we might end up in different solution.
Often the choice that seems the best on the current step does not lead to the optimal solution at then end, but the greedy approach often helps to find a reasonably good solution. Therefore, the greedy approach is suitable when we want to find a good solution fast, but we do not necessarily need the optimal solution. However, there are also problems for which a greedy algorithm that always finds the optimal solution is known.
Example 5.2.1
We need to schedule jobs out of a set of \(N\) jobs so that the profit is maximized. Each job takes unit time for execution. Each job has a deadline and profit. Profit is earned only if the job is completed by the deadline.
The simple solutions is to test all the possible schedules (orders of jobs) and to select then the one that gives the highest profit. However, there are \(N!\) different permutations of \(N\) jobs. Therefore such brute-force solution has a running time of \(\Theta(N!)\). With a greedy approach we can be much more efficient.
Let us consider the following simple greedy algorithm:
# J = array of jobs; D = array of deadlines; P = array of profits
def schedule(J, D, P):
J.sort() # Sort the jobs in decreasing order of profit
S = [None] * len(J) # Schedule array
counter = 0 # counter to the amount of jobs in the schedule
for i in range(len(J)):
if D[i] >= counter + 1:
S[counter] = J[i] # Add the job to the schedule if the job will be done before the deadline
counter += 1
return S
The algorithm “greedily” starts with the most profitable job, proceeds to the second most profitable, and so on. We start with sorting the job list which can be done in \(\Theta(N \log(N))\) time. The actual scheduling part goes through the job list once and is \(\Theta(N)\). Therefore, the whole algorithm is \(\Theta(N \log(N))\). If we apply the algorithm to the above table of jobs we get the following solution:
And the total profit is \(220\).
We can do better than this. Let us consider the following modification of the greedy algorithm:
# J = array of jobs; D = array of deadlines; P = array of profits
def schedule(J, D, P):
J.sort() # Sort the jobs in decreasing order of profit
S = [None] * len(J) # Schedule array
for i in range(len(J)):
for j in range(D[i] - 1, -1, -1): # find the latest possible free slot meeting the job's deadline
if not S[j]:
S[j] = J[i] # Add the job to the schedule if the job will be done before the deadline
break
return S
The new version of the algorithm does not only choose the most profitable jobs first but also schedule them in locally optimal manner:
Now, the total profit is \(270\).
It can be proven that the latter greedy algorithm provides always the optimal solution. However, due to the two nested loops, the average running time of this algorithm is \(\Theta(N^2)\).
