Definition of greedy algorithm

Assuming that a problem is complicated and the global optimal solution cannot be found temporarily, we can consider splitting the original problem into several small problems and finding the optimal solution of each small problem respectively. Then, these “local optimal solutions” are stacked up and “regarded” as the optimal solution of the whole problem.

1.1 How to understand greed

At each step, choosing the current best over the global best is greedy.

1.2 The difference between greedy thought and divide and conquer Thought

Both greed and divide-and-conquer split the problem to reduce the complexity of the solution. The difference is that divide-and-conquer ensures that each task is relatively independent and does not consider the least optimal problem. However, there is always correlation between greedy subtasks, and the current optimal is selected between each trade-off.

Two. Greedy algorithm key steps

How to know whether a problem can be solved by greedy algorithm? Analyze the problem and solve the problem with greedy can refer to the steps:

Analyze the optimal solution of the problem
Analyze the optimal solution of the subproblem
Analyze whether subproblems can be superimposed as the optimal solution of the problem

Three. Classic application – biscuit problem

3.1 Problem Description

Each child can only be given one cookie at most. For each child I, there is an appetite value g[I], which is the minimum size of cookie that can satisfy their appetite. And every cookie J has a size S [J]. If s[j] >= g[I], we can assign this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number. Leetcode portal

3.2 Step disassembly according to greedy algorithm

Analyze the optimal solution of the problem

Obviously, meet the maximum number of children

Analyze the optimal solution of the subproblem

For each child, the smallest size of cookie should be chosen to satisfy that child’s appetite

Analyze whether subproblems can be superimposed as the optimal solution of the problem

From the greedy point of view, each child should be satisfied in the order of his appetite from small to large

3.3 Derivation of formula

Suppose we have m children with appetites ranging from G1 to gm, and n cookies ranging from S1 to Sn, and we order the two numbers from smallest to largest, gi <= GI +1 and Sj <= sj+1

The smallest cookie that can satisfy the appetite of the ith child is the JTH cookie, i.e., sj is the minimum of the remaining cookies satisfying sj >= gi. The optimal solution is to allocate the JTH cookie to the ith child

3.4 Code Implementation

public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int numOfChildren = g.length, numOfCookies = s.length;
        int count = 0;
        for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
            while (j < numOfCookies && g[i] > s[j]) {
                j++;
            }
            if(j < numOfCookies) { count++; }}return count;
    }
Copy the code

Four. Possible problems with greedy algorithms

4.1 “Global Optimal” and “Local Optimal”

In many situations in daily life, there is a great difference between global optimization and local optimization. Blindly pursuing global optimization may be quite different from the expected results.

Problem of fork in the road

The seemingly short road may branch out many times, and the shortest road may take a circle every time you take it

Snowball problem

A road that looks snowy may be short and not as big as a snowball on a sticky, long road

The taxi-hailing app was closest to me

The nearest bus picks up the fare every time, so some passengers may never get a taxi

4.2 The significance of the existence of greedy algorithms

Since greedy algorithms do not guarantee global optimality, why do we need them?

When the scale of the problem is very large, it is almost impossible to find the global optimal in a reasonable time, so we tend to accept the local optimal solution, because the quality of the local optimal solution is not necessarily bad.
In engineering applications, sometimes the precision difference between the optimal solution and the local optimal solution is very small, but it takes a longer time to search for the global optimal solution. After weighing the calculation accuracy and time cost, decision makers can often accept the local optimal solution.

Five. Greedy algorithm application scenarios

According to the previous description, we can know that although the greedy algorithm is not the global optimal, we can also use the greedy algorithm if the local optimal can be guaranteed to approach the global optimal to a large extent.
If it can be proved that the decision is not affected by the previous decision or the subsequent decision, then the greedy algorithm is the determined optimal solution algorithm. There is no guarantee that the greedy algorithm is optimal.

Fortunately, previous experience summed up some conditions for reference:

The problem has bound values and expected values
The problem can be broken down by greedy steps
The mathematical model of global optimal solution is difficult to establish or too much to calculate
It is not necessary to find the global optimal solution, “relatively good” will do

Common scenarios are: backpack problems, sharing candy, change, coverage, etc

Advantages and disadvantages of greedy algorithms

In fact, in the previous article has been mentioned, here is a summary.

Advantages: Simple thinking, easy to implement, efficient processing, trade-off between the best solution and complexity.
Disadvantages: Problem scenarios need to be screened. It cannot be used if there is a large difference between local optimal and global optimal.

Vii. How to prove that greedy algorithms can approach the optimal solution

It is often difficult to prove that a scene can satisfy “local optimum approaches global optimum by a large degree” with greedy solution. Generally speaking, if a problem can be converted into matroids, it can be solved by greed. But not all problems that can be solved by greed can be transformed into matroids. The derivation of matroids involves some mathematical knowledge, you can have a look. Matroids and optimal problems

Greedy algorithm