Shulou(Shulou.com)06/01 Report--

This article focuses on "what are the Python algorithms", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "what are the Python algorithms?"

1 enumeration

First of all, the simplest idea is the enumeration algorithm. Enumeration is also called exhaustive enumeration, which, as the name implies, is exhaustive enumeration. The application scenario of enumeration idea is very extensive and easy to understand. To put it simply, enumeration is to enumerate the possible solutions of the problem in turn, and then bring them into the test of the problem one by one, so as to obtain the exact solution that can solve the problem from a series of possible solutions.

Although enumerations may seem simple, there are still some considerations that are easy to overlook. For example, the screening conditions of the "possible solution / candidate solution" of the problem to be solved, the mutual influence of the "possible solution", the cost of enumerating the "possible solution", the exhaustive way of the "possible solution" and so on.

In many cases, there is no need to pursue high-end and complex algorithm structure, but the main road to simplicity, the use of enumeration method can well avoid the redundancy caused by system complexity, and may also be able to reduce space to a certain extent.

The flow of enumerating ideas can be represented by the following figure. Through the realization, the "possible solution" is determined in advance, and then verified in the system one by one, and the "possible solution" is analyzed and demonstrated according to the verification results. This is an obvious result-oriented idea, which simply and rudely attempts to reverse the feasibility of the "possible solution" from the final result.

However, the disadvantages of enumerating ideas are also obvious. In the actual running program, there are very few problems that can be solved directly by enumerating methods. When the filter condition of "possible solution" is not clear, so that the number and range of "possible solution" can not be judged accurately, enumeration loses its meaning. However, when the scale of "possible solution" is relatively small and the process of sequential verification is easy to implement, the idea of enumeration is a convenient and fast way. However, in the specific use, the verification of the "possible solution" can also be optimized for the application scenario. This optimization can start from two directions: one is the simplification of the problem, and the model structure of the problems that need to be dealt with can be simplified as much as possible. This simplification can be specifically reflected in the number of variables in the problem and reduce the data of variables, thus fundamentally reducing the combination of "possible solutions". The second is to strictly judge the scope and conditions of screening "possible solutions" and eliminate most of the invalid "possible solutions" as much as possible. That said, generally speaking, most scenarios where enumerations are not available are due to too many "possible solutions" to verify all possibilities in limited space or time. But in fact, enumeration is the closest way of thinking to people, and it is more often used to help us "understand problems" than to "solve problems".

Case study: the problem of buying a hundred chickens for a hundred dollars. In translation, it means five yuan for a rooster, three yuan for a hen, and one yuan for three chicks. Now we have to buy one hundred chickens with one hundred yuan. How many cocks, hens and chicks are each?

2 recursion

Recursive thought, like enumeration thought, is close to the human way of thinking, and even has more application scenarios than enumeration thought in real life. When the human brain encounters unknown problems, most people's first intuition 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 a recursive algorithmic idea. The core of recursive thinking is to gradually calculate the solution of the problem from the known conditions. The way of realization is very similar to a series of "because" and "so" on our math papers in junior and high school. At that time, it was expressed by three points.

As far as computers are concerned, complex derivation is actually very difficult to achieve. Computers are good at performing tasks with high density and high repetition, but it is difficult to calculate problems with high randomness and variety. In contrast, the human brain has a higher degree of freedom in deducing the problems of different dimensions.

For example, the human brain can easily derive "the sun sets from the west" from "the sun rises in the east" and then roughly "the present time". But it's not that easy for a computer, and you may need to set a series of restrictions to avoid the possibility that the computer will "set / fly away / fall" from the "south / north / east".

The purpose of this example is to show that when computers use recursive ideas, they are mostly repetitive reasoning. For example, the launch of "tomorrow is the 2nd" from "Today is No.1". The structure of this kind of reasoning is very similar, and the final solution can often be obtained through subsequent reasoning.

The idea of recursion is illustrated as shown in the following figure. 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 the scope of recursion is broader.

Case: rabbit problem. It is determined that a pair of big rabbits can give birth to a pair of little rabbits every month, and each pair of newborn rabbits can grow into a pair of big rabbits after a month and have the ability to reproduce. If there is no death, and each time a female and a male are born, how many pairs of rabbits will there be a year later?

3 recursion

After talking about recursion, we have to talk about its brotherly thought-recursive algorithm. Both of them also have the word "delivery", which shows that they still have some similarities. The understanding of "delivery" can be step by step. In recursion, the problem is deduced one by one until the final solution is obtained. In recursion, it is a successive regression iteration until it jumps out of the regression.

In fact, the recursive algorithm transforms the problem into a smaller sub-problem of the same kind, first solves the sub-problem, and then gradually solves the higher-level problem through the same solving process, and finally obtains the final solution. Therefore, compared with recursion, the scope of the recursive algorithm is smaller, and the structure of the subproblem is the same as that of the parent problem. Recursive thinking has no such constraint conceptually.

