Skip to content

Latest commit

 

History

History
105 lines (76 loc) · 4.97 KB

greedy-algorithms.asc

File metadata and controls

105 lines (76 loc) · 4.97 KB

Greedy Algorithms

Greedy algorithms are designed to find a solution by going one step at a time and using heuristics to determine the best choice. They are quick but not always lead to most optimum results since it might not take into consideration all the options to give a solution.

An excellent example of a greedy algorithm that doesn’t work well is finding the largest sum on a tree.

graph G {
  5 -- 3 [color="#B8E986", penwidth=2]
  5 -- 7 [color="#FF5252", penwidth=2]
  3 -- 87 [color="#B8E986", penwidth=2]
  3 -- 1
  7 -- 2
  7 -- 4 [color="#FF5252", penwidth=2]

  label="Optimal vs. Greedy path"
}

Let’s say the greedy heuristics are set to take the more significant value. The greedy algorithm will start at the root and say "Which number is bigger 3 or 7?" Then go with 7 and later 4. As you can see in the diagram, the most significant sum would be the path 7 - 3 - 87. A greedy algorithm never goes back on its options. This greedy choice makes it different from dynamic programming which exhaustive and it’s guaranteed to find the best option. However, when they work well, they are usually faster than other options.

Greedy algorithms are well suited when an optimal local solution is also a globally optimal solution.

Tip

Greedy algorithms make the choice that looks best at the moment based on a heuristic such as smallest, largest, best ratio, and so on. This algorithm only gives one shot at finding the solution and never goes back to consider other options.

Don’t get the wrong idea; some greedy algorithms work very well if they are designed correctly.

Some examples of greedy algorithms that works well:

  • part04-algorithmic-toolbox.asc: we select the best (minimum value) remove it from the input and then select the next minimum until everything is processed.

  • part04-algorithmic-toolbox.asc: the "merge" uses a greedy algorithm, where it combines two sorted arrays by looking at their current values and choosing the best (minimum) at every time.

In general, we can follow these steps to design Greedy Algorithms:

  1. Take a sample from the input data (usually in a data structure like array/list, tree, graph).

  2. Greedy choice: use a heuristic function that will choose the best candidate. E.g., Largest/smallest number, best ratio, etc.

  3. Reduce the processed input and repeat step #1 and #2 until all data is gone.

  4. Return solution.

  5. Check correctness with different examples and edge cases.

Fractional Knapsack Problem

We are going to use the "Fractional Knapsack Problem" to learn how to design greedy algorithms. The problem is the following:

You are going to resell legumes (rice, beans, chickpeas, lentils) and you only brought a knapsack. What proportion of items can you choose to get the highest loot without exceeding the maximum weight of the bag?

Let’s say we have the following items available.

Knpasack Input
const items = [
  { value: 1, weight: 1},
  { value: 4, weight: 3 },
  { value: 5, weight: 4 },
  { value: 7, weight: 5 },
];

const maxWeight = 7;

So, we have four items that we can choose from. We can’t take them all because the total weight is 13 and the maximum we can carry is 7. We can’t just take the first one because with value 1 because it is not the best profit.

How would you solve this problem?

First, we have to define what parameters are we going to use to make our greedy choice. This some ideas:

  • We can take items with the largest value in hopes to maximize profit. Based on that we can make take the last item and first having a total weight of 7 and a total cost of 8.

  • Also, we could take items smallest weight so we can fit as much as possible. Let’s analyze both options. So we can choose the first two items for a total value of 5 and a total weight of 4. This is worse than picking the largest value! 👎

  • One last idea, we can take items based on the best value/weight ratio and take fractions of an article to fill up the knapsack to maximum weight. In that case, we can buy the last item in full and 2/3 of the 2nd item. We get a total value of 9.67 and a total weight of 7. This heuristics seems to be the most profitable. 👍

Items value/weight ratio
  { value: 1, weight: 1 }, // 1/1  = 1
  { value: 4, weight: 3 }, // 4/3 = 1.33 ✅
  { value: 5, weight: 4 }, // 5/4 = 1.25
  { value: 7, weight: 5 }, // 7/5 = 1.4 ✅

Let’s implement this algorithm!

Factional Knapsack Problem Implementation
link:../../../src/algorithms/knapsack-fractional.js[role=include]

What’s the runtime of this algorithm?

We have to sort the array based on value/weight ratio. Sorting runtime is O(n log n). The rest is linear operations, so we the answer is O(n log n) for our greedy algorithm.