Common algorithm design strategies:
1. Divide and Conquer
The design idea of the divide and conquer method is to divide a A large problem that is difficult to solve directly is divided into k smaller sub-problems. These sub-problems are independent of each other and the same as the original problem, and then each is broken down to divide and conquer.
The divide-and-conquer method is often used in conjunction with recursion: by repeatedly applying divide-and-conquer, the sub-problem can be made consistent with the original problem type and continuously reduced in size. Eventually, the sub-problem can be reduced to the point where it is easy to find its solution. Naturally leads to recursive algorithms.
2. Dynamic programming
The dynamic programming method is similar to the divide-and-conquer method. Its basic idea is to decompose the original problem into several sub-problems. Unlike the divide-and-conquer method, the sub-problems decomposed are often not independent of each other. In this case, using the divide-and-conquer method will solve some sub-problems multiple times, which is obviously unnecessary. The dynamic programming method saves the answers to all solved sub-problems during the solution process, thereby avoiding repeated solving of sub-problems.
Dynamic programming is often used to solve optimization problems. Whether dynamic programming can be applied to an optimization problem depends on whether the problem has the following two properties:
Optimal substructure properties:
When the optimal solution of the problem contains its subproblems When the optimal solution of , the problem is said to have optimal substructure properties.
The overlapping nature of sub-problems:
The overlapping nature of sub-problems means that the sub-problems decomposed from the original problem are not independent of each other and overlap.
3. Greedy
When a problem has optimal substructure properties, it can be solved by dynamic programming. But sometimes there is an algorithm that is simpler, more direct and more efficient than dynamic programming - the greedy method. The greedy method always makes the best choice at the moment, which means that the greedy method does not consider the overall optimal choice. The choice it makes is only a local optimal choice in a certain sense.
4. Backtracking
The backtracking method is to perform a depth-first search on the solution space tree of the problem, but before performing DFS on each node, the node must first be judged. Is it possible to contain a solution to the problem. If it is definitely not included, skip the search for the subtree rooted at this node and backtrack to its ancestor nodes layer by layer. If it is possible to contain it, enter the subtree and perform DFS.
5. Branch and Bound
The search strategy of the branch and bound method is to first generate all its child nodes (branch) at the current node, and for each The child nodes that satisfy the constraint conditions calculate a function value (bound), and then all the child nodes that satisfy the constraint conditions are added to the live node priority queue of the solution space tree. Then select the node with the highest priority from the current live node priority queue (the priority of the node is determined by the value of its limit function) as the new current node. This process is repeated until a leaf node is reached. The leaf node reached is the optimal solution.
The above is the detailed content of What are the commonly used algorithm design strategies?. For more information, please follow other related articles on the PHP Chinese website!