CS计算机代考程序代写 data structure algorithm Lecture 3 – Linked Lists

Lecture 3 – Linked Lists

Lecture 24

Knapsack Solved All Ways

Shortest Path Algorithms

EECS 281: Data Structures & Algorithms

http://xkcd.com/287

Many

http://xkcd.com/287/

Data Structures & Algorithms

The Knapsack Problem

3

Knapsack Problem Defined

• A thief robbing a safe finds it filled with N

items

– Items have various sizes (or weights)

– Items have various values

• The thief has a knapsack of capacity M

• Problem: Find maximum value the thief

can pack into their knapsack that does not

exceed capacity M

4

• Assume a knapsack with capacity M = 11

• There are N = 5 different items

• Return maxVal, the maximum value the

thief can carry in the knapsack

Example: Knapsack

1 2 3 4 5

Size 1 2 5 6 7

Value 1 6 18 22 28

5

Variations on a Theme

• Each item is unique (the Standard)

– Known as the 0-1 Knapsack Problem

– Must take an item (1) or leave it behind (0)

• Finite amount of each item (explicit list)

• Infinite number of copies of each item

• Fractional amount of item can be taken

• Using weight (wi) instead of size

6

Solve Knapsack Problem

Using multiple algorithmic approaches

• Brute-Force

• Greedy

• Divide and Conquer

• Dynamic Programming

• Backtracking

• Branch and Bound

Data Structures & Algorithms

The Knapsack Problem

Data Structures & Algorithms

Knapsack: Brute-Force

9

Knapsack: Brute-Force

• Generate possible solution space

– Given an initial set of N items

– Consider all possible subsets

• Filter feasible solution set

– Discard subsets with setSize > M

• Determine optimal solution

– Find maxVal in feasible solution set

Brute-Force

Knapsack:

1 2 3 4 5 Val

0 0 0 0 0 0

1 0 0 0 0 1

0 1 0 0 0 6

1 1 0 0 0 7

0 0 1 0 0 18

1 0 1 0 0 19

1 1 1 0 0 25

0 0 0 1 0 22

1 0 0 1 0 23

0 1 0 1 0 28

1 1 0 1 0 29

0 0 1 1 0 40

1 0 1 1 0 41

0 1 1 1 0 46

1 1 1 1 0 47
10

1 2 3 4 5 Val

0 0 0 0 1 28

1 0 0 0 1 29

0 1 0 0 1 34

1 1 0 0 1 35

0 0 1 0 1 46

1 0 1 0 1 47

1 1 1 0 1 53

0 0 0 1 1 50

1 0 0 1 1 51

0 1 0 1 1 56

1 1 0 1 1 57

0 0 1 1 1 68

1 0 1 1 1 69

0 1 1 1 1 74

1 1 1 1 1 75

1 2 3 4 5

Size 1 2 5 6 7

Value 1 6 18 22 28

11

Brute-Force Pseudocode

1 bool array possSet[1..N] (0:leave,1:take)

2 maxVal = 0

3 for i = 1 to 2N

4 possSet[] = genNextPower(N)

5 setSize = findSize(possSet[])

6 setValue = findValue(possSet[])

7 if setSize <= M and setValue > maxVal

8 bestSet[] = possSet[]

9 maxVal = setValue

10 return maxVal

12

Brute-Force Efficiency

• Generate possible solution space

– Given an initial set of N items

– Consider all possible subsets

– O(2N)

• Filter feasible solution set

– Discard subsets with setSize > M

– O(N)

• Determine optimal solution

– Find maxVal in feasible solution set

– O(N)

O(N2N)

Data Structures & Algorithms

Knapsack: Brute-Force

Data Structures & Algorithms

Knapsack: Greedy

15

Greedy Approach

Approaches

• Steal highest value items first
– Might not work if large items have high value

• Steal lowest size (weight) items first
– Might not work if small items have low value

• Steal highest value density items first
– Might not work if large items have high value density

If greedy is not optimal, why not?

16

Example: Greedy Knapsack

• Assume a knapsack with capacity M = 11

• There are N different items, where

– Items have various sizes

– Items have various values

1 2 3 4 5

Size 1 2 5 6 7

Value 1 6 18 22 28

Ratio 1 3 3.6 3.67 4

17

Greedy Pseudocode
Input: integers capacity M, size[1..N], val[1..N]

Output: integer max value size M knapsack can carry

1 maxVal = 0, currentSize = 0

2 ratio[] = buildRatio(value[], size[])

3 // Sort all three arrays by ratio

4 sortRatio(ratio[], value[], size[])

5 for i = 1 to N //sorted by ratio

6 if size[i] + currSize <= M 7 currSize = currSize + size[i] 8 maxVal = maxVal + value[i] 9 10 return maxVal 18 Greedy Efficiency • Sort items by ratio of value to size – O(N log N) • Choose item with highest ratio first – O(N) O(N log N) + O(N)  O(N log N) 19 Fractional Knapsack: Greedy • Suppose that thief can steal a portion of an item • What happens if we apply a Greedy strategy? • Is it optimal? Data Structures & Algorithms Knapsack: Greedy Data Structures & Algorithms Knapsack: Dynamic Programming 22 Dynamic Programming • Enumeration with DP – Examples: Fibonacci, Binomial Coefficient, Knight Moves – These are constraint satisfaction problems • Optimization with DP – Examples: Knapsack, Longest Increasing Subsequence, Weighted Independent Subset • Both can be solved top-down or bottom-up, optimizations often favor bottom-up 23 DP Knapsack Approach • A master thief prepares job for apprentice – Alarm code, safe combination, and knapsack – List of items in safe – Table of items to put in knapsacks, 0 < x ≤ M • Apprentice finds one extra item in safe – Take it or leave it? – Remove just enough to fit the new item • Q: What should be removed? • Q: When should the new item be included? 24 DP Knapsack Generalization • Each item will either be taken or left behind – If it is too large it is left behind – If room can be made to include it, it will be taken only when it improves the haul • Bottom-Up uses two nested loops – Look at items one a time • Look at knapsacks from size 0 up to M – Build and use a 2D memo 25 1 2 3 4 5 Size 1 2 5 6 7 Value 1 6 18 22 28 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 Safe Knapsack Size S a fe I te m # 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 6 7 7 7 7 7 7 7 7 7 0 1 6 7 7 18 19 24 25 25 25 25 0 1 6 7 7 18 22 24 28 29 29 40 0 1 6 7 7 18 22 28 29 34 35 40 27 Dynamic Programming: Knapsack 1 uint32_t knapsackDP(const vector &items, const size_t m) {

2 const size_t n = items.size();

3 vector>

4 memo(n + 1, vector(m + 1, 0)); // +1, +1

5

