There are n inputs, and its solution consists of a subset of the n inputs. This subset must satisfy certain pre-given conditions. These conditions are called constraints. The solution that satisfies the constraints is called a feasible solution to the problem. . There may be more than one feasible solution that satisfies the constraints. In order to measure the quality of these feasible solutions, certain standards are given in advance. These standards are usually given in the form of functions. These standard functions are called objective functions, which make the objective function achieve an extreme value. The feasible solution (maximum or minimum) is called the optimal solution, and this type of problem is called an optimization problem.

For an optimization problem with n inputs, the solution process can often be divided into several stages. The decision-making in each stage only depends on the state of the previous stage. The actions taken by the decision-making make the state transfer and become the next stage. basis for stage decisions. Thus, a sequence of decisions is generated in a constantly changing state. The process resulting from this decision sequence is called a multi-stage decision-making process

For problems that are suitable to be solved by dynamic programming methods, the sub-problems obtained after decomposition are often not independent of each other. Unlike divide and conquer.

During the solution process, the solutions to the solved subproblems are saved and can be easily retrieved when needed. This avoids a large number of meaningless repeated calculations, thereby reducing the time complexity of the algorithm.

How to save the solution of the solved sub-problem? Usually in the form of a table, that is, in the actual solution process, once a certain sub-problem is calculated, regardless of whether the problem will be used in the future, the calculation results will be filled in the table, and the sub-problem will be found from the table when needed. The solution to the problem, the specific dynamic programming algorithms are diverse, but they have the same form filling format

Analyze the properties of the optimal solution and characterize the structural characteristics of the optimal solution—examine whether it is suitable to use dynamic programming method

Recursively define optimal values ​​(i.e. establish recursive or dynamic programming equations)

Calculate the optimal value in a bottom-up manner and record relevant information

Construct the optimal solution based on the information obtained when calculating the optimal value

Optimal substructure properties

Features: The order of the calculation matrix sub-chains A[i:k] and A[k 1:j] included in the optimal order of calculating A[i:j] is also optimal.

The optimal solution to the matrix multiplication calculation order problem contains the optimal solution to its sub-problems. This property is called the optimal substructure property. The optimal substructure property of a problem is a significant feature of the problem that can be solved by dynamic programming algorithms.

The design idea of ​​the divide-and-conquer method is to divide a large problem that is difficult to solve directly into a number of smaller identical problems so that they can be solved individually and divided and conquered.

Divide a large problem that is difficult to solve directly into some smaller sub-problems so that they can be solved individually and divide and conquer.

Then merge the solutions of the sub-problems into the solution of a larger problem, and gradually find the solution to the original problem from the bottom up.

The problems that can be solved by the divide and conquer method generally have the following characteristics:

The problem can be easily solved when the scale of the problem is reduced to a certain extent; the problem can be decomposed into several smaller problems of the same size, that is, the problem has optimal substructure properties.

The solutions to the sub-problems decomposed using this problem can be merged into the solution of this problem

The sub-problems decomposed into this problem are independent of each other, that is, there are no common sub-problems between the sub-problems.

This feature involves the efficiency of the divide-and-conquer method. If each sub-problem is not independent, the divide-and-conquer method will have to do a lot of unnecessary work and repeatedly solve common sub-problems. Although the divide-and-conquer method can also be used at this time, it is generally Dynamic programming is better

divide

Solve subproblems

merge

How to divide it, that is, how to reasonably decompose the problem?

How to cure, that is, how to solve the problem

The key to the problem - discovering the regularity in the process of making the round-robin schedule

The divide and conquer strategy of quick sort is

Divide-and-conquer strategy of quick sort algorithm

The greedy method is short-sighted in problem-solving strategies and always makes the best choice at the moment. And once a choice is made, no matter what the consequences are in the future, this choice will not change. In other words, the greedy method does not consider the overall optimal, but the choice it makes is only a local optimal in a certain sense.

When the optimal solution of a problem contains the optimal solutions of its subproblems, the problem is said to have optimal substructure properties, and it is also said that the problem satisfies the principle of optimality.

The so-called greedy selection property means that the overall optimal solution to the problem can be obtained through a series of local optimal choices, that is, greedy selection (only make the best choice in the current state)

Candidate set C: In order to construct a solution to the problem, there is a candidate set C as a possible solution to the problem, that is, the final solution to the problem is taken from the candidate set C. For example, in a payment problem, currencies of various denominations form the candidate set.

Solution set S: As the greedy selection proceeds, the solution set S continues to expand until it forms a complete solution that satisfies the problem. For example, in the payment problem, the money paid constitutes the solution set.

Solution function: Checks whether the solution set S constitutes a complete solution to the problem. For example, in a payment problem, the solution function is that the monetary amount paid exactly equals the amount due

Selection function select: that is, the greedy strategy. This is the key to the greedy method. It points out which candidate object is most promising to form a solution to the problem. The selection function is usually related to the objective function. For example, in the payment problem, the greedy strategy is to choose the currency with the largest denomination in the candidate set.

Feasible function: Check whether it is feasible to add a candidate object to the solution set, that is, whether the constraint conditions are satisfied after the solution set is expanded. For example, in the payment problem, the feasible function is that the sum of the currency selected and the currency paid at each step does not exceed the amount due

greedy choice property

Optimal substructure properties

The leaf with a large weight is closest to the root (characters with high frequency have short codes)

It can be seen from the idea of ​​​​the algorithm that if the number of edges in the graph G is small, Kruskal can be used, because the Kruskal algorithm finds the shortest edge each time; if the number of edges is large, the Prim algorithm can be used, because it adds one vertex each time. It can be seen that Kruskal is suitable for sparse graphs, while Prim is suitable for dense graphs.

In terms of time, the time complexity of Prim's algorithm is O(n2), and the time complexity of Kruskal's algorithm is O(eloge).

In terms of space, it is obvious that in Prim's algorithm, only a small space is needed to complete the algorithm, because each scan starts from an individual point, and each scan only scans the edges corresponding to the current vertex set. . But in the Kruskal algorithm, because you have to know where the edge with the smallest weight in the current edge set is at all times, you need to sort all the edges. For a very large graph, the Kruskal algorithm takes up much more space than the Prim algorithm. Space.

Refers to a description of the steps to solve a specific problem, which is a finite sequence of several instructions.

characteristic

natural language

graphics

programming language

advantage

shortcoming

pseudocode

Fully understand the problem to be solved

mathematical model formulation

Algorithm detailed design

Algorithm Description

Verification of correctness of algorithmic ideas

Analysis of Algorithms

Computer implementation and testing of algorithms

Preparation of documentation

Estimate the two computer resources required by the algorithm - time and space

Purpose

Algorithm complexity = the amount of computer resources required to run an algorithm

1. Decide which parameter(s) to use as a measure of algorithmic problem size

2. Find the basic statements in the algorithm

3. Check whether the number of executions of basic statements depends only on the problem size

4. Establish a summation expression for the number of execution times of basic statements

5. Represent this summation expression in asymptotic notation

A subroutine (or function) calls itself directly or indirectly through a series of calling statements, which is called recursion.

An algorithm that calls itself directly or indirectly is called a recursive algorithm

General steps for solving problems using recursive algorithms: