Five commonly used algorithms

Five commonly used algorithms

1. Greedy algorithm

The greedy algorithm can obtain the local optimal solution to the problem, but may not necessarily obtain the global optimal solution. At the same time, the quality of obtaining the optimal solution depends on the choice of the greedy strategy. The characteristic is that it is simple and can obtain local optimal solutions. Just like the dog-beating stick method, the level of Hong Qigong and Lu Youjia is very different for the same set of stick methods. Therefore, it is also a greedy algorithm, and different greedy strategies will lead to very different results.

2. Dynamic programming algorithm

When the optimization problem has repeated sub-problems and optimal sub-structures, it is time for dynamic programming to appear. The core of the dynamic programming algorithm is to provide a memory to cache the results of repeated subproblems, avoiding a large number of repeated calculations in the recursive process. The difficulty of dynamic programming algorithm is how to transform the problem into one that can be solved by dynamic programming algorithm. When the number of repeated subproblems is small, the effect of dynamic programming will be poor. If the problem has a large number of repeated sub-problems, then dynamic programming is very terrible for improving efficiency. Just like martial arts, if the opponent is strong, it will be stronger; if the opponent is stronger, it will be weaker.

3. Divide and Conquer Algorithm

The logic of the divide and conquer algorithm is simpler. It is just one word, divide and conquer. The divide-and-conquer algorithm divides a large problem into several sub-problems, and then continues to divide the sub-problems downwards, all the way to the base cases. Through the solution of the base cases, step by step, the original big problem is finally solved. The divide-and-conquer algorithm is a typical application of recursion.

4. Backtracking algorithm

The backtracking algorithm is a typical application of the depth-first strategy. The backtracking algorithm goes down a path. If the path is different, then backtrack. Go to the previous

branching road, choose a way to go, and keep recursing like this until all paths are traversed. The Eight Queens problem is a classic problem of backtracking algorithm, and another classic application scenario is the maze problem.

5. Branch-and-bound algorithm

The backtracking algorithm is depth-first, so the branch-and-bound method is a classic example of breadth-first. Generally speaking, the backtracking method traverses the entire solution space to obtain all solutions to the problem, while the branch-and-bound method is to obtain one solution (generally speaking, to obtain the optimal solution).

Recommended tutorial: "PHP Tutorial"

The above is the detailed content of Five commonly used algorithms. For more information, please follow other related articles on the PHP Chinese website!