Greedy algorithm and its use!!
What is a greedy algorithm?
You may have heard about a lot of algorithmic design techniques while sifting through some of the articles here. Some of them are:
- Brute Force
- Divide and Conquer
- Greedy Programming
- Dynamic Programming to name a few. In this article, you will learn about what a greedy algorithm is and how you can use this technique to solve a lot of programming problems that otherwise do not seem trivial.
Imagine you are going for hiking and your goal is to reach the highest peak possible. You already have the map before you start, but there are thousands of possible paths shown on the map. You are too lazy and simply don’t have the time to evaluate each of them. Screw the map! You started hiking with a simple strategy — be greedy and short-sighted. Just take paths that slope upwards the most. This seems like a good strategy for hiking. But is it always the best ?
After the trip ended and your whole body is sore and tired, you look at the hiking map for the first time. Oh my god! There’s a muddy river that I should’ve crossed, instead of keep walking upwards. This means that a greedy algorithm picks the best immediate choice and never reconsiders its choices. In terms of optimizing a solution, this simply means that the greedy solution will try and find local optimum solutions — which can be many — and might miss out on a global optimum solution.
Formal Definition
Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.
Greedy algorithms have some advantages and disadvantages:
- It is quite easy to come up with a greedy algorithm (or even multiple greedy algorithms) for a problem. Analyzing the run time for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer). For the Divide and conquer technique, it is not clear whether the technique is fast or slow. This is because at each level of recursion the size of gets smaller and the number of sub-problems increases.
- The difficult part is that for greedy algorithms you have to work much harder to understand correctness issues. Even with the correct algorithm, it is hard to prove why it is correct. Proving that a greedy algorithm is correct is more of an art than a science. It involves a lot of creativity. Usually, coming up with an algorithm might seem to be trivial, but proving that it is actually correct, is a whole different problem.
Interval Scheduling Problem
Let’s dive into an interesting problem that you can encounter in almost any industry or any walk of life. Some instances of the problem are as follows:
- You are given a set of N schedules of lectures for a single day at a university. The schedule for a specific lecture is of the form (s time, f time) where s time represents the start time for that lecture and similarly the f time represents the finishing time. Given a list of N lecture schedules, we need to select maximum set of lectures to be held out during the day such that none of the lectures overlap with one another i.e. if lecture Li and Lj are included in our selection then the start time of j >= finish time of i or vice versa .
- Your friend is working as a camp counselor, and he is in charge of organizing activities for a set of campers. One of his plans is the following mini-triathlon exercise: each contestant must swim 20 laps of a pool, then bike 10 miles, then run 3 miles.
- The plan is to send the contestants out in a staggered fashion, via the following rule: the contestants must use the pool one at a time. In other words, first one contestant swims the 20 laps, gets out, and starts biking.
- As soon as this first person is out of the pool, a second contestant begins swimming the 20 laps; as soon as he or she is out and starts biking, a third contestant begins swimming, and so on.
- Each contestant has a projected swimming time, a projected biking time, and a projected running time. Your friend wants to decide on a schedule for the triathlon: an order in which to sequence the starts of the contestants.
- Let’s say that the completion time of a schedule is the earliest time at which all contestants will be finished with all three legs of the triathlon, assuming the time projections are accurate. What is the best order for sending people out, if one wants the whole competition to be over as soon as possible? More precisely, give an efficient algorithm that produces a schedule whose completion time is as small as possible.
When do we use Greedy Algorithms
Greedy Algorithms can help you find solutions to a lot of seemingly tough problems. The only problem with them is that you might come up with the correct solution but you might not be able to verify if its the correct one. All the greedy problems share a common property that a local optima can eventually lead to a global minima without reconsidering the set of choices already considered.
Greedy Algorithms help us solve a lot of different kinds of problems, like:
- Shortest path algorithm :-
Even the wisest man can’t see through the future. Our best bet is taking the action that seems good now.
Well, this is the main idea behind greedy algorithm. The problem is far too complicated for future planning. We’ll just do what seems good now and proceed to see the final result. Clearly, the main focus for greedy algorithm is its correctness, not running time. They generally run fast, but it’s hard to prove they are correct. Choosing the correct greedy criterion is an art.
Here we’ll introduce Dijkstra Shortest-Path algorithm as a demonstration.
1. An instance of Dijkstra Shortest-Path algorithm
Dijkstra Shortest-Path algorithm is an algorithm about graph. Given a directed graph G=(V,E) with nonnegative edge length, a source vertex s, we use this algorithm to compute L(v) = length of a shortest path from s to v in G, where v is any vertex in V.
See an example below.
Start from source s, L(t) = 6.
2. What is the algorithm doing?
From the example above, our first impression would be the algorithm just selects the shortest path from current vertex. However, that’s not the story. The algorithm is doing something a bit more complicated.
Before deciding which path to take, we’ll first initialize two data structures. X = {s}, which stores vertices processed so far. A[s] = 0, which is the computed shortest path distances.
The pseudo codes look like this.
While (x != v) //iteration until we reach target
{
Among all crossing edges (v,w) for X, //all potential candidates
Pick the one that minimize A[v] + lvw //Dijkstra greedy criterion
Call that edge (v*, w*)
Add w* to X
Set A[w*] = A[v*] + lv*w*
}
You see, the algorithm is not merely picking the shortest path for current vertex. Rather, it’s calculating all previous crossing edges and finding the one that minimize the distance so far. Let’s look at the example again.
The first step is initialization. X={s} and A[s] = 0.
The second step is examining all crossing edges, which are (s,v) and (s,w), and pick the one that meet the greedy criterion. A[s] + lsv = 1. A[s] + lsw = 4. Clearly (s,v) is the one to pick. As a result we add v to X and X= {s, v}. We also update A[] so that A[v] = 1.
What about the next iteration? Same story. We examining all crossing edges, which are (s,w), (v,w) and (v,t). Notice the (s,w) edge here. We not only look edges from v, but also all other edges from vertices in X. That’s the key. A[s] + lsw = 4. A[v] + lvw = 3. A[v] + lvt = 7. Surely the second one is the best choice. As a result we add w to X and X={s,v,w}. We also update A[] so that A[w] = 3.
The final iteration. There’re only two crossing edges this time since s,v,w are all in X. They are (v,t) and (w,t). A[v] + lvt = 7. A[w] + lwt = 6. Edge (w,t) is the shortest. Because t is the target, we’re done.
References
Introduction to Algorithms from Javatpoint.
When to use greedy algorithm from Software testing help.