notes ： Sorting out the knowledge points of Teacher Liu's class content this semester .

<> Greedy Algorithm

Greed is not always right , Need proof

<> Activity arrangement

Proof of algorithm correctness ：

Basic elements of greedy algorithm ：
Greedy selection property and optimal substructure property
greedy-choice property
contrast : Matrix multiplication , 0-1 knapsack vs Fractional knapsack , Activity arrangement
The first basic element of greedy algorithm , And DP Main differences
== Top down calculation ==
OSP: The sub strategies of the optimal strategy are also optimal // Moving gauge , greedy
== General process of correctness proof : ==
Greedy choice +OSP+ Mathematical induction
condition : The subproblem is similar to the original problem , Relatively independent // Not similar ? Another method is required
The optimal solution of the subproblem is combined with greedy selection to obtain the overall optimal solution

General design process ：

* The problem is described as greedy choice and a sub problem to be solved
* greedy-choice property : Prove that greedy choice is right
* Optimal substructure properties :
Ensure that if the optimal solution of the subproblem is combined with greedy selection , The optimal solution of the original problem can be obtained .
Activity arrangement
Greedy choice : The earliest activity to end
Subproblem : T1 = { Start time is later than f1 Activities }
<> Optimal coding problem （Huffman coding ）

Determine the structure of the solution : Binary tree

Good coding ：
Large frequency coding short
Small frequency coding length
Regular binary tree
Relative balance

greedy-choice property ：
 There is an optimal solution with the minimum frequency and the maximum depth of the two leaf node
 There is an optimal solution whose frequency is the smallest. The two leaf nodes are brothers

Optimal coding problem
Greedy choice : The two letters with the lowest frequency are brothers . Subproblem ?
Original problem : 6 Symbols to be coded
Subproblem : 5 Symbols to be coded

input C[1:n], f[1:n] // Alphabet set C And frequency f 1. Q=C // Build priority queue Q, O(n) 2. yes i = 1:n-1 // loop n-1 second 3.
Assign new node z4. take Q in f minimum x As z My left child //O(log n) 5. take Q in f minimum y As z My right child //O(log n) 6. f[z] = f[x] + f
[y] 7. take z insert Q in //O(log n) 8. take out Q Middle node as tree root //?
<> Shortest path problem

* All point to shortest circuit （APSP)
DP：

1. D[i,j][0] = w[i,j], The nonexistent boundary value takes infinity 2. yes k=1:n 3. yes i=1:n, yes j=1:n 4. if D[i,k][k-1]+D
[k,j][k-1] < D[i,j][k-1] 5. be D[i,j][k] =D[i,k][k-1]+D[k,j][k-1]; 6. otherwise D[i,j][k
] = D[i,j][k-1]
Floyd-Warshall algorithm

Reduce storage ? D[i,k][k]=D[i,k][k-1]?
Any shortest path passes at most k once
0. if w[i,j]< Infinity , be p[i,j]=i 1. D[i,j] = w[i,j] 2. yes k=1:n 3. yes i=1:n, yes j=1:n 4. if D
[i,k]+D[k,j] < D[i,j] 5. be D[i,j] = D[i,k]+D[k,j]; 6. p[i,j] = p[k,j]; // Unmark
reason .== Structural solution .== O(n3).
p[i,j]: stay i reach j On the shortest circuit of j Precursor of

* Single source shortest circuit
function d And slack operation

Bellman-Ford( Including negative weight [C])
initial d[s]=0, Other points d[u]=INF, 1. yes i =1: |V|-1 // slack |V|-1 Times 2. For each edge (u,v), slack (u,v) 3. For each edge
(u,v), // Check the negative circuit 4. if d[v]>d[u]+w(u,v), Return false 5. Return true
time O(|V| |E|)
Non dynamic programming , Non greedy
set up s Connect all points
Negative loop : Edge weight sum <0
Proof of correctness :