To describe the implementation of a recursive algorithm in one sentence is to call your own algorithm directly or indirectly inside a function or subprocedure. Therefore, in the process of implementation, the most important thing is to determine the conditions for the termination of the recursive process, that is, the condition judgment for the iterative process to jump out. Otherwise, the program will loop indefinitely in the self-call, resulting in a memory overflow and crash.

The diagram of the recursive algorithm can be shown in the following figure. Obviously, recursive thinking is actually a process of nesting dolls. Generally speaking, the nesting of dolls is strictly prohibited by the authorities. Therefore, when in use, we must make clear the stop conditions of the "doll" action and stop the loss in time.

Case: the Tower of Hanoi problem. According to Indian legend, when Brahma created the world, he built three diamond pillars, one of which folded 64 gold discs from the bottom up. Brahma ordered the Brahmin to rearrange the disc on another pillar in order of size from below. It is also stipulated that the disk cannot be enlarged on the small disc and can only be moved one disk at a time between the three columns.

4 divide and cure

Divide and rule.

The core step of the divide-and-conquer algorithm is two steps, one is division, the other is treatment. But this also leads to a series of questions, why, how to divide, how to treat, and how to treat it.

The divide-and-conquer algorithm is very similar to the idea of downward management, which divides the sub-tasks into different sub-modules from the highest level, and then divides the big problems, refines the granularity of the system problems, and seeks the most basic solution at the bottom. This idea has been used in many fields, such as the concepts of orthogonal coordinates, unit coordinates and bases in geometric mathematics, by simplifying complex problems into basic sub-problems, and then solving the main module step by step.

In practical application, the divide-and-conquer algorithm mainly includes two dimensions: one is from top to bottom, the main problem is divided into sub-problems level by level; the other is from the bottom up, the solution of the sub-problem is gradually integrated into the solution of the main problem.

Then why split it? This is easy to explain, because the scale of the main problem is too large to be solved directly, so it is necessary to divide the granularity of the main problem.

How do you divide it? In accordance with the repeated operation that the computer is best at, the divided sub-problems need to be independent of each other and have the same structural characteristics as the original problem, so that after solving the sub-problem, the main problem can be solved.

How to treat it? This involves the solution of the most basic sub-problem, we agree that the smallest sub-problem can be easily solved, such a sub-problem division is meaningful, so in the treatment of the link is the need for the most basic sub-problem simple solution.

How's it going after treatment? The solution of the sub-problem serves for the main problem. When the most basic sub-problem is solved, it needs to increase layer by layer, and gradually obtain the solution of the higher-level problem, until the final solution of the original problem.

The illustration of the idea of partition and rule can be seen in the following figure. Through the division of layer by layer granularity, the original problem is divided into the smallest sub-problem, and then the higher granularity solution is obtained in turn. From the top down, and then from the bottom up. First decompose, then solve, then merge.

Case: merge and sort.

5 dynamic programming

After talking about divide-and-conquer, we know that the most important point of divide-and-conquer thought is that the sub-problems are independent of each other and have the same structural characteristics. Not all problems can be satisfied, and the sub-problems of many problems often overlap and influence each other, so it is difficult to use divide-and-conquer algorithm to divide the sub-problems effectively and cleanly.

As a result, dynamic planning came. Dynamic programming also needs to divide the problem into multiple sub-problems, but the sub-problems are often not independent of each other. The solution of the current sub-problem can be regarded as a complete summary of the previous stage problems. Therefore, it is necessary to make multi-stage decisions in the process of solving the sub-problem, and the decisions before the current stage can form an optimal substructure. This is the so-called optimization principle.

According to the optimization principle, an optimization strategy has the property that regardless of the past state and decision-making, the remaining decisions must constitute the optimal strategy for the state formed by the previous decision. At the same time, this optimal strategy is a summary of the decisions that have been made, has no direct impact on the subsequent decisions, and can only borrow the state data of the current optimal strategy. This is also called no aftereffect.

Dynamic programming is an algorithm that is not very close to the human way of thinking at present, the main reason is that it is difficult for the human brain to remember the results of each decision in the process of calculus. In the actual operation, dynamic planning often needs extra space to save the state data of each stage, so that it can be used in the next decision.

The solution of dynamic programming is illustrated as follows. The beginning of dynamic regression needs to divide the problem into stages in a certain order, and then determine the state of each stage, such as the F0 of the nodes in the figure. Then the key point is to determine the state transition equation according to the decision-making method. 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, it is necessary to record the current state variables 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 method in practical problems, and the algorithm must be designed according to the characteristics of the problem, which is the reason why this algorithm is difficult to master.