6 for (size_t i = 0; i < n; ++i) { 7 for (size_t j = 0; j < m + 1; ++j) { // +1 for memo[][m] 8 if (j < items[i].size) 9 memo[i + 1][j] = memo[i][j]; 10 else 11 memo[i + 1][j] = max(memo[i][j], 12 memo[i][j – items[i].size] + items[i].value); 13 } // for j 14 } // for i 15 return memo[n][m]; 16 } // knapsackDP() Run time is O(MN) 28 Reconstructing the Solution • Included items improve a smaller solution, excluded items do not • If a smaller solution plus an item is greater than or equal to a full solution without the item it is included, otherwise it is excluded • Use completed memo to determine the items taken • Work backward from (n, m) to (0, 0) 29 1 2 3 4 5 Size 1 2 5 6 7 Value 1 6 18 22 28 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 Safe Knapsack Size S a fe I te m # 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 6 7 7 7 7 7 7 7 7 7 0 1 6 7 7 18 19 24 25 25 25 25 0 1 6 7 7 18 22 24 28 29 29 40 0 1 6 7 7 18 22 28 29 34 35 40 0 0 0 18 40 40 30 Knapsack DP Reconstruction 18 vector knapDPReconstruct(const vector &items,

19 const vector> &memo, const size_t m) {

20 const size_t n = items.size();

21 size_t c = m; // current capacity

22 vector taken(n, false); // included items

23

24 for (int i = n – 1; i >= 0; –i) { // use int for -1 loop exit

25 if (items[i].size <= c) { 26 if (memo[i][c - items[i].size] + items[i].value >= memo[i][c]) {

27 taken[i] = true;

28 c -= items[i].size;

29 } // if ..item added

30 } // if ..item fits

31 } // for i..0

32 return taken;

33 } // knapDPReconstruct()
Run time is O(N)

Data Structures & Algorithms

Knapsack: Dynamic Programming

Data Structures & Algorithms

Knapsack: Branch and Bound

33

Knapsack Branch and Bound

• The Knapsack Problem is an optimization

problem

• Branch and Bound can be used to solve

optimization problems

– Knapsack is a maximization

– Initial estimate and current best solution are a

“lower bound”

– Calculate partial solution, remainder is an

“upper bound” estimate

34

Knapsack B&B Elements

• promising(): total weight of items < M • solution(): any collection that is promising • lower_bound: starts with highest possible underestimate, ends with maximum value taken – Can start w/ Greedy 0-1 Knapsack (by value density) • upper_bound: sum of value of included items, plus an ”overestimate” of value that can fit in remaining space – Prune if upper_bound < lower_bound – Can use Greedy Fractional Knapsack • Don’t need permutations only combinations Data Structures & Algorithms Knapsack: Branch and Bound EECS 281: Data Structures & Algorithms Shortest Path Algorithms Data Structures & Algorithms Dijkstra’s Algorithm 39 Shortest Path Examples • Highway system – Distance – Travel time – Number of stoplights – Krispy Kreme locations • Network of airports – Travel time – Fares – Actual distance 40 Weighted Path Length • Consider an edge-weighted graph G = (V, E). • Let C(vi, vj) be the weight on the edge connecting vi to vj. • A path in G is a non-empty sequence of vertices P = {v1, v2, v3, …, vk}. • The weighted path length is given by C(vi, vi+1) i=1 k-1 41 The Shortest Path Problem Given an edge-weighted graph G = (V, E) and two vertices, vs  V and vd  V, find the path that starts at vs and ends at vd that has the smallest weighted path length 42 Single-Source Shortest Path • Given an edge-weighted graph G = (V, E) and a vertex, vs  V, find the shortest path from vs to every other vertex in V • To find the shortest path from vs to vd, we must find the shortest path from vs to all other vertexes in G 43 The shortest weighted path from b to f: {b, a, c, e, f} a b c d e f 3 5 1 5 1 54 2 44 a b c d e f 3 5 1 5 1 54 2 The shortest weighted path from b to f: {b, a, c, e, f} A shortest unweighted path from b to f: {b, c, e, f} 45 Shortest path problem undefined for graphs with negative-cost cycles {d, a, c, e, f} cost: 4 {d, a, c, d, a, c, e, f} cost: 2 {d, a, c, d, a, c, d, a, c, e, f} cost: 0 a b c d e f 3 5 1 5 -6 54 -8 46 Dijkstra’s Algorithm • Greedy algorithm for solving shortest path problem • Assume non-negative weights • Find shortest path from vs to every other vertex 47 Dijkstra’s Algorithm For each vertex v, need to know: • kv: Is the shortest path from vs to v known? (initially false for all v  V) • dv: What is the length of the shortest path from vs to v? (initially  for all v  V, except vs = 0) • pv: What vertex precedes (is parent of) v on the shortest path from vs to v? (initially unknown for all v  V) 48 v kv dv pv a F  b F 0 c F  d F  e F  f F  Find shortest paths to b 3 5 1 5 1 54 2 a b c e f d 49 v kv dv pv a F 3 b b T 0 -- c F 5 b d F  e F  f F  3 5 1 5 1 54 2 a b c e f d 50 v kv dv pv a T 3 b b T 0 -- c F 4 a d F 8 a e F  f F  3 5 1 5 1 54 2 a b c e f d 51 v kv dv pv a T 3 b b T 0 -- c T 4 a d F 6 c e F 8 c f F  3 5 1 5 1 54 2 a b c e f d 52 v kv dv pv a T 3 b b T 0 -- c T 4 a d T 6 c e F 8 c f F 11 d 3 5 1 5 1 54 2 a b c e f d 53 v kv dv pv a T 3 b b T 0 -- c T 4 a d T 6 c e T 8 c f F 9 e 3 5 1 5 1 54 2 a b c e f d 54 v kv dv pv a T 3 b b T 0 -- c T 4 a d T 6 c e T 8 c f T 9 e 3 5 1 5 1 54 2 a b c e f d 55 v kv dv pv a T 3 b b T 0 -- c T 4 a d T 6 c e T 8 c f T 9 e 4 3 98 6 a b c e f d 56 Dijkstra Complexity • O(V2) for a simple nested loop implementation, a lot like Prim’s – Intuition: for each vertex, find the min using linear search • O(E log V) for sparse graphs, using heaps – E for considering every edge – log E = O(log V2) = O(log V) for finding the shortest edge in heap • CLRS 24.3 has a good explanation 57 Dijkstra’s Algorithm 1 Algorithm Dijsktra(G, s0) 2 //Initialize 3 n = |V| 4 create_table(n) //stores k,d,p 5 create_pq() //empty heap 6 table[s0].d = 0 7 insert_pq(0, s0) O( ) O( ) O( ) O( ) O( ) 1 V 1 1 1 58 Dijkstra’s Algorithm (cont.) 1 while (!pq.isempty) 2 v0 = getMin() //heap top() & pop() 3 if (!table[v0].k) //not known 4 table[v0].k = true 5 for each vi  Adj[v0] 6 d = table[v0].d + distance(vi, v0) 7 if (d < table[vi].d) 8 table[vi].d = d 9 table[vi].p = v0 10 insert_pq(d, vi) 11 12 for each v  G(V,E) 13 //build edge set in T 14 (v, table[v].p)  T(V, E’) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) E log E 1 1 1 + E/V 1 1 1 1 log E V 1 Data Structures & Algorithms Dijkstra’s Algorithm 60 Exercise Find the shortest path from O to T kv dv pv O A B C D E F T 61 All-pairs shortest path problem • Given an edge-weighted graph G = (V, E), for each pair of vertices in V find the length of the shortest weighted path between the two vertices Solution 1: Run Dijkstra V times Other solutions: Use Floyd’s Algorithm (dense graphs) Use Johnson’s Algorithm (sparse graphs) 62 NOTE! • We usually end up stopping here for lecture material • You don’t need to know Floyd-Warshall for the exam, but it seems a shame to delete perfectly good slides • If you ever need it for a reference, you’ve got it! 63 Solution 2: Floyd’s Algorithm • Floyd-Warshall Algorithm • Dynamic programming method for solving all-pairs shortest path problem on a dense graph • Uses an adjacency matrix • O(V3) (best, worst, average) 64 Weighted path length • Consider an edge-weighted graph G = (V,E), where C(v,w) is the weight on the edge (v,w). • Vertices numbered from 1 to |V| (i.e. V = {v1, v2, v3, …, v|V|}) 65 Weighted path length • Consider the set Vk = {v1, v2, v3, …, vk} for 0 ≤ k ≤ |V| • Pk(i,j) is the shortest path from i to j that passes only through vertices in Vk if such a path exists • Dk(i,j) is the length of Pk(i,j) Dk(i,j) = |Pk(i,j)| if Pk(i,j) exists  otherwise { 66 Suppose k = 0 • V0 = Ø, so P0 paths are the edges in G: • Therefore D0 path lengths are: P0(i,j) = {i,j} if (i,j)  E undefined otherwise { D0(i,j) = { |C(i,j)| if (i,j)  E  otherwise 67 a b c d e f 3 5 1 5 1 54 2 D0 a b c d e f a   1    b 3  5    c    2 4  d 5     5 e      1 f       to fr o m 68 Floyd’s Algorithm • Add vertices to Vk one at a time • For each new vertex vk, consider whether it improves each possible path – Compute Dk(i,j) for each i,j in V – Minimum of: • Dk-1(i,j) • Dk-1(i,k) + Dk-1(k,j) 69 fr o m to D0 a b c d e f a   1    b 3  5    c    2 4  d 5     5 e      1 f       D1 a b c d e f a   1    b 3  4    c    2 4  d 5  6   5 e      1 f       Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) V1 = {a} 70 fr o m to D1 a b c d e f a   1    b 3  4    c    2 4  d 5  6   5 e      1 f       D2 a b c d e f a   1    b 3  4    c    2 4  d 5  6   5 e      1 f       V2 = {a, b} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 71 fr o m to D2 a b c d e f a   1    b 3  4    c    2 4  d 5  6   5 e      1 f       D3 a b c d e f a   1 3 5  b 3  4 6 8  c    2 4  d 5  6  10 5 e      1 f       V3 = {a, b, c} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 72 fr o m to D3 a b c d e f a   1 3 5  b 3  4 6 8  c    2 4  d 5  6  10 5 e      1 f       D4 a b c d e f a   1 3 5 8 b 3  4 6 8 11 c 7   2 4 7 d 5  6  10 5 e      1 f       V4 = {a, b, c, d} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 73 fr o m to D4 a b c d e f a   1 3 5 8 b 3  4 6 8 11 c 7   2 4 7 d 5  6  10 5 e      1 f       D5 a b c d e f a   1 3 5 6 b 3  4 6 8 9 c 7   2 4 5 d 5  6  10 5 e      1 f       V5 = {a, b, c, d, e} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 74 fr o m to D5 a b c d e f a   1 3 5 8 b 3  4 6 8 11 c 7   2 4 7 d 5  6  10 5 e      1 f       D6 a b c d e f a   1 3 5 6 b 3  4 6 8 9 c 7   2 4 5 d 5  6  10 5 e      1 f       V6 = {a, b, c, d, e, f} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 75 Floyd’s Algorithm 1 Floyd(G) { 2 // Initialize 3 n = |V|; 4 for (k = 0; k <= n; k++) 5 for (i = 0; i < n; i++) 6 for (j = 0; j < n; j++) 7 d[k][i][j] = infinity; 8 9 for (all (v,w)  E) 10 d[0][v][w] = C(v,w) O( ) O( ) O( ) 76 Floyd’s Algorithm 11 // Compute next distance matrix 12 for (k = 1; k <= n; k++) 13 for (i = 0; i < n; i++) 14 for (j = 0; j < n; j++) 15 d[k][i][j] = min(d[k-1][i][j], 16 d[k-1][i][k] + d[k-1][k][j]); 17 } O( ) 77 What About the Paths? • Can’t simply reconstruct them at end • Add initialization: 1 for (i = 0; i < n; i++) 2 for (j = 0; j < n; j++) 3 // If edge doesn’t exist, no path 4 if (C(i,j) == infinity) 5 p[0][i][j] = NIL; 6 else 7 p[0][i][j] = j; 78 Updating Paths • When going through the triple-nested loop of the algorithm, if you ever update a weight, you must also update the path • See code next page 79 fr o m to P0 a b c d e f a - - c - - - b a - c - - - c - - - d e - d a - - - - f e - - - - - f f - - - - - - P1 a b c d e f a - - c - - - b a - a - - - c - - - d e - d a - a - - f e - - - - - f f - - - - - - V1 = {a} 80 Paths: Primary Loops 1 for (k = 1; k < n; k++) 2 for (i = 0; i < n; i++) 3 for (j = 0; j < n; j++) 4 // Compute next distance matrix 5 d[k][i][j] = min(d[k-1][i][j], 6 d[k-1][i][k] + d[k-1][k][j]); 7 // Compute next paths matrix 8 if (d[k-1][i][j] 9 <= d[k-1][i][k] + d[k-1][k][j]) 10 p[k][i][j] = p[k-1][i][j]; 11 else 12 p[k][i][j] = p[k-1][k][j]; O( ) O( ) 81 Worst Case Running Time • Add vertices to Vk one at a time – Outer loop executes |V| times • For each new vertex, consider whether it improves each possible path – Inner loops execute |V|2 times • Overall O(|V|3) • Better than running Dijkstra |V| times?