Wondershare EdrawMind
MindMap Gallery Introduction to Algorithms
- 26
Introduction to Algorithms
Introduction to algorithms, if for a certain constant e>0, f(n)=O(n^log_b(a-e)), then T(n)=/Theta(n^log_b(a)), if f(n) =/Theta(n^log_b(a)), then T(n)=/Theta(n^log_b(a)logn).
Edited at 2022-11-10 10:24:33
- Avatar Character Relationship Chart
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
- Zootopia 2 Easter Egg
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
- Zootopia 2 Character Relationship Chart
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
Introduction to Algorithms
- Avatar Character Relationship Chart
Avatar 3 centers on the Sully family, showcasing the internal rift caused by the sacrifice of their eldest son, and their alliance with other tribes on Pandora against the external conflict of the Ashbringers, who adhere to the philosophy of fire and are allied with humans. It explores the grand themes of family, faith, and survival.
- Zootopia 2 Easter Egg
This article discusses the Easter eggs and homages in Zootopia 2 that you may have discovered. The main content includes: character and archetype Easter eggs, cinematic universe crossover Easter eggs, animal ecology and behavior references, symbol and metaphor Easter eggs, social satire and brand allusions, and emotional storylines and sequel foreshadowing.
- Zootopia 2 Character Relationship Chart
[Zootopia Character Relationship Chart] The idealistic rabbit police officer Judy and the cynical fox conman Nick form a charmingly contrasting duo, rising from street hustlers to become Zootopia police officers!
- Recommended to you
- Outline
Introduction to Algorithms
maximum flow problem
streaming network
Nodes represent cities
Directed edges represent the direction of transportation paths and logistics
The weight represents the traffic limit
network convention
Flow conservation
Unlimited resources, limited only by path traffic
standard flow network
No anti-parallel edges/anti-parallel edges
Only a single source and sink
Non-standard flow networks can be converted to standard form
Have antiparallel sides
Multiple sources/sinks
Related definitions
Actual flow f(u,v)
Capacity function c(u,v)
Algorithm implementation
Ford-Fulkerson method
residual network
Unused traffic is marked as forward edges
Used traffic is marked as a reverse edge
Sending traffic to the reverse edge in the remaining network is equivalent to reducing traffic in the original network. This is called an offset operation.
augmenting path
The maximum traffic that can be increased on an augmented path becomes the remaining capacity of the path
The remaining capacity is equal to the minimum remaining capacity of all edges on the path.
Constantly search for augmentation paths in the new residual network to increase the residual capacity
Maximum Flow Minimum Cut Theorem
Cutting of streaming network
Cutting capacityc
Calculation: only consider positive capacity
Flow f
Calculation: forward flow minus reverse flow
minimum cut
For any cut in a flow network, the net flow on the cross-section is equal to the flow of the network
The value of any flow f in the flow network G cannot exceed the capacity of any cut of G.
The maximum flow value is equal to the minimum cutting capacity
Equivalent description
There is no longer an augmenting path (sink t in the remaining network is unreachable)
Proof: proof by contradiction
Algorithm implementation
Initialization: The initial flow of each edge is set to 0 (with built-in capacity function c)
Find the augmenting path: DFS/BFS
After finding the augmenting path, find the minimum edge and perform the operation
Add positive edge
Reduce reverse edges
time complexity
Edmonds-Karp algorithm
time complexity
Application: Maximum bipartite matching
match
maximum match
Convert to flow network
Add a source point to the left side of the original image and connect the source point to all points on the left side
Add a sink point on the right side of the original image and connect the sink point to all points on the right
Define the capacity on each edge as unit capacity 1
Solve the maximum flow problem
Use the Ford-Fulkerson algorithm to find the maximum flow in G'
The edges with a flow value greater than 0 and in the original graph will constitute the maximum matching, and the number of edges with the maximum matching is the flow value of the maximum flow.
prove
Prove that there is a one-to-one correspondence between matching and flow in the original image and the converted flow network, and the number of matching edges corresponds to the flow value (|f|=|M|)
A bipartite graph is a bipartite cut, and the edges in M are exactly the edges across the cut, and there is a unit of flow on it. Therefore, the net flow value of the cut is the flow value of f, and the net flow value of the cut is equal to the number of matching edges.
It is proved that under the premise that the capacity is an integer, the stream generated by the Ford-Fulkerson method is an integer stream, thus ensuring that the stream calculated by the algorithm can be restored to match the original image.
Prove that the flow value of the largest flow is equal to the cardinality of the largest matching
Johnson algorithm
Summary: Different shortest path algorithms
Floyd-Warshall algorithm: n^3
Execute |V| times single source shortest path algorithm
Dijkstra's algorithm
Bellman-Ford algorithm
Johnson algorithm
working principle
Johnson's algorithm uses Dijkstra's algorithm and Bellman-Ford algorithm as its own subroutines and can handle graphs with negative weights
If there are no negative edges, run Dijkstra's algorithm once for each node
If there are negative edges but no negative cycles, use Dijkstra's algorithm to construct a new set of non-negative weight values by reweighting them.
The newly assigned weight must satisfy the following two properties
path equivalence
non-negativity
Assignment method
Create a new node s, whose weights to other vertices are all 0 (all are out-degrees, no in-degrees)
Define new weight (u,v) = (u,v) h(u)-h(v)
Floyd-Warshall algorithm
Steps
optimal substructural
If it does not change after adding (k does not belong to the shortest path), the original path remains unchanged.
If it changes after adding, the shortest path becomes i->k->j, where i->k and k->j are the shortest paths where the intermediate nodes are taken from 1...k-1
Construct a recursive expression
Compute recursive expression
Actual operation
1. First pay attention to the weight matrix D, and only look at the in-degree connected node (sequence number is i) of the added node to the out-degree connected node (sequence number is j)
2. If necessary, update the weights and predecessor nodes (note that the predecessor node is the k-th row and j-th column element of the previous predecessor matrix)
3. Repeat the above steps until all nodes are included
Time complexity: n^3
Compute matrix transitive closure
1
2
The shortest path for all pairs of nodes
Basic settings
cost adjacency matrix
shortest path matrix
precursor node matrix
NIL when i=j or path does not exist
Matrix multiplication algorithm
optimal substructural
Construct a recursive expression
When i=j, the path does not contain any edges and the weight is 0
When i!=j, the path is divided into two parts: the starting point and the end precursor (the path is p`, containing at most m-1 edges, which must be the shortest path) and the end precursor and the end point.
The maximum number of edges contained in the path between two points is used as the traversal condition (add an intermediate point when adding an edge, similar to the relaxation operation)
Compute recursion
Top-down (recursive)
Bottom-up (iterative)
Relationship to matrix multiplication
Improvement: Repeated squaring technique (square each time)
single source shortest path
prerequisite knowledge
optimal substructural
Negatively weighted edges
The shortest path should be a simple path (not containing loops)
Representation of the shortest path: record predecessor
precursor subgraph
Solution steps
initialization
For each vertex v there is
d=the shortest distance from the point v to the source point s
pi=precursor of this point (used to recover the shortest path)
After initialization, the initial value of each vertex is
d=∞
pi=null
Relax (Relax u, v, w) operation
Input the operated node v and an intermediate node u. If s->u->v is shorter than the weight of s->v, update the weight of v to the new path and the predecessor to u.
nature
Triangle Inequality Properties
Upper bound properties
non-path properties
convergence properties
path relaxation properties
In the absence of a negative loop, it will definitely converge after N relaxations.
The establishment of the relaxation property has nothing to do with the order of relaxation operations.
Algorithm implementation
Bellman-ford algorithm
theoretical operation
Execute N-1 large loops. In each large loop, each edge in the graph is relaxed. The direct object is each directed edge (u->v) in the graph.
After performing N-1 loosening cycles, if there is no negative cycle, according to the convergence properties, the d table should be stable; therefore, if the d table remains unchanged after another cycle, it means that there is no negative cycle, and True is returned.
Operations in actual graphs (refer to Dijkstra’s ideas)
Relaxation order does not matter
Stare at the point where the node value changed in the last operation (including the initialized ∞->0) and see if the weight of the node connected to it has changed.
(The number of nodes is N) Table D should be stable after N-1 RELAX operations, and the last one is used for detection.
Dijkstra's algorithm
Practical & theoretical operations
Data settings
initialization
Iterate
Theoretical proof
Use loop invariants to prove
Time complexity analysis
differential constraint system
nature
Vector x is a solution of a certain differential constraint system, then adding a constant d is still the solution of the system.
If the constraint graph does not include a cycle with a negative weight, the corresponding node weight is a feasible solution of the system; if it contains a cycle with a negative weight, the system has no feasible solution.
constraint graph
ways to obtain
Treat the mxn matrix A as the transformation of the adjacency matrix of n nodes and m edges.
The purpose is to have the independent variables correspond to the nodes and the constraints to the edges.
Each directed edge corresponds to an inequality
Add a new node v0, which is connected to all nodes and the distance is 0
Processing method: Bellman-Ford algorithm
minimum spanning tree
Generate method
MST (Minimum-Span-Tree) properties (greedy algorithm)
Add a safety edge at each step (the loop invariant will not be changed after adding)
cut definition
Cut across: for a certain edge
respect
lightweight edges
Lightweight edges may not be the only ones
Expanded definition: The edges with the smallest weight that satisfy a certain property are all lightweight edges of that property.
Principles for choosing the safe side
Delineate an edge set A that is included in the complete set E, and it is known that A is included in a certain minimum spanning tree.
Given an arbitrary cut of A, find a lightweight edge in E that spans the cut. This edge must be safe.
Kruskal algorithm
Steps
1. During initialization, set A is a forest, which is the node set of G.
2. Use the edge with the smallest weight connecting two different components/nodes of A as a safe edge to merge the two components/nodes.
3. Until A contains n-1 edges
Time complexity: O(ElgE)
Prim's algorithm
Steps
1. During initialization, set A only contains one specified root node.
2. Each time, the edge with the smallest weight connecting the node outside set A and the node inside set A is added as a safe edge.
3. Until A contains n-1 edges
Time complexity: O(ElgV)
Basic knowledge of algorithms
Five important characteristics of algorithms
certainty
feasibility
enter
output
Finiteness
A set of rules that satisfy certainty, feasibility, input and output is called a computing process. An operating system is a typical computing process.
An algorithm is a "terminable computational process"
bounding function
upper bound function
lower bound function
Asymptotically tight bounding function
time complexity calculation
Algorithm time complexity classification
Polynomial time algorithm: O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)
Exponential time algorithm: O(2^n)<O(n!)<O(n^n)
loop invariant
initialization
Keep
termination
divide and conquer algorithm
Solving recursive formulas (divide and conquer algorithm)
preprocessing
The running time function T(n) assumes n is a positive integer
Ignore the boundary conditions of the recursion (when n is small)
Ignore the upper and lower forensic functions
Substitution skills
Remove lower order terms
Variable substitution: set to exponential and logarithmic forms or interchange
Solution
substitution method
Commonly used formulas
T(n)=2T(n/2) => T(n)=O(nlogn)
Problem solving steps
Guess the solution form, then set constants to get the initial inequality form
Assume that the n-1th recursion holds and the corresponding inequality is obtained
Substituting the n-1th inequality into the simplified original formula, we get the target formula
Transform the objective equation into the form of the initial inequality and the form of additional terms. The establishment conditions can be obtained by dealing with the additional terms.
Analyze the boundary conditions, and if they do not hold, set new boundary conditions independently.
recursive tree method
Each node represents the cost of a single subproblem, and the subproblem corresponds to a certain recursive call.
The root node represents the cost of the top-level call, and the child nodes represent the cost of the recursive call at each level.
The sum of the costs of all nodes is the total cost (generalized into a geometric sequence summation problem)
After taking the upper bound function, use the substitution method to prove
main method
If for a certain constant e>0, f(n)=O(n^log_b(a-e)), then T(n)=/Theta(n^log_b(a))
If f(n)=/Theta(n^log_b(a)), then T(n)=/Theta(n^log_b(a)logn)
If for a certain constant e>0, f(n)=/Omega(n^log_b(a e)), and for all sufficiently large n, af(n/b)<=cf(n), then there is T (n)=/Theta(f(n))
Maximum subarray problem
Solution steps
1. Divide A[low...high] into two subarrays of equal size as much as possible
2. Solve two subarrays separately and recursively
The largest subarray is on the left
The largest subarray is on the right
Maximum subarray spans both sides
dynamic programming
background knowledge
Optimization problem
Classification
linear programming
nonlinear programming
integer programming
dynamic programming
subproblem graph
Features
Directed graph, arrows represent dependencies, and arrows point to dependent items
Each vertex corresponds to a sub-problem one-to-one
Nodes of the same subproblem in the recursion tree shrink to one vertex in the subproblem graph
Bottom-down processing order: a subproblem is solved after all its dependent subproblems have been solved
Estimate time complexity
The number of subproblems is equal to the number of vertices
Remove this part of the solution from the original problem solution and replace it with a better solution
The solution time of a subproblem is proportional to the out-degree of the corresponding vertex
General steps
1. Characterize the structural characteristics of an optimal solution
optimal substructural
Proof: proof by contradiction (cut-and-paste method)
Assume that a certain partial solution is not the optimal solution and there is a better solution
The new solution obtained is better than the original "optimal solution", which is a contradiction
sub-problem irrelevance
For example: the longest simple path sub-problem is relevant, so DP cannot be used; but the shortest path sub-problem is not relevant, so DP can be used.
2. Recursively define the value of the optimal solution
3. Calculate the value of the optimal solution
Usually a bottom-up approach is used to find the optimal solution
4. Use the calculated information to construct an optimal solution
If you only need the value, you can ignore the fourth step.
Store steps during calculation
example
Steel bar cutting problem
thought process
1. Determine the optimal solution structure
2. Convert to recursive form
3. Solve and get the optimal number
4. Reconstruct the solution (obtain the plan/process for obtaining the optimal solution)
Optimizing recursive processes using dynamic programming
Problem: A large number of repeated subproblem calculations appear in the recursion tree
The dynamic programming method will carefully arrange the solution sequence, solve each sub-problem only once, and save the results
Dynamic programming requires additional space cost to save the solution of the sub-problem, which is a typical space-time trade-off.
Solution
Top-down approach with memos
bottom-up approach
First sort the sub-problems from small to large in size
Solve sub-problems in order, calling the solved sub-problems directly each time
The final result is the optimal solution to all sub-problems (including the original problem)
Compared
Typically, top-down and bottom-up have the same progressive running time
matrix chain multiplication
background knowledge
Matrix multiplication satisfies the associative law but does not satisfy the commutative law
Different order of operations (adding parentheses) brings significant differences in the number of operations
Finding the optimal way to add brackets is an optimal solution problem
definition
Minimum number of operations m[i,j]
Record the dividing point s[i,j]
Solution steps
1. Construct the optimal solution
p is the dimension representation of the n-brother matrix
2. Recursive solution
Drawing analysis
Longest common subsequence (LCS)
Solution steps
1. Construct the optimal solution
2. Construct recursion
3. Solving recursion
Practical operation (drawing analysis)
For a sequence X of length m and a sequence Y of length n, construct a two-dimensional table of mxn
Generate a sequence of 0s at the top and left, and then represent the string
The i-th row and j-th column of the table means the largest common subsequence of Xi and Yj so far.
Determine inheritance mode by comparing new elements for equality
If the newly added elements are not equal, the largest one above or on the right will be inherited.
If the newly added elements are equal, assign the value to the upper left corner ➕1
Pattern representation (used to record each step of operation and restore LCS)
⬆️/⬅️: Indicates inheriting the maximum value
↖️: Indicates where the maximum common subsequence increases (used for restoration)
optimal binary search tree
background knowledge
Pseudo keyword di
Probability qi
expected search cost
The cost of a search is equal to the depth of the node (the depth of the root node is 0) 1
The total cost is the sum of the costs of all keywords and pseudo-keywords
recursive formula
structure
definition
Cost array e[1..n 1,0..n]
Root node record array root[1...n]
Node probability sum w[1..n 1,0..n]
greedy algorithm
General steps
1. Determine the optimal substructure of the problem
2. Optimize the optimal substructure
3. Prove the correctness of greedy choice
Prove that after making a greedy choice, there is always an optimal solution to the original problem (greedy choice is safe)
Prove that the greedy selection property is satisfied (the optimal solution can be constructed through local optimal greedy selection)
Proof method: cut-and-paste method
Theoretical basis
greedy choice property
Unlike dynamic programming, which requires solving sub-problems (bottom-up) before making the first selection, greedy algorithms do not need to solve any sub-problems. They usually perform calculations directly from top to bottom, reducing the size of the problem step by step.
optimal substructural
example
Activity selection issues
It can be solved using dynamic programming, but the greedy algorithm can be transformed into a simpler iterative problem
Solution steps
Optimal substructures and recursive formulas
Reduce subsetting to filling in one activity
Using the dynamic programming method, you should create a memo after traversing all activities and select the optimal one to fill in.
The greedy algorithm optimizes dynamic programming by converting one of the two sub-problems into an empty problem
prove correctness
Assume that there is a maximum compatible subset
Because the end time fj of the earliest activity aj in the subset must be greater than or equal to the end time fm of the earliest activity am in the entire set, and the activities in the subset must not intersect.
Therefore, the size of the subset remains unchanged after replacing the earliest activity in the subset with the earliest activity in the full set.
Therefore, the earliest activity in the complete set must be in the largest compatible activity subset
Huffman coding
Discrete mathematics has a detailed introduction
Solution
1. Initially, all words are independent leaf nodes.
2. Select the two nodes with the smallest word frequency to form a tree. The root node is the sum of word frequencies (the one with the larger word frequency is the right child)
3. Repeat the above steps until the tree is established
Time complexity: nlgn
graph algorithm
basic knowledge
A graph is usually represented by G=(V,E)
V: the set of nodes in G, |V| represents the number of nodes
E: The set of edges in G, |E| represents the number of edges
Usually the two parameters |V| and |E| are used to represent the size of the algorithm input.
Representation of graph
Adjacency list: a linked list representing edges
Adjacency matrix: 01 matrix representing the adjacent relationship between vertices
The adjacency matrix of an undirected graph is symmetric, so it can be represented by an upper/lower triangular matrix
Graph traversal
BFS (Broad-First-Search) breadth-first search
spanning tree
BFT (Broad-First-Traverse) breadth-first traversal
If the number of BFS calls is more than 1, then G is not a connected graph
Each time BFS generates a connected subgraph
Improvement: deep search
DFS (Depth-First-Search)
Do recursion directly
planning algorithm
Common ideas
divide and conquer thinking
dynamic programming
greedy algorithm
Backtrack
branch-limit
Related concepts
A set of solutions with specific properties used to solve a problem or an optimal solution that satisfies certain constraints.
Question requirements
The solution can be represented by an n-tuple vector, and the dimensionality is taken from a finite set
The goal of solving the problem is to find a vector (or a set of vectors) that makes a certain canonical function take an extreme value or other conditions.
Restrictions
Explicit constraints
implicit constraints
solution space
solution space organization
state space tree
Related concepts
Problem status
state space
solution state
answer status
The same problem may have different forms of state space trees
The edges of each layer represent a set of values of Xi
structure
Use the initial state of the problem as the root node, and then systematically generate nodes for other problem states.
node type
slipknot
E-node
dead node
construction strategy
DFS strategy
BFS strategy
Optimization Strategy
bounding function
Backtracking
Branch-and-bound method
Backtracking
basic concepts
What is backtracking
example
Eight Queens Problem
Use an 8-tuple of [x1,…,x8] to represent the solution, where i represents the row number and xi represents the column number.
explicit condition
implicit condition
Any two xi cannot be the same
Two queens cannot be on the same diagonal
solution space organization
bounding function
Prune based on the original DFS tree without changing the node number
subset sum problem
display method
Directly represented by elements
k-tuple (represented by element subscripts)
explicit condition
implicit condition
No two xj are the same
and must be M
Satisfy monotonic increase (avoid repeated iterations)
n-tuple (represented by 01 vector)
explicit condition
The ancestor has a fixed size
The value can only be 0 or 1
Implicit condition: sum is M
Solution space: 2^n
branch-and-bound method
Slipknot table
data structure
Queue (FIFO, for BFS)
Stack (LIFO, for D-Search)
example
n-queen problem
FIFO/BFS
LC (Least Cost) search (A* algorithm)
Problems with LIFO/FIFO pruning
solution
node cost function
Standard cost function C(X)
If X is the answer node, then take the number of levels from the root node to X
If X is not but its subtree contains the answer node, then take the cost of the answer node with the minimum cost in the subtree
If X does not contain any answer nodes, it is ∞
Problem: The computational cost complexity is the same as the solution problem
Cost estimation function: estimated cost incurred cost
Estimate function g(x)
Problem: It will cause the selection of E node to be biased towards DFS
Incurred cost function h(x)
Effect: Make the algorithm prioritize retrieval of nodes closer to the answer node and closer to the root
Example
Special cases (using LC searches to describe other searches)
BFS
estimated function = 0
Cost function = series
Effect: Prioritize retrieval of the same layer
D-Search
cost function=0
15-Puzzle question
LC branch-bounded search
Construction of state space tree
Pruning strategy
cost estimation function
The estimation function should represent the estimate of the shortest path from X to the answer state
The cost estimation function is the lower bound of the minimum cost and serves as a heuristic function to reduce the blindness of E-node selection.
Concrete expression
costs incurred
Upper bound of minimum cost (bounded function)
Method 1: Initial value
Method 2: After getting the new answer, update the answer to the upper bound