First article: wechat search for “amateur code farmers”
Algorithms and data structures have always been the basic internal work of programmers. It can be said that without the infrastructure construction of data structures and the support of algorithms, there would have been no information revolution era of nearly 80 years. Data structure can be regarded as the container of algorithm implementation. Through a series of data sets with special structure, the algorithm can be executed more efficiently and reliably.
The application of algorithms is not just in programming. In a narrow sense, algorithms can be regarded as the order, method and composition of data transmission and processing, just like various sorting algorithms, etc. Broadly speaking, algorithms are more like logic and rules for how things work. The sun rises in the east and sets in the west, the tides of the sea and the waxing and waning of the moon may all seem like algorithms, except that nature, rather than computers, is the enforder.
Chatting away. Therefore, to understand the algorithm, it is important to understand its ideas and feel its inner. Some of you might say, “The algorithm is Leetcode, it’s just brushing.”
One-sided. The problems are always endless, but there are only a few ideas for the algorithm. So, brush so many questions of you, still do not understand these several common algorithm ideas, presumably should reflect on the next.
The enumeration
First, the simplest idea, the enumeration algorithm. Enumeration is also called exhaustive, as the name implies, exhaustive enumeration. The application scenarios of the enumeration idea are very wide and easy to understand. To put it simply, enumeration is to list the possible solutions of a problem and then bring them into the problem test one by one, so as to obtain the exact solution that can solve the problem from a series of possible solutions.
Enumerations seem simple, but there are a few considerations that can easily be overlooked. For example, the screening conditions of “possible solutions/candidate solutions” of the problem to be solved, the mutual influence of “possible solutions”, the cost of exhaustive “possible solutions”, the exhaustive method of “possible solutions” and so on.
In many cases, it is not necessary to pursue a high and complex algorithm structure, but a simple way. Using enumeration method can well avoid the redundancy brought by system complexity, and at the same time, it may reduce the space to a certain extent.
The flow of enumerating ideas can be illustrated in the following figure. The “possible solutions” are determined in advance through implementation, and then verified in the system one by one. According to the verification results, the “possible solutions” are analyzed and demonstrated. This is clearly results-oriented thinking, simply trying to work backwards from the end result to analyze the feasibility of “possible solutions”.
However, the disadvantages of the enumeration idea are also obvious. In actual running programs, few problems can be solved directly by enumeration method. When the screening conditions of “possible solutions” are not clear, the number and range of “possible solutions” cannot be accurately judged, enumeration loses its significance.
However, when the scale of “possible solutions” is relatively small and the process of sequential verification is easy to implement, enumeration is a convenient and fast way. However, the validation of “possible solutions” can be optimized for application scenarios.
This optimization can start from two directions, one is the simplification of the problem, as far as possible to deal with the problem on the model structure of simplification. This reduction can be embodied in the number of variables in the problem, reducing the number of variables and thus radically reducing the combination of “possible solutions”.
Second, strictly judge the scope and conditions of screening “possible solutions” and eliminate most invalid “possible solutions” as much as possible.
That said, in general most scenarios in which enumerations are not available are due to the fact that the number of “possible solutions” is too large to validate all possibilities in a limited space or time. But enumeration is actually the most human way of thinking, and is used more to help us “understand problems” than “solve them.”
case
A hundred dollars for a hundred chickens. The problem is described as follows: chicken weng one, worth five; Chicken mother one, worth three; Chicken chick three, valuable one; A hundred money to buy a hundred chickens, then weng, mother, young geometry?
A cock five dollars, a hen three dollars, three chickens one dollar, now want to use 100 dollars to buy 100 chickens, ask cock, hen, chicken how many?
recursive
Like enumeration thought, recursion thought is close to human thinking mode, and even has more application scenarios than enumeration thought in real life. When the human brain encounters an unknown problem, most people will start from the accumulated “prior knowledge” and try to deduce the “unknown” from the “known”, so as to solve the problem and convince themselves.
In fact, this is the idea of a recursive algorithm. The core of recursion is to calculate the solution of a problem step by step from known conditions. The implementation is much like a series of “because” and “so” on math tests in middle and high school. At that time it was represented by three dots.
For a computer, complex reasoning is hard to do. Computer is good at performing high density and repetitive work, for the randomness of high variable problems but not easy to calculate. The human brain, by contrast, has a greater degree of freedom when deducing problems of different dimensions.
The human brain, for example, can easily derive “the sun rises in the east” from “the sun sets in the west” to roughly derive “the present time.” But it’s not that easy with computers, and you may need to set a number of constraints to avoid the possibility that the computer will “set/fly away/fall” from “south/north/east”.
What I mean by this example is that when computers use recursion, they mostly do repetitive reasoning. For example, from “today is the first” to “tomorrow is the second.” The structure of such reasoning is very similar, and the final solution can often be reached through repeated reasoning.
The idea of recursion is represented graphically in the figure below. The result of each derivation can be used as the beginning of the next derivation, which seems to be similar to the idea of iteration and recursion, but recursion is a bit broader.
case
Rabbit problem. Set a pair of big rabbits can give birth to a pair of little rabbits every month, and each pair of newborn little rabbits can grow into a pair of big rabbits after a month, with reproductive ability, if there is no death, and give birth to a male and female, ask how many pairs of rabbits after a year?
recursive
Say that recursion, have to talk about its brother idea – recursive algorithm. Both of them also have a “pass” word, it can be seen that they still have a certain similarity. “Recursion” can be understood as successive, step by step. In recursion, you go through the problem one by one until you get to the final solution. In recursion, you iterate until you get out of regression.
Recursive algorithm is actually to transform the problem into smaller similar sub-problems, solve the sub-problems first, and then gradually solve higher level problems through the same solving process, and finally obtain the final solution. Therefore, compared with recursion, recursion algorithm has a smaller category and requires the same structure of the subproblem and the parent problem. Recursion has no such constraints conceptually.
In a word to describe the implementation of recursive algorithm, is in the function or sub-process of the internal, directly or indirectly call their own algorithm. Therefore, in the process of implementation, the most important thing is to determine the termination condition of the recursive process, that is, the conditional judgment of the iterative process. Otherwise, the program will loop endlessly in its own invocation, eventually running out of memory and crashing.
A diagram of the recursive algorithm is shown below. Clearly, recursive thinking is a nesting process. The general official is strictly prohibited nesting doll behavior. So in use must be clear “nesting doll” move stop conditions, timely stop loss.
case
Hannotta problem. According to an Indian legend, When Mahama created the world, he built three pillars of steel and stone, one of which was stacked with 64 gold disks from bottom to top. Mahama ordered the Brahmin to rearrange the disks on another pillar, starting from below, in order of size. It is also stipulated that the disk cannot be enlarged on the small disk and that only one disk can be moved at a time between the three columns.
Divide and conquer
Divide and conquer. Divide and conquer.
The core step of divide-and-conquer algorithm is two steps, one is divide, the other is conquer. But this also raises a series of questions, why divide, how to divide, how to treat, after treatment.
Divide-and-conquer algorithm is like a kind of idea of downward management. It divides the sub-tasks into different sub-modules from the highest level, and then it can split the big problems, refine the granularity of system problems, and seek the most basic solution at the bottom level. This idea has been used in many fields, such as the concept of orthogonal coordinates, unit coordinates and bases in geometric mathematics, by simplifying complex problems into basic sub-problems, and then by solving the sub-modules and then gradually solving the main module.
In practical application, the divide-and-conquer algorithm mainly includes two dimensions of processing, one is from top to bottom, the main problem is divided into sub-problems layer by layer; Second, from bottom to top, the solutions of sub-problems are gradually integrated into the solution of the main problem.
Then why split it up? This is easy to explain. Since the scale of major problems is too large to be solved directly, the granularity of major problems needs to be divided.
How about that? In accordance with the repeated operation that computers are best at, sub-problems should be separated from each other and have the same structural characteristics as the original problem, so as to ensure that after solving the sub-problem, the main problem can be solved accordingly.
How to treat? This involves the solution of the most basic subproblem. We agree that the smallest subproblem can be easily solved, so the division of subproblems is meaningful. Therefore, the simple solution of the most basic subproblem is needed in the link of governance.
How’s it going after treatment? The solution of subproblems serves the main problem. When the most basic sub-problem is solved, it is necessary to increase level by level to obtain the solution of higher level problem step by step until the final solution of the original problem is obtained.
A diagram of the idea of divide and conquer can be seen below. The original problem is divided into the smallest sub-problems by the granularity of layers, and then the solutions with higher granularity are obtained. From the top down, and then from the bottom up. Decompose, then solve, then merge.
case
Merge sort.
Dynamic programming
Now, by the end of divide and conquer, we know that the most important thing about divide and conquer is that the subproblems are independent and have the same structural characteristics. Not all problems can be satisfied, and the subproblems of many problems often overlap and affect each other, so it is difficult to use the divide-and-conquer algorithm for effective and clean subproblem division.
So dynamic programming comes in. Dynamic programming also needs to divide the problem into several sub-problems, but the sub-problems are not independent of each other. The solution of the current subproblem can be regarded as a complete summary of the previous problems. Therefore, it is necessary to make multi-stage decisions in the process of solving sub-problems, and the decisions before the current stage can form an optimal substructure. This is called the principle of optimization.
The principle of optimization, an optimization strategy has the property that, regardless of past states and decisions, the remaining decisions must constitute the optimal strategy for the state formed by previous decisions. At the same time, such optimal strategy is a summary of decisions made, and has no direct influence on subsequent decisions, so it can only borrow the status data of the current optimal strategy. This is also known as no aftereffect.
Dynamic programming is an algorithm that is not close to the way of human thinking at present. The main reason is that it is difficult for the human brain to remember the results of every decision in the process of calculation. In the actual operation of dynamic planning, extra space is often needed to save the state data of each stage for the next decision.
The solution idea of dynamic programming is illustrated below. At the beginning of dynamic regression, problems need to be divided into various stages in a certain order, and then the state of each stage is determined, such as F0 of nodes in the figure. Then the emphasis is on determining the state transition equation according to the method of decision making. That is, the state of the next phase needs to be determined according to the state of the current phase.
In this process, the determination of the next state often needs to refer to the previous state. Therefore, the current state variables need to be recorded in the process of each state transition to facilitate subsequent search.
Dynamic programming is mainly used to solve the problem of multi-stage decision-making, but it is often difficult to have a unified approach to practical problems, and must be combined with the characteristics of the problem to design the algorithm, which is also the reason why this algorithm is difficult to really master.
case
Backpack problem. There are n items and a backpack with a capacity of M, giving the weight and value of the item. Solve so that the weight of items into the backpack does not exceed the backpack capacity and maximum value.
greedy
Greedy algorithms, I would call them the most realistic algorithmic ideas.
Living in this world, not every choice can be just right. So many problems, it is impossible to find the optimal solution for all the problems. Many problems have no exact solution at all, or even no solution. So in some situations, it doesn’t make sense to be silly and pursue the most exact solution to a problem.
Some people say, well, there’s an optimal solution. Don’t you want the best solution?
Yes, many problems do not have the most precise solution, but there does exist one or several optimal solutions. But is it necessary to pursue these optimizations? I don’t think so.
The existence of the algorithm is not simply to solve the problem, but to provide a “strategy”. What is “strategy”, a way to solve the problem, an Angle, a way. So greedy thinking is valuable.
Back to greedy algorithms. From the word greedy, we can know that the purpose of this algorithm is to “covet more”. But this kind of greed is “shortsighted”, which leads to greedy algorithms can not start from the long-term, only pay attention to the immediate interests.
To be more specific, greedy algorithms will choose the maximum payoff each time in the execution process, but the total payoff is not necessarily the maximum. So the benefit of this silly sweet thinking is that the choice is easy, there is no need to tangle, no need to think about the future.
The realization process of greedy algorithm is to start from an initial solution of the problem and make the “current best” choice every time until the local extremum point is encountered. The limitation brought by greed is obvious, that is, the final solution cannot be guaranteed to be optimal, and it is easy to fall into the local optimal situation.
However, it is quick to make choices every time, and the judgment conditions are simple, so it can give a similar solution relatively quickly. The diagram here is illustrated by the following diagram.
This graph shows the intersection of multiple lines. Obviously, the line in the figure below does not have a unified intersection, but the optimal solution of the unified intersection can be obtained by an algorithm. If the greedy algorithm is used, the line closest to this position will be selected for update each time during iteration. In this way, after many iterations, the position of the intersection will jump in an infinite circle in a certain area. And this region right here is the approximate optimal region that we can find.
case
Traveling salesman problem. Given a series of cities and the distance between each pair of cities, solve the shortest loop that visits each city once and returns to the starting city.
back
Thick reeds, white dew for frost. The so-called girl, in the water side. Back from the whirl, road resistance and long. Travel back from it, wan in the middle of the water.
Every time I mention the retrospective, I can’t help but think of this poem in “The Time”. When I see my beloved whom I miss in my heart, I cannot help but pursue her against the current, though the road to follow is long and perilous; She continued to search downstream, feeling as if she was in the middle of the river. The process of backtracking algorithm is as difficult and repeated as chasing love, sometimes backing from it, sometimes backtracking from it.
The backtracking algorithm, also known as the heuristic algorithm, does not remind you of being cautious in front of the goddess. Simply put, backtracking is the process of testing every possibility before making a next move. Move forward only when possibilities exist. If all options are impossible, step back and choose again.
In this way, the backtracking algorithm looks a lot like an enumeration algorithm in progress, enumerating and judging all possibilities as it goes along. Common application scenarios are on the tree structure, graph structure and checkerboard traversal.
For a very simple example, look at the diagram below. Assuming that the goal is to go from O0 to O4, all nodes need to be backtracked through the path. The process of backtracking requires testing all possible paths at every step of the way.
For example, there are three paths for O0 node, namely O1 in the upper, middle and lower lines. At the beginning of the process, you go up to O1, and then you can go up to O2, but it’s a dead end. So you have to go back from O2 to O1, and then O1’s only option doesn’t work, so you have to go back from O1 to O0. And then we’re going to test O1 in the middle.
The process of backtracking is to constantly test, judge, back and re-test until a complete path forward is found. However, in this process, restrictions such as “pruning” can reduce the space of exploratory search, so as to avoid repeated ineffective exploratory. For example, the upper and lower O2 nodes have been proved to be infeasible after o0-O1-O2 trials, so there is no need to repeat the trials for O2 starting from O1 next time.
Retrospective thinking can be used effectively in solving many large-scale problems. Backtracking allows you to step through a complex problem so that all possible uses of enumeration ideas can be traversed along the way. In this way, the layers of problem solving can be clearly seen, which helps to better understand the final solution structure of the problem.
case
Eight queen questions. Put 8 queens on an 8×8 chess board so that they cannot attack each other, i.e. no two queens can be in the same row, column, or diagonal line.
simulation
The idea of simulation should not be difficult to understand compared with the above ideas.
In many real scenarios, due to the large scale of the problem, too many variables and other factors, it is difficult to abstract the specific problem, so it is impossible to design the algorithm according to the characteristics of the abstract problem. At this point, simulation might be the best strategy.
The process of simulation is to simulate the real scene as much as possible, and then predict the results through the powerful computing power of the computer. This is a much bigger idea than the algorithm above. In the simulation of real scene, the realization of system components may need the participation of the above algorithm ideas.
Simulation is a very magical idea, there is no specific implementation ideas, there is no specific optimization strategy. Let’s just say it’s a case by case.
So how do we do that graphically. My understanding is custom, arbitrary input, irregular system response, but only in order to obtain a reliable ideal output.
conclusion
The idea of algorithms is, in fact, quite fanciful. The same problem may be implemented with different ideas. These eight ideas are not as independent as you might imagine. Many of them are mixed together, but with different angles and emphases. The above cases do not mean that only one idea can be used to solve, just to experience the corresponding algorithm ideas.
As the bottom programmer, although do not need to brush every day, but the basic algorithm ideas still need some. This kind of thing is not specific to an algorithm, but to a higher level of understanding of the system or requirements.
Like an independent spirit, like a free mind.