Case

Backpack problem. There are n items and a backpack with a capacity of m, giving the weight and value of the items. Solve the problem so that the weight of the items in the backpack does not exceed the capacity of the backpack and the value is maximum.

6 greed

Greedy algorithm, I would like to call it the most realistic algorithm idea.

When people live in the world, it is impossible for every choice to be just right. With so many problems, it is impossible to find the optimal solution to all the problems. Many problems have no accurate solution at all, or even no solution at all. So in some scenarios, it makes no sense to foolishly pursue the most accurate solution to the problem.

Some people say that there is an optimal solution. Don't you want the best solution?

Yes, although many problems can not find the most accurate solution, but there will be one or some optimal solutions. But do we have to pursue these optimal solutions? I don't think so.

The existence of the algorithm is not only to solve the problem, but also to provide a "strategy". What is meant by "strategy" is a way, an angle and a way to solve the problem. Therefore, greed is valuable.

Back to the greedy algorithm. From the word greed, we can see that the purpose of this algorithm is to "covet more". But this greed is "short-sighted", which leads to the greedy algorithm can not start from the long-term, only focus on the immediate interests.

Specifically, in the process of implementation, the greedy algorithm will choose the maximum benefit each time, but the total benefit is not necessarily the largest. So the advantage of such a silly and sweet way of thinking is that the choice is simple, there is no need to struggle, there is no need to think about the future.

The implementation process of greedy algorithm is to start from an initial solution of the problem and make the "current optimal" choice every time until it meets the local extreme point. The limitation caused by greed is obvious, that is, there is no guarantee that the final solution is optimal, and it is easy to fall into the local optimal situation.

But it makes a fast choice each time, and the judgment condition is simple, so it can give a similar solution more quickly. I use the following picture to show the diagram here.

This graph represents the solution of the intersection of multiple lines. Obviously, there is no unified intersection of the lines in the following figure, but the optimal solution of the unified intersection can be obtained by the algorithm. If the greedy algorithm is used, then each iteration will select the line closest to this position to be updated. In this way, after many iterations, the position of the intersection will jump infinitely in a certain area. And this region is the approximate optimal solution region that can be obtained.

Case

Travel salesman problem. Given the distance between a series of cities and each pair of cities, solve the shortest path to visit each city once and return to the starting city.

7 backtracking

The backtracking algorithm, also known as the heuristic algorithm, reminds you of your caution in front of the goddess. To put it simply, the process of backtracking is to explore each possibility before making the next choice; move forward only when the possibility exists, and if none of the options are possible, then go back to the original position and choose again.

In this way, the backtracking algorithm is very much like an ongoing enumeration algorithm, enumerating and judging all possibilities in the process of traveling. The common application scenarios are the traversal of tree structure, graph structure and pieces on the chessboard.

To give a very simple example, see the following illustration. Assuming that the goal is to travel from the most O0 to O4, all nodes need to be traversed backwards. Then the process of the backtracking algorithm needs to explore all possible paths at each step forward.

For example, there are three paths for the O0 node to move forward, which are the O1 of the upper, middle and lower bars. At the beginning of the backtracking process, first go to the top O1, and then you can reach the upper O2, but this is a dead end. Then you need to go back from O2 to O1, and the only option for O1 doesn't work, so you also need to go back from O1 to O0. Then continue to test O1 in the middle.

The process of backtracking algorithm is to continue to test, judge, return and re-explore until a complete path is found. However, in this process, the space for trial search can be reduced through restrictions such as "pruning", so as to avoid repeated and invalid temptations. For example, the upper and lower O2 nodes, after the trial of O0-O1-O2, have verified that the node is not feasible, and there is no need to repeat the O2 test from O1 next time.

The idea of backtracking can be effectively used in solving many large-scale problems. Backtracking can adjust complex problems step by step, so that all possible enumeration ideas can be traversed in the middle process. In this way, we can often see the level of problem solving clearly, which can help to better understand the final solution structure of the problem.

Case

The question of eight queens. Put eight queens on an 8 × 8 chess game so that they can't attack each other, that is, no two queens can be in the same row, the same column or the same slash. Ask how many pendulums there are.

8-module simulation

The understanding of simulation ideas should not be difficult 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 time, simulation thought may be the best problem-solving 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 more ambitious idea than the above algorithm. In the simulation of the real scene, the implementation of the system components may need the participation of the above algorithms.

Simulation is a very illusory idea, there is no specific implementation ideas, and there is no specific optimization strategy. It can only be said that the specific problems are analyzed in detail.

How should it be illustrated? My understanding is custom, arbitrary input, irregular system response, but only to get a reliable and ideal output.

At this point, I believe you have a deeper understanding of "Python algorithm", you might as well come to the actual operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.