recursive algorithm,
exhaustive method,
divide and conquer law,
Backtracking method,
branch and bound method,
dynamic programming,
greedy method
The ideas of each algorithm,
the difference between
as well as
connection between
recursive algorithm
self call
Function calls solve problems by themselves
Have clear termination conditions
Decompose the problem
Break the problem into smaller sub-problems
Sub-problems are independent of each other
recursive tree
Visualizing recursive processes
Show recursive call hierarchy
Exhaustive method (violent method/brute force method)
Simple and direct
try all possible solutions
Suitable for smaller problem sizes
High time complexity
Inefficiency is low when the solution space is large
Not suitable for large-scale problems
full search
Check every possible solution
Make sure you find the optimal solution
divide and conquer
Decompose the problem
Decompose the original problem into several smaller problems of the same type
Recursive solution
Solve each decomposed subproblem recursively
Merge results
Combine solutions to subproblems into solutions to the original problem
applicability
Suitable for problems that can be decomposed into independent sub-problems
Backtracking
Trial and error thinking
try all possible solutions
Roll back when conditions are not met
state space tree
Represent the solution space as a tree structure
Each node represents a state of the problem
Pruning optimization
Eliminate paths that are unlikely to produce optimal solutions
Improve search efficiency
Application scenarios
Solve constraint satisfaction problems
Such as the Eight Queens problem and the coloring problem of graphs
branch and bound method
search strategy
Search the solution space tree according to certain rules
bounded pruning
Use the limit function to prune branches that are unlikely to produce optimal solutions.
Activity selection
Choose the best activity to carry out
Suitable for scheduling problems
The difference from the backtracking method
The branch and bound method focuses more on optimizing the search process
The backtracking method focuses more on finding all feasible solutions
dynamic programming
state transition equation
Describe the relationship between the optimal solution of the problem and the optimal solution of the sub-problem
overlapping subproblems
Subproblems are evaluated multiple times
Use memoization technology to store subproblem solutions
optimal substructure
The optimal solution to a problem contains the optimal solutions to its subproblems
Application scenarios
stock buying and selling problem, knapsack problem
greedy method
local optimal choice
At each step, choose the solution that seems to be the best at the moment.
No backtracking
Once you make a choice, it won't change
Applicable conditions
The problem has greedy choice properties
Greedy selection can produce the global optimal solution
Application scenarios
Minimum spanning tree, Huffman coding
Differences and connections between algorithms
the difference
Different ideological foundations
Recursion based on function calling itself
Exhaustive method based on complete search
Divide and Conquer is based on decomposition and merging
The backtracking method is based on trial and error and pruning
The branch-and-bound method is based on search strategy and bound-and-bound pruning.
Dynamic programming is based on state transfer and memoization
The greedy method is based on local optimal selection
Different application scenarios
Exhaustive method is suitable for small-scale problems
The divide-and-conquer method is suitable for problems that can be decomposed into independent sub-problems
Backtracking method is suitable for constraint satisfaction problems
Branch and bound method is suitable for scheduling problems
Dynamic programming is suitable for problems with overlapping subproblems and optimal substructures
The greedy method is suitable for problems with greedy selection properties.
connect
They are all problem-solving strategies
Each algorithm is designed to solve a specific type of problem
Intersecting application scenarios
Some problems may be solved using more than one algorithm
Inspire each other
The idea of one algorithm may inspire the improvement of another algorithm
Algorithm optimization
Optimize the problem-solving process by combining ideas from different algorithms
Wondershare EdrawMind
