/ Data Structure and Algorithms  

Greedy Algorithm

Basic Concept

The so-called greedy algorithm means that when solving a problem, always makes the best choice in the current view. In other words, without considering the global optimality. The choice is only a local optimal solution in a certain sense.

Greedy algorithms do not have a fixed algorithm framework. The key to algorithm design is the choice of greedy strategies. It must be noted that the greedy algorithm does not obtain the global optimal solution to all problems, and the greedy strategy chosen must have no aftereffect, that is, the process after a certain state does not affect the previous state, and is only related to the current state.

Therefore, we must carefully analyze whether the greedy strategy adopted has no aftereffects.

Basic idea of greedy algorithm

  1. Establish a mathematical model to describe the problem.
  2. Divide the problem into several sub-problems.
  3. Solve each sub-problem to get the local optimal solution.
  4. Combine the local optimal solution of the sub-problems into a solution of the original problem.

Scope of application

The prerequisite of greedy strategy is that a local optimal strategy can lead to a global optimal solution.

In practice, greedy algorithms are rarely used. Generally, to analyze whether a problem is applicable to greedy algorithms, you can first select several example data of the problem to analyze and then make a judgment.

Implementation framework of greedy algorithm

1
2
3
4
5
6
7
8
Start with an initial solution to the problem

while (can move forward to a given overall goal)
{
    Use feasible decision to find a local optimal solution;
}

Combining all local optimal solution and get a global optimal solution

Choice of greedy strategies

Because the greedy algorithm can only achieve the global optimal solution through the strategy of get the local optimal solution, we must pay attention to determine whether the problem is suitable for the greedy algorithm, and whether the solution is the optimal solution of the problem.

Example

The following is a problem that can be solved by the greedy algorithm. The greedy solution is good, but it is not the optimal solution.

Knapsack problem

There is a backpack, and the capacity of the backpack is M = 150. There are 7 items, and the items can be divided into any size.

It is required to maximize the total value of the items in the backpack, but not exceed the total capacity.

Item A B C D E F G
Weight 35 30 60 50 40 10 25
Value 10 40 30 50 35 40 30

Analysis

Objective function: maximize Σpi

The constraint is that the total weight of the loaded items does not exceed the capacity of the backpack: ∑wi <= M (M = 150)

  1. According to the greedy strategy, every time you pick the item with the highest value and put it in the backpack, is the result the best?
  2. Can I get the optimal solution every time I load the smallest weighted item?
  3. Each time you select the item with the largest unit weight value, it becomes a strategy to solve this problem.

It is worth noting that the greedy algorithm is not completely unfeasible. Once the greedy strategy is proven, it is an efficient algorithm.

The greedy algorithm is still one of the most common algorithms, because it is simple and easy to implement, and it is not very difficult to construct a greedy strategy.

Unfortunately, it needs to be proved before it can be applied to the problem.

Generally speaking, the proof of the greedy algorithm revolves around: the optimal solution of the entire problem must be obtained from the optimal solution of the subproblems in the greedy strategy.

For the three greedy strategies in the example problem, none of them can be established (cannot be proven), and the explanation is as follows:

1. Greedy strategy: select the one with the highest value

Counter example:

W = 30

Item A B C
Weight 28 12 12
Value 30 20 20

According to the strategy, the item A is selected first, and then it cannot be selected anymore. However, it is better to select B and C.

2. Greedy strategy: choose the smallest weight

The counter example is similar to that of the first strategy.

3. Greedy strategy: Select the item with the largest value per unit weight

Counter example:

W = 30

Item A B C
Weight 28 20 10
Value 28 20 10

According to the strategy, the three items have the same unit weight value, and the program cannot make a judgment based on the existing strategy. If A is selected, the answer is wrong.