程序代写代做代考 cache algorithm AI data structure COMP251: Dynamic programming (1)

COMP251: Dynamic programming (1)
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Cormen et al., 2002) & (Kleinberg & Tardos, 2005)

Algorithms paradigms
• Greedy:
o Build up a solution incrementally.
o Iteratively decompose and reduce the size of the problem. o Top-down approach.
• Dynamic programming:
o Solve all possible sub-problems.
o Assemble them to build up solutions to larger problems. o Bottom-up approach.

An example? 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 = ?
20!
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 = ?
21
Principle: Use answers previously computed for a smaller instance

INTRODUCTION

Activity-selection Problem
• Input: Set S of n activities, a1, a2, …, an. – si = start time of activity i.
– fi = finish time of activity i.
• Output: Subset A of maximum number of compatible activities.
– 2 activities are compatible, if their intervals do not overlap.
Example:
Activities in each line are compatible.
0 1 2 3 4 5 6 7 8 9 10

Activity-selection Problem
i
si fi
1234567
0124568
2 3 5 6 9 9 10
Activities sorted by finishing time.
s2 a1
s3 a2
f1
a3
f2 s4
s5
s6 f3
a4
a5 f4
a6
s7
a7
f6 f5
s1
f7 0 1 2 3 4 5 6 7 8 9 10

Activity-selection Problem
i12 si 0 1 fi 2 3
s3 a2
Activities sorted by finishing time.
34567
24568
5 6 9 9 10
f1
a3
f2 s4
s5
s6 f3
a4
a5 f4
a6
s7
a7
f6 f5
a1 s1
s2
f7 0 1 2 3 4 5 6 7 8 9 10

Activity-selection Problem
i1234 si 0 1 2 4 fi 2 3 5 6
Activities sorted by finishing time.
a3 s3
a2
567
568
9 9 10
s6 f3
a4
a5 f4
a6
s7
a7
f6 f5
s2
f2 s5
sa1 fs 114
f7 0 1 2 3 4 5 6 7 8 9 10

Activity-selection Problem
i1234567 si 0 1 2 4 5 6 8
fi
2 3 5 6 9 9 10 Activities sorted by finishing time.
s a3 s6 a6 f
3 f3 6
a2fsa5 f 255
s2
s a1 114477
f s a4 f s a7 f 0 1 2 3 4 5 6 7 8 9 10

Optimal sub-structure
• Let Sij = subset of activities in S that start after ai
finishes and finish before aj starts. S=a∈S:∀i,j f≤s M[j–1])
return { j } ∪ Find-Solution(p[j]) else
return Find-Solution(j–1).
Analysis. # of recursive calls ≤ n ⇒ O(n).

Example: Computing solution
activity predecessor Best weight M Vj+M[p(j)] M[j-1]
(1) Activities sorted by finishing time. (2) Weight equal to the length of activity.
a1 a2 a3 a4 a5
123
45
002
23
—
—
—
—
—
—
0 1 2 3 4 5 6 7 8 9 10

123
45
002
23
2–
—
2–
—
0–
—
M[0]=0
Example: Computing solution
activity predecessor Best weight M Vj+M[p(j)] M[j-1]
(1) Activities sorted by finishing time. (2) Weight equal to the length of activity.
a1 a2 a3 a4 a5
0 1 2 3 4 5 6 7 8 9 10

Example: Computing solution
1
activity predecessor Best weight M
23
02
45
0
23
3-
—
3-
—
2-
—
2 Vj+M[p(j)] 2
0
M[j-1]
(1) Activities sorted by finishing time. (2) Weight equal to the length of activity.
a1 a2 a3 a4 a5
0 1 2 3 4 5 6 7 8 9 10

Example: Computing solution
12
23 2 3 02
activity predecessor Best weight M Vj+M[p(j)] M[j-1]
00
3
2
4
4
3
45
23
—
—
—
(1) Activities sorted by finishing time. (2) Weight equal to the length of activity.
a1 a2 a3 a4 a5
0 1 2 3 4 5 6 7 8 9 10

Example: Computing solution
activity predecessor Best weight M Vj+M[p(j)] M[j-1]
123
234 2 3 4 023
002
45
23
9-
9-
4-
(1) Activities sorted by finishing time. (2) Weight equal to the length of activity.
a1 a2 a3 a4 a5
0 1 2 3 4 5 6 7 8 9 10

Example: Computing solution
1234
2349 2 3 4 9 0234
Your solution
activity predecessor Best weight M Vj+M[p(j)] M[j-1]
0022
5
3
9 8 9
(1) Activities sorted by finishing time. (2) Weight equal to the length of activity.
a1 a2 a3 a4 a5
0 1 2 3 4 5 6 7 8 9 10

Example: Reconstruction
activity predecessor Best weight M Vj+M[p(j)] M[j-1]
12345 00223 23499 2 3 4 9 8 02349
(1) Activities sorted by finishing time. (2) Weight equal to the length of activity.
a1 a2 a3 a4 a5
0 1 2 3 4 5 6 7 8 9 10

Related Posts