Dijktra( No negative right ）
1. initial d[s]=0, Other points d[u]=INF, S empty , Q=V 2. When Q Non empty 3. take out Q in d[u] least u, join S 4. yes u Every neighbor v, slack (
u,v) remember u Your neighbor is N(u): vN(u)

Cumulative complexity estimation .
(1)
Q Using general array storage . Cumulative all page 5 step ： Each edge is relaxed once , total O(|E|); Cumulative all page 3 step , Perform one-time minimum search d[u] need O(|V|) time , common |V| second . total O(|V|2
+ |E|)
(2)
Q Store with minimum heap . Cumulative all page 5 step ： Each edge is relaxed once , After relaxation, add a point to the minimum heap , Time to maintain the minimum heap at one time O(log|V|), total O(|E|log|V|); Cumulative all page 3 step , Execute once O(log|V|), common |V| second . total O((|V|+|E|)log|V|)=O(|E|log|V|). Only if the number of sides is not reached c|V|
2, It is necessary to use the minimum heap .

Dijkstra Correctness proof of greedy algorithm

<> minimum spanning tree (MST)

Undirected connected weighted graph G=(V,E,w).
G The spanning tree is G A subtree containing all vertices
if G Spanning tree T At all G The sum of each edge weight in the spanning tree is the smallest ,
be T be called G Minimum spanning tree (MST, minimum spanning tree)

there MST I don't understand the proof of nature （ Greedy choice + induce ）
I didn't understand it yesterday I understand it today ... Is to assume one MST Excluding （u,v) But if so, it is not MST

MST Proof of algorithm correctness

Prim algorithm ：
Use general array
key[u] remember u reach U Minimum distance of , p[u] remember u And U Minimum distance corresponding point 1. initial p[u]=NIL, key[r]=0, other key[u]=INF, Q=V, U empty
2. When Q Non empty 3. take out Q in u bring key[u] minimum , join U 4. yes u Every neighbor v, 5. if vQ And w[u,v] < key[v] 6. be key
[v] = w[u,v], p[v] = u Q General array O(|V|^2+|E|) = O(|V|^2)
Estimation of time complexity using cumulative method .
Q Using general array storage . Cumulative all page 456 step ： Each edge is processed once , total O(|E|); Cumulative all page 3 step , Execute once O(|V|), common |V| second . total O(|V|2+ |E|)
Use priority queue ：
key[u] remember u reach U Minimum distance of , p[u] remember u And U Minimum distance corresponding point 1. initial p[u]=NIL, key[r]=0, other key[u]=INF, Q={r},
U empty 2. When priority queue ( Minimum heap )Q Non empty 3. delete Q Heap top element u. if u stay U in , be continue; Otherwise join U. 4. yes u Every neighbor v, 5. if w[u,v]
< key[v] 6. be take v Key value key[v]=w[u,v] insert Q, p[v] = u Q Priority queue O(|E|log|V|+|E|log|E|) = O(|E
|log|V|)

Q Store with minimum heap . Cumulative all page 456 step ： Each edge is processed once , Add a point to the minimum heap after processing , Time to maintain the minimum heap at one time O(log|V|), total O(|E|log|V|); Cumulative all page 3 step , Execute once O(log|V|), common |V| second . total O((|V|+|E|)log|V|)=O(|E|log|V|). Only if the number of sides is not reached c|V|2, It is necessary to use the minimum heap .

Kruskal algorithm
1. A Empty , Q=E Arrange in ascending order of edge weight 2. When Q Non empty 3. Sequential access Q Middle edge (u,v) 4. if u,v stay A Different connected branches of ( inspect ), 5. Then add (u,v) reach A, (
And merge u,v Connected branch ) 6. output A Parallel search set algorithm to deal with connected branches , O(|E|log|E|+|E|log*|V|)
Using parallel search set algorithm （ I didn't understand until I checked the analysis of others …）

1. A Empty , Q=E Arrange in ascending order of edge weight , x Make(x) 2. When Q Non empty 3. Take order Q Middle edge (u,v) 4. if Find(u)Find(v), Then add (u
,v) reach A, Union(u,v), 5. output A
This is what ordinary people can understand ???
I can't understand it anyway
[ Liu ]n Nodes , m Secondary operation , O((n+m)log*n)

<> Multi machine scheduling problem

The optimization class learned the randomization algorithm to solve , But the optimal solution may not be obtained .

Technology
Daily Recommendation
views 1