Bài giảng Thiết kế và đánh giá thuật toán - Lập trình động - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Lập Trình Động
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Kỹ thuật thiết kế dưới lên (bottom-up)

 Một số bài toán tiêu biểu
1
Chia Để Trị - Nhắc Lại

 Kỹ thuật thiết kế thuật toán

 Ý tưởng

 Thiết kế trên xuống (top-down design)

 Chia bài toán lớn thành bài toán nhỏ không giao nhau

 Giải các bài toán nhỏ (theo phương pháp đệ quy)

 Gộp lời giải bài toán nhỏ thành lời giải bài toán lớn

 Ví dụ

 Sắp xếp gộp (merge sort)

 Sắp xếp nhanh (quick sort)

 Tính số Fibonacci
2
Lập Trình Động

 Kỹ thuật thiết kế thuật toán

 Ý tưởng

 Thiết kế dưới lên (bottom-up design)

 Lần lượt giải bài toán từ nhỏ nhất đến lớn

 Xây dựng lời giải bài toán lớn dựa trên lời giải bài
toán nhỏ

 Ví dụ

 Sắp xếp chèn (insertion sort)

 Tính số Fibonacci
3
Lập Trình Động

 Bài toán có tính chất

 Các bài toán con gối nhau (overlapping)

 Cấu trúc con tối ưu (optimal structure)

Lời giải tối ưu của bài toán con có thể sử dụng để
xây dựng lời giải tối ưu cho bài toán toàn cục
4
Lập Trình Động

 Áp dụng cho bài toán tối ưu

 Có nhiều lời giải khả thi

Mỗi lời giải có giá trị đặc trưng

 Tìm lời giải có giá trị đặc trưng tối ưu

 Có thể có nhiều lời giải có cùng giá trị đặc
trưng tối ưu

 Thiết kế cấu trúc (bảng) để lưu kết quả
5
Lập Trình Động

 Dựa trên các bước sau
1. Đưa ra cách tính nghiệm của các bài toán con
2. Tìm công thức xây dựng nghiệm của bài toán 
thông qua nghiệm của các bài toán con
3. Thiết kế bảng để lưu nghiệm của các bài toán
4. Tính nghiệm của các bài toán từ nhỏ đến lớn
5. Xây dựng nghiệm của bài toán cần tìm từ bảng
6
Chia Để Trị – Lập Trình Động

 Lựa chọn đúng kỹ thuật rất quan trọng

 Áp dụng chia để trị cho bài toán mà bài
toán con gối nhau

 Giải lại các bài toán con

 Không hiệu quả

 Ví dụ: tính số Fibonacci
7
Bài Toán

 Dãy Fibonacci

 Hệ số nhị thức

 Dãy con tăng dài nhất

 Bài toán ba lô

 Dãy con chung dài nhất

 Cắt dây
8
Dãy Fibonacci

 = 		=	0,1

+


		 ≥ 2

 Chia để trị

 Bài toán con có giao nhau

 Lập trình động

 Bảng lưu kết quả các giá trị 
 đã tính
9
Hệ Số Nhị Thức
 ,  =  =
 − 1
 − 1 +
 − 1


 Chia để trị

 Bài toán con có giao nhau

 Lập trình động

 Bảng lưu kết quả các giá trị  ,  đã tính
10
Dãy Con Tăng Dài Nhất

 Tìm dãy con tăng dài nhất của dãy số S

 Ví dụ

 S = { 14, 1, 17, 2, 16, 17, 3, 15, 4, 1, 5, 18, 13, 
6, 7, 19, 8, 12, 1, 9, 10, 8 }

 Dãy tăng

S’ = { 14, 1, 17, 2, 16, 17, 3, 15, 4, 1, 5, 18, 
13, 6, 7, 19, 8, 12, 1, 9, 10, 8 }

 Dãy tăng dài nhất

S = { 14, 1, 17, 2, 16, 17, 3, 15, 4, 1, 5, 18, 
13, 6, 7, 19, 8, 12, 1, 9, 10, 8 }
11
Dãy Con Tăng Dài Nhất

 Bài toán con: Tìm dãy con tăng dài nhất 
kết thúc tại phần tử thứ k

 Thuật toán

 Nếu tất cả các phần tử trước k đều lớn hơn
hoặc bằng S[k], trả về dãy con chỉ chứa S[k]

 Nếu có t phần tử đứng trước k nhỏ hơn S[k], 
