Skip to content

Latest commit

 

History

History
105 lines (76 loc) · 5 KB

greedy-algorithms.asc

File metadata and controls

105 lines (76 loc) · 5 KB
Raw

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 the 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 is exhaustive and 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 the 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 work 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 bag’s maximum weight?

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 we will 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 take the last and the first to have a total weight of 7 and a total cost of 8.

We could also take items with the smallest weight so we can fit as much as possible in the knapsack. 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 option is worse than picking the most significant amount! 👎

  • 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. These heuristics seem 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 the value/weight ratio. Sorting runtime is O(n log n). The rest is linear operations, so the answer is O(n log n) for our greedy algorithm.