The main idea

A greedy algorithm lets a computer simulate a “greedy person” to make a decision. The greedy man is shortsighted. He always:

  • Make only the choice that is best for the moment
  • Focus only on immediate benefits, not the impact of the choice on the future

And once he has made a choice, there is no way to go back, so in order to maximize his profit, he needs to make sure that he never makes the wrong choice.

Greedy algorithms do not consider the problem from the point of view of global optimization, but only care about the local optimal solution in a sense. Therefore, greedy algorithms cannot guarantee the optimal solution in all cases. So when we use greedy algorithms, we want to make sure that we can prove that the optimal solution is correct.

Greedy nature

A problem that can be solved with a greedy algorithm should have the following properties:

  • Optimal substructure: The optimal solution of a problem contains the optimal solution of its subproblems
  • Greedy selectivity: the global optimal solution of the problem can be reached through a series of locally optimal choices, that is, through greedy selection

That method

The most difficult part of greedy algorithm is never the solution of the problem, but lies in the correctness of the proof, commonly used proof methods have induction and exchange proof method.

  • Induction: induction of the number of steps or problem size of the algorithm
  • Exchange argument method: starting from the optimal solution, under the premise of ensuring the same optimality, gradually replace from an optimal solution, so as to obtain the solution of the greedy strategy

Due to space limitation, we will focus on inductive proof. Inductive proof is essentially mathematical induction, so let’s review mathematical induction.

Mathematical induction

Mathematical Induction is a method of Mathematical proof, usually used to prove that a given statement is true in the whole (or local) range of natural numbers.

That step

The simplest and most common mathematical induction is to prove that a statement is true when n is equal to any natural number. There are two steps to prove:

  1. Prove that whenn = 1, the proposition is true
  2. Prove that ifn = m(m is any natural number), then it can be deduced thatn = m + 1Is also true

1 is the basis of induction, and 2 is the induction step.

The principle of

The principle of this method is that once we have proved that the proposition is true at some starting point (e.g., n = 1) and that the process from one value to the next is valid (i.e., n = m to n = m + 1), then any value can be derived by repeated use of this method. That is:



So:




For example

If we want to prove that for any natural number, it satisfies:


Inductive basis

Find the starting point, i.e. N = 1, where the left side of the equation equals 1 and the right side equals:


The left and right sides are equal, so at n equals 1, this is true.

Induction step

First assume: for any natural number n statement is true.

Then, when n = n + 1:






So if n is equal to n plus 1, this is true. Never put off till tomorrow what you can.

The correctness of the algorithm is proved by induction

The proof steps of inductive proof are as follows:

  1. Describe a natural numbernThe proposition that the execution of greedy strategies will eventually lead to the optimal solution, where the natural numbersnCan representAlgorithm stepsorProblem size.
  2. Prove that the problem is true for all natural numbers

Among them, the second step uses mathematical induction proof, that is, the practice of induction basis and induction steps.

Now let’s see how we can prove Kruskal’s algorithm by induction.

Kruskal minimum spanning tree

Kruskal algorithm is a common and easy to write minimum spanning tree algorithm, invented by Kruskal. The algorithm is based on greedy idea, the basic idea is to add edges from small to large.

The main idea

  1. The edges of the graph are selected according to the weight size from small to large
  2. The edge with the lowest weight is selected, and the two points constituting the edge are assumed to be (point1, point2). If point1 and point2 are already in a connected graph, the edge is discarded. Otherwise, the edge is added to the minimum spanning tree
  3. Repeat Step 2 until a minimum spanning tree is formed

Proof of correctness

Narrative proposition

First, the proposition is given: for any n, the algorithm can obtain a minimum spanning tree for n-order graph.

Inductive basis

When n is equal to 2, there’s only one edge, and the statement is clearly true.

Induction step

Assuming that the algorithm is correct for graphs with n vertices, consider graphs with n + 1 fixed points, it is assumed thatWhere the minimum edge weight is.

At this point, in the figureThe connection pointWith the pointTo get the figure.

According to the induction hypothesis, it can be deduced from the algorithm: existenceMinimum spanning tree of. make,Is aboutMinimum spanning tree of.

ilyaIf:notMinimum spanning tree of, then there must be some containMinimum spanning tree of edges,(i.e.The edge weight of is less than).

At this point, theRemove theEdge, to obtain the minimum spanning tree of G’, and there is:


This expression is associated withThe optimal solutions contradict each other, soMust beThe minimum spanning tree of.

conclusion

  • Greedy algorithms do not consider the problem from the point of view of global optimization, but only consider the local optimal solution in a sense, non-traceable, without considering the consequences
  • The problem that can be solved by greed needs to satisfy optimal substructure and greed selectivity
  • Greedy algorithm can not guarantee that the optimal solution can be obtained in all cases, so it is necessary to prove the correctness of the algorithm when using greedy algorithm. Common proof methods include induction and exchange demonstration
  • Mathematical induction is usually used to prove that a given proposition is true in the whole (or local) range of natural numbers, and the proof process is inductive basis + inductive steps
  • Induction proof requires the proposition to be given, and then mathematical induction is used to prove that the proposition is true for all natural numbers

Review past

  • Graphic double pointer | LeetCode 27. Remove elements
  • Get the interview series | partition algorithm by three steps

TOP Interview series

  • Diagram to select TOP interview questions 001 | LeetCode 237. Delete a node from a linked list
  • Diagram to select TOP interview questions 002 | LeetCode 104. The maximum depth of a binary tree
  • Diagram to select TOP interview questions 003 | LeetCode 344. Inverted string

🐱

If you think the article is well written, please do me two small favors:

  1. Like and follow me to get this article seen by more people
  2. Pay attention to the public number “programming to save the world”, the public number focuses on programming foundation and server research and development, you will get the first time the new article push ~

Original is not easy, great encouragement ~ thank you!