gọi W là dãy dài nhất trong các dãy con tăng 
kết thúc tại các phần tử này. Trả về W ∪ S[k]
12
s1 14 {14}
s2 1 {1}
s3 17 {14|1, 17}
s4 2 {1, 2}
s5 16
s6 17
s7 3
s8 15
s9 4
s10 1
s11 5
s12 18
s13 13
s14 6
s15 7
s16 19
s17 8
s18 12
s19 1
s20 9
s21 10
s22 8
Dãy Con Tăng Dài Nhất
S = { 14, 1, 17, 2, 16, 
17, 3, 15, 4, 1, 5, 18, 
13, 6, 7, 19, 8, 12, 1, 
9, 10, 8 }
Sử dụng tất cả các Si 
đã được xây dựng để
tiếp tục xây dựng Sj
13
s1 14 {14}
s2 1 {1}
s3 17 {14|1, 17}
s4 2 {1, 2}
s5 16 {1, 2, 16}
s6 17 {1, 2, 16, 17}
s7 3 {1, 2, 3}
s8 15 {1, 2, 3, 15}
s9 4 {1, 2, 3, 4}
s10 1 {1}
s11 5 {1, 2, 3, 4, 5}
s12 18 {1, 2, 3, 4, 5, 18}
s13 13 {1, 2, 3, 4, 5, 13}
s14 6 {1, 2, 3, 4, 5, 6}
s15 7 {1, 2, 3, 4, 5, 6, 7}
s16 19 {1, 2, 3, 4, 5, 6, 7, 19}
s17 8 {1, 2, 3, 4, 5, 6, 7, 8}
s18 12 {1, 2, 3, 4, 5, 6, 7, 8, 12}
s19 1 {1}
s20 9 {1, 2, 3, 4, 5, 6, 7, 8, 9}
s21 10 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
s22 8 {1, 2, 3, 4, 5, 6, 7, 8}
Dãy Con Tăng Dài Nhất
S = { 14, 1, 17, 2, 16, 
17, 3, 15, 4, 1, 5, 18, 
13, 6, 7, 19, 8, 12, 1, 
9, 10, 8 }
Sử dụng tất cả các Si 
đã được xây dựng để
tiếp tục xây dựng Sj
14
Ba Lô
Có N đồ vật, đồ vật i có khối lượng wi và giá trị ti
1 chiếc ba lô có thể mang được không quá M kg
Tìm cách mang một số đồ vật để tổng giá trị lấy
được là lớn nhất.
Ví dụ
N = 5, M = 10
i A B C D E
wi 1 3 5 7 9
ti $100 $200 $301 $400 $500
15
Ba Lô
for mọi ô [x, y]
if x = 0 và y = 0 then
cell[x, y] = 0kg $0 {}
else
gọi m là đồ vật thêm vào ở cột y
gọi w là khối lượng của m
if w > khối lượng cực đại của hàng
cell[x, y] = cell[x, y-1]
else
cell[x, y] = max {cell[x, y-1], (cell[x-w, y-1] U {m})}
16
tập rỗng A A/B A/B/C A/B/C/D A/B/C/D/E
kg ≤0 0kg $0 {} 0kg $0 {} 0kg $0 {} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤1 0kg $0 {} 1kg $100 {A} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤2 0kg $0 {} 1kg $100 {A} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤3 0kg $0 {} 1kg $100 {A} 3kg $200 {B} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤4 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤5 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤6 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤7 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤8 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤9 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {}
kg ≤10 0kg $0 {} 1kg $100 {A} ?kg $? {} ?kg $? {} ?kg $? {} ?kg $? {}
Đồ vật Khối lượng Giá trị
A 1kg $100 
B 3kg $200 
C 5kg $301 
D 7kg $400 
E 9kg $500 
Ba Lô
for mọi ô [x, y]
if x = 0 và y = 0 then
cell[x, y] = 0kg $0 {}
else
gọi m là đồ vật thêm vào ở cột y
gọi w là khối lượng của m
if w > khối lượng cực đại của hàng
cell[x, y] = cell[x, y-1]
else
cell[x, y] = max {cell[x, y-1], (cell[x-w, y-1] U {m})}
17
Đồ vật Khối lượng Giá trị
A 1kg $100 
B 3kg $200 
C 5kg $301 
D 7kg $400 
E 9kg $500 
tập rỗng A A/B A/B/C A/B/C/D A/B/C/D/E
kg ≤0 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {} 0kg $0 {}
kg ≤1 0kg $0 {} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A}
kg ≤2 0kg $0 {} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A} 1kg $100 {A}
kg ≤3 0kg $0 {} 1kg $100 {A} 3kg $200 {B} 3kg $200 {B} 3kg $200 {B} 3kg $200 {B}
kg ≤4 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 4kg $300 {A, B} 4kg $300 {A, B} 4kg $300 {A, B}
kg ≤5 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 5kg $301 {C} 5kg $301 {C} 5kg $301 {C}
kg ≤6 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 6kg $401 {A,C} 6kg $401 {A,C} 6kg $401 {A,C}
kg ≤7 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 6kg $401 {A,C} 6kg $401 {A,C} 6kg $401 {A,C}
kg ≤8 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 8kg $501 {B,C} 8kg $501 {B,C} 8kg $501 {B,C}
kg ≤9 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 9kg $601 {A, B, C} 9kg $601 {A, B, C} 9kg $601 {A, B, C}
kg ≤10 0kg $0 {} 1kg $100 {A} 4kg $300 {A, B} 9kg $601 {A, B, C} 9kg $601 {A, B, C} 9kg $601 {A, B, C}
Dãy Con Chung Dài Nhất
Cho 2 dãy [1	. . ] và [1	. . ], tìm dãy con 
chung dài nhất của chúng.
: A B C B D A B
: B D C A B A
Dãy con chung: ? AB ? BCDB ? BCBA
18
Dãy Con Chung Dài Nhất
Cho 2 dãy [1	. . ] và [1	. . ], tìm dãy con 
chung dài nhất của chúng.
: A B C B D A B
: B D C A B A
LCS(, ) = BCBA
19
Dãy Con Chung Dài Nhất

 Kiểm tra tất cả các dãy con của [1	. . ]
xem có phải dãy con của [1	. . ] không

 Phân tích

 Kiểm tra =   cho mỗi dãy con.

 Có 2 dãy con của .

 Thời gian chạy xấu nhất =  2 , thời gian
hàm mũ.
20
Cắt Dây

 Đọc Mục 15.1 Tr.360
21