2. Data processing algorithms, such as data fitting, parameter estimation and interpolation. There are usually a lot of data to be processed in the competition, and the key to processing data lies in these algorithms, usually using MATLAB as a tool.
3. Programming algorithms, such as linear programming, integer programming, multivariate programming and quadratic programming. Most of the problems in modeling competition belong to optimization problems, and many times these problems can be described by mathematical programming algorithms, usually solved by Lindo and Lingo software.
4. Graph theory algorithm. This kind of algorithm can be divided into many kinds, including shortest path algorithm, network flow algorithm, bipartite graph algorithm and so on. Problems related to graph theory can be solved by these methods and need careful preparation.
5. Computer algorithms, such as dynamic programming, backtracking search, divide and conquer algorithm, branch and bound. These algorithms are commonly used in algorithm design and will be used in many occasions in competitions.
6. Three non-classical algorithms of optimization theory: simulated annealing algorithm, neural network algorithm and genetic algorithm. These problems are used to solve some difficult optimization problems and are very helpful to some problems, but the algorithm is difficult to implement and needs to be used carefully.
7. Grid algorithm and exhaustive method. Both of them are the best algorithms for brute force search, and they are applied in many competition questions. When we focus on the model itself and despise the algorithm, we can use this brute force scheme, and it is best to use some high-level languages as programming tools.
8. Several discretization methods of continuous data. Many problems are practical, data can be continuous, and computers can only handle discrete data, so it is very important to discretize them and implement the ideas of difference instead of differential and summation instead of integral.
9. Numerical analysis algorithm. If high-level language programming is used in the competition, the commonly used algorithms in numerical analysis, such as solving equations, matrix operation, function integration, etc., need to write additional library functions to call.
10. Image processing algorithm. There is a kind of problem related to graphics in the competition. Even if the problem has nothing to do with graphics, the paper will need pictures to illustrate the problem. How to display these graphics and how to deal with them are problems that need to be solved, which are usually handled by MATLAB.
The following will explain these ten algorithms in detail in combination with the competition questions over the years.
The following will explain these ten algorithms in detail in combination with the competition questions over the years.
2 Detailed description of ten algorithms
2. 1 Monte Carlo algorithm
Most modeling competitions are inseparable from computer simulation, and random simulation is one of the most common algorithms.
For example, in question A of 1997, each part has its own calibration value and tolerance grade, so solving the optimal combination scheme will face extremely complicated formulas and 108 tolerance selection schemes, and it is impossible to find an analytical solution. How to find the best solution? Stochastic simulation and finding the optimal scheme is one of the methods. In the feasible range of each part, a calibration value and a tolerance value are randomly selected as schemes according to normal distribution, and then a large number of schemes are simulated by Monte Carlo algorithm to select the best scheme. Another example is the second question in last year's lottery, which requires a better plan. First of all, the quality of the scheme depends on many complicated factors, and it can not be solved by depicting a model, so it can only be simulated by random simulation.
2.2 data fitting, parameter estimation, interpolation and other algorithms
Data fitting is applied in many games, and many problems related to graphics processing are related to fitting. An example is 1998 American game A, the three-dimensional interpolation processing of biological tissue slices, the interpolation calculation of mountain peak altitude in 1994 A game, and the noisy SARS problem that may be tested in the exam. Data fitting algorithm should also be used to observe the trend of data for processing. For this kind of problem, there are many ready-made functions in MATLAB that can be called. If you are familiar with MATLAB, these methods can be used very well.
2.3 Programming class problem algorithm
Many problems in the competition are related to mathematical planning. It can be said that many models can be reduced to a set of inequalities as constraints and several function expressions as objective functions. The key to such problems is to solve them. For example, question B of 1998 can be clearly described by many inequalities. Therefore, it is convenient to use software such as Lindo and Lingo to solve the plan after listing, so you need to be familiar with these two softwares.
2.4 Graph theory problems
The problem of 98 B, 00 B and 95 locking boxes reflects the importance of graph theory. There are many algorithms for this kind of problem, including Dijkstra, Floyd, Prim, Bellman-Ford, maximum flow, binary matching and so on. Every algorithm must be implemented once, otherwise it will be too late to write in the game.
2.5 Problems in computer algorithm design
Computer algorithm design includes many contents: dynamic programming, backtracking search, divide-and-conquer algorithm, branch and bound. For example, 1992, question b is a branch and bound method; 1997, problem b is a typical dynamic programming problem; In addition, the problem B of 1998 embodies the divide-and-conquer algorithm. The problems in this respect are similar to those in the ACM programming contest. It is recommended to read books related to computer algorithms such as Computer Algorithm Design and Analysis (Electronic Industry Press).
2.6 Three non-classical algorithms of optimization theory
In recent ten years, the optimization theory has developed rapidly, and three kinds of algorithms, simulated annealing method, neural network and genetic algorithm, have developed rapidly. In recent years, the competition questions have become more and more complicated, and there are no good models for many problems to learn from, so these three kinds of algorithms can often come in handy, for example, the simulated annealing algorithm for 97 A question, the neural network classification algorithm for 00 B question, and the neural network can also be used for such difficult problems as 0 1 B question. The 89 A question in the American competition is also related to the BP algorithm just proposed in 1986 and 1989. The Gamma Knife problem of Question B in 2003 is also a current research topic, and the best algorithm at present is genetic algorithm.
2.7 grid algorithm and exhaustive algorithm
The grid algorithm is the same as the exhaustive method, except that the grid method is an exhaustive method for continuous problems. For example, if the optimization problem requires n variables, then select the space where these variables are desirable, such as in [a; B] Take the interval M+1 point as a; a+(b-a)/M； a+2(b-a)/M； …… ; B Then this loop needs to be operated (M+ 1)N times, so the amount of calculation is very large. For example, question A in 1997 and question B in 1999 can be searched by grid method, which is better with faster operation speed.
In the computer, there are high-level languages to do, and it is best not to use MATLAB to make grids, otherwise it will take a long time. Everyone is familiar with the exhaustive method, so I won't talk about it.
2.8 Some methods of discretization of continuous data
The programming solutions of most physical problems are related to this method. Physical problems reflect that we live in a continuous world, and computers can only deal with discrete quantities, so we need to deal with continuous quantities discretely. This method is widely used and related to many of the above algorithms. In fact, grid algorithm, Monte Carlo algorithm and simulated annealing all use this idea.
2.9 Numerical analysis algorithm
This algorithm is specially designed for high-level languages. If you use MATLAB and Mathematica, you don't need to prepare, because there are many functions in numerical analysis.
2. 10 image processing algorithm
0 1, you need to be able to read BMP images. 1998, in the United States, you need to be able to calculate three-dimensional interpolation. In 2003, Question B was more demanding, not only programming calculation but also processing. There are many pictures to be displayed in digital and analog papers, so image processing is the key. To do this kind of problems well, it is very important to learn MATLAB well, especially the image processing part.