Four basic algorithm ideas
Data structures and algorithms are a very large range, and various problems require different algorithms, which are either complex or simple. This blog simply introduces four very basic and commonly used algorithm ideas through classic knapsack problems, namely greed, divide and conquer, backtracking, and motion rules.
These four are algorithm ideas, not specific algorithms, mainly to understand their ideas, not specific implementations.
This article is mainly to help me re-summarize the knowledge points that were slightly scattered before, so a lot of specific content is in other previous blogs.
Suppose we have a backpack that can hold 100kg of items and can hold various items. We have the following 5 types of beans, each of which has a different total amount and total value. In order to maximize the total value of the items in the backpack, how do we choose which beans to put in the backpack? How many beans should each be packed?
| Items | Total quantity (kg) | Total value (yuan) |
|---|---|---|
| Soybeans | 100 | 100 |
| Green Beans | 30 | 90 |
| Red Beans | 60 | 120 |
| Black Beans | 20 | 80 |
| Green beans | 50 | 75 |
Greedy
In fact, this question is very simple. I estimate that you can figure it out at once. That’s right, we just need to calculate the unit price of each item first, and install it in order from high to low. The unit price is arranged from high to low, in order: black beans, mung beans, red beans, green beans, and soybeans, so we can pack 20kg of black beans, 30kg of mung beans, and 50kg of red beans into our backpack.
The solution to this problem is obvious, and it essentially relies on a greedy algorithm. Combined with this example, I summarize the steps of greedy algorithm to solve the problem, let’s take a look.
Problem-solving steps
The first step, when we see this kind of problem, we must first think of greedy algorithm: for a set of data, we ** define the limit value and the expected value **, hoping to select a few data, in the case of meeting the limit value, the expected value is the largest.
By analogy to the example just now, the limit value is that the weight cannot exceed 100kg, and the expected value is the total value of the item. This set of data is 5 kinds of beans. We choose a part that weighs no more than 100kg and has the largest total value.
In the second step, we try to see if this problem can be solved with a greedy algorithm: ** Each time you choose the data that contributes the most to the expected value in the current case, with the same contribution to the limit value **.
By analogy to the example just now, we choose the bean with the highest unit price from the remaining beans every time, that is, the bean that contributes the most to the value under the same weight.
In the third step, we will give a few examples to see if the results produced by the greedy algorithm are optimal. In most cases, just give a few examples to verify. Strictly proving the correctness of a greedy algorithm is very complicated and requires more mathematical reasoning. Moreover, from a practical point of view, most problems that can be solved with greedy algorithms are obvious and do not require strict mathematical derivation proofs.
Attention
The premise of greedy algorithm work is that the choice of the previous step will not affect the choice of the next step. For example, this problem just now, if I add restrictions, if I choose soybeans, I cannot choose mung beans. This problem cannot be solved with greedy algorithm.
Backtracking
Let’s slightly modify the backpack problem just now to become a 0-1 backpack problem:
We have a backpack, and the total carrying weight of the backpack is Wkg. Now we have n items, each of which varies in weight and is indivisible. We now expect to select several items and load them into the backpack. How to maximize the total weight of the items in the backpack without exceeding the weight that the backpack can carry?
In fact, we have already talked about the backpack problem in the section of greedy algorithm, but the items mentioned there can be divided, and I can load part of an item into the backpack. The backpack problem we talked about today, the items are indivisible, either loaded or not, so it is called the 0-1 backpack problem. Obviously, this problem can no longer be solved by greedy algorithms. Let’s now see how to solve it with a backtracking algorithm.
** Backtracking is an idea that is often used in conjunction with recursion, a programming technique. **
The processing idea of backtracking is somewhat similar to enumeration search. We enumerate all the solutions and find the solution that meets the expectation.
** In order to regularly enumerate all possible solutions and avoid omission and repetition, we divide the problem solving process into multiple stages **. At each stage, we will face a fork in the road. We first choose a road at will. When we find that this road cannot go (the solution that does not meet the expectations), we will go back to the previous fork in the road and choose another way to continue walking.
For a detailed explanation, see this blog: https://sunra.top/posts/376d0826/
In fact, from a one-sided point of view, backtracking is to record which nodes you have passed in the process of depth-first traversal, and the condition of reaching the leaf node is that there is no other way to choose, and then start backtracking.
Dynamic Programming
Dynamic Programming if from the perspective of recursion, in fact, is not a very difficult idea, the above-mentioned ** backtracking is to record the path taken in the traversal process, then Dynamic Programming is a recursion process with memos, in other words, if there are repeated sub-problems in the recursion process, use Dynamic Programming, if not, then backtrack. **
For example, in the process of recursion, I choose the optimal solution of the first four kinds of beans is a function of selecting the first three and selecting the first two optimal solutions, that is, dp (4) = f (dp (3), dp (2)), Once I calculate dp (4), I first find a place to save it. When I calculate dp (5), I need to use dp (4), so I don’t need to continue recursion.
Converting this recursion process into a recursive formula is Dynamic Programming.
Details can be found here: https://sunra.top/posts/a80d0031/
Divide and conquer algorithm
The core idea of divide and conquer algorithm is actually four words, divide and conquer, that is, divide the original problem into n sub-problems with smaller scale and similar structure to the original problem, solve these sub-problems recursion, and then combine the results to get the solution of the original problem.
This definition looks a bit similar to the definition of recursion. Regarding the difference between divide and conquer and recursion, we said in the order (below) that the divide and conquer algorithm is an idea to deal with problems, and recursion is a programming technique. In fact, divide and conquer algorithms are generally suitable for recursion implementation. In the recursion implementation of the divide and conquer algorithm, each layer of recursion will involve the following three operations:
Decomposition: Decompose the original problem into a series of sub-problems;
Solve: solve each sub-problem recursively, and if the sub-problem is small enough, solve it directly;
Merge: Merge the results of sub-questions into the original question.
Divide and conquer algorithm can solve the problem, generally need to meet the following conditions:
The original problem has the same pattern as the decomposed small problem;
The subproblems decomposed into the original problem can be solved independently, and there is no correlation between the subproblems. This is the obvious difference between the divide-and-conquer algorithm and Dynamic Programming.
has a decomposition termination condition, that is, when the problem is small enough, it can be solved directly;
The subproblem can be merged into the original problem, and the complexity of this merge operation cannot be too high, otherwise the effect of reducing the overall complexity of the algorithm will not be achieved.
归并排序就是一个非常典型的分治思想