Phần thứ nhất
LÝ THUYẾT TỔ HỢP Combinatorial Theory
1
Toán rời rạc
Fall 2009
Nội dung
Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp
2
Toán rời rạc
Chương 3 BÀI TOÁN LIỆT KÊ
3
Toán rời rạc
NỘI DUNG
1. Giới thiệu bài toán
2. Thuật toán và độ phức tạp
3. Phương pháp sinh
4. Thuật toán quay lui
4
Toán rời rạc
Giíi thiÖu bµi to ¸n
ư
ả
t c c u h ướ
Bài toán đ a ra danh sách t ấ
ình t ượ c đ
ổ ợ h p ọ c g i
h p.
ườ
ố ượ
ổ ợ ầ
Do s l ấ ớ
ệ h p c n li ướ ấ
ng t kê th ư c c u hình ch a
ố ố ậ
ầ ử
là n! c a n ph n t
là n!/(m!(n
ấ ả ấ ộ ố tho mãn m t s tính ch t cho tr ổ ợ ệ t kê t là bài toán li ấ ng c u hình t ả là r t l n ngay c khi kích th l n:ớ • S hoán v c a n ph n t ầ ử ị ủ • S t p con m ph n t ầ ử ủ
m)!
ệ
ế
ả
Do đó n có quan ni m th nào là gi
i bài
5
ầ ệ t kê t
toán li
ổ ợ h p
Giíi thiÖu bµi to ¸n
ổ ợ là gi
Bài toán li
ư
ả ượ i đ ậ ộ thu t toán ượ ấ c t
ế c n u đ ể t
t xây d ng đ
ả
t kê t h p ị ể xác đ nh m t ể ầ ượ ự ầ ình c n quan tâm. ả ả ệ án li
t kê ph i đ m b o 2 yêu
ộ ấ ượ ặ ạ i m t c u h c l p l ộ ấ ượ ỏ c b sót m t c u h
ình, ình.
ệ nh ta có th theo đó có th l n l ả ấ c các c u h ậ ộ M t thu t to ầ ơ ả c u c b n: • Không đ • không đ
6
Chương 3. Bài toán liệt kê
1. Giới thiệu bài toán
2. Thuật toán và độ phức tạp
3. Phương pháp sinh
4. Thuật toán quay lui
7
Toán rời rạc
Khái niệm bài toán tính toán
ị
Đ nh nghĩa.
ị ạ ừ ậ t p các xâu nh ộ
ữ ạ
ị
ậ
phân đ dài h u h n vào t p các xâu nh phân đ dài h u h n:
{0, 1}*.
ể ể
ễ
ướ ạ
ị
i d ng xâu nh phân là
ủ
ị
ễ
ướ ạ
Ax = b có th bi u di n d
Bài toán tính toán F là ánh x t ữ ạ ộ F : {0, 1}* (cid:0) Ví d : ụ ề ỗ ố M i s nguyên x đ u có th bi u di n d ệ ế ế cách vi t trong h đ m nh phân c a nó. ế ươ ệ H ph ng trình tuy n tính ể ố ủ
ể ể ủ
ị
ễ
ơ b.
ứ
ộ
ể ể
ễ
i d ng xâu ầ ủ là ghép n i c a các xâu bi u di n nh phân c a các thành ph n c a ma tr n ậ A và vect ế Đa th c m t bi n: P(x) = a0 + a1 x + ... + an xn, ị hoàn toàn xác đ nh b i dãy s
ố n, a0, a1, ..., an, mà đ bi u di n dãy
ị
ở ể ử ụ ố s này chúng ta có th s d ng xâu nh phân.
8
Khái niệm thuật toán
ậ
Ta hi u thu t toán gi
ả ộ
Đ nh nghĩa. ủ ụ
ể
ể ị ệ
ặ ạ ộ ầ
ầ
ồ ượ c c n th c hi n đ thu đ
ự ướ ủ c c a bài toán. ặ
ư
Thu t toán có các đ c tr ng sau đây:
ừ ộ ậ ữ ệ ậ ậ m t t p (Input): Thu t toán nh n d li u vào t
ậ ớ (Output): V i m i t p các d li u đ u vào, thu t
ị i bài toán đ t ra là ữ ộ m t th t c xác đ nh bao g m m t dãy h u h n các ướ ầ c đ u ra cho m t đ u b vào cho tr ậ • Đ u vào ầ nào đó. • Đ u ra ầ ư
ỗ ậ ữ ệ ươ ứ ầ ả ủ ớ ờ
ng ng v i l ướ ủ ả ữ ệ i gi ậ c c a thu t toán đ i c a bài toán. ượ c mô t toán đ a ra các d li u t • Chính xác (Precision): Các b
9
chính xác.
Khái niệm thuật toán
ầ
ạ
ộ ố ữ
ư ả ể ấ ớ
đ b
ự
ệ
ả ượ ầ
ủ ộ ế
ị
c th c hi n thu t toán đ ụ ướ
ướ
ỉ c tr
c.
ụ
ể
ậ
(Generality): Thu t toán có th áp d ng
ạ
• H u h n ậ ạ (Finiteness): Thu t toán c n ph i đ a ữ ượ ầ c đ u ra sau m t s h u h n (có th r t l n) ọ ầ ướ ớ c v i m i đ u vào. • Đ n tr ế ị (Uniqueness): Các k t qu trung gian c a ơ ị ậ ướ ừ t ng b c xác đ nh m t ộ ơ cách đ n tr và ch ph thu c vào đ u vào và các k t ả ủ qu c a các b • T ng quát ổ ọ ể ả đ gi
i m i bài toán có d ng đã cho.
10
Độ phức tạp của thuật toán
Đ ph c t p tính toán ạ
ứ ạ ượ ị ư
ộ ượ ậ ủ c a thu t toán đ ậ c xác đ nh nh là ỏ ử ụ l ng tài nguyên các lo i mà thu t toán đòi h i s d ng.
ạ ộ ờ ọ ớ Có hai lo i tài nguyên quan tr ng đó là th i gian và b nh .
ượ ậ
ư ệ ế ấ
ự ạ ệ Vi c tính chính xác đ c các lo i tài nguyên mà thu t toán đòi ế ỏ h i là r t khó. Vì th ta quan tâm đ n vi c đ a ra các đánh giá ạ ượ sát th c cho các đ i l ng này.
Trong giáo trình này ta đ c bi
ặ ờ
ế ẽ ọ ờ ệ ậ t quan tâm đ n đánh giá th i gian th i gian tính
11
ệ ầ ế ể ự c n thi t đ th c hi n thu t toán mà ta s g i là ậ ủ c a thu t toán.
Độ phức tạp của thuật toán
Rõ ràng: Th i gian tính ph thu c vào d li u vào.
ữ ệ ụ ờ ộ
Ví d : Vi c nhân hai s nguyên có 3 ch s đòi h i th i gian ố
ụ ữ ố ệ ờ
ệ ẳ ớ ố khác h n so v i vi c nhân hai s nguyên có 3*10 ỏ 9 ch s !ữ ố
ữ ộ (hay đ dài d
Đ nh nghĩa. li u vào
Ta g i ọ kích th ầ ố ị ệ c d li u đ u vào ễ ế ể ể ướ ữ ệ ầ t đ bi u di n nó. ) là s bít c n thi
ầ ố
ướ ữ ệ ủ ụ Ví d : N u kích th ế x, y là đ u vào cho bài toán nhân 2 s nguyên, thì c d li u vào c a bài toán là n = (cid:0) log |x|(cid:0) + (cid:0) log |y| (cid:0) .
Ta s tìm cách đánh giá th i gian tính c a thu t toán b i m t
ủ ậ ở ộ ẽ
12
ủ ộ ữ ệ ờ hàm c a đ dài d li u vào.
Phép toán cơ bản
ằ
ơ
ờ
ị
Đo th i gian tính b ng đ n v đo nào?
ị
Ta g i ọ phép toán c b n
Đ nh nghĩa.
ờ
ị
ể ự ố
ộ ằ
ụ
ộ
ơ ả là phép ở ặ ớ ệ toán có th th c hi n v i th i gian b ch n b i ướ ữ c d m t h ng s không ph thu c vào kích th li u. ệ
ủ
ậ
ờ
ơ ả
ả
ẽ Đ tính toán th i gian tính c a thu t toán ta s ự ố s phép toán c b n mà nó ph i th c
ể đ m ế hi n. ệ
13
Các loại thời gian tính
Chúng ta sẽ quan tâm đến:
ầ ế ể ự ậ i thi u c n thi
ể ầ ệ ờ
ố ủ th i gian tính t ớ t đ th c hi n thu t toán v i ư ậ ẽ ướ n. Th i gian nh v y s c ớ ầ ậ ấ c a thu t toán v i đ u t nh t
ấ ầ ệ ậ
ầ ờ
ồ ủ th i gian tính t ớ ế ể ự t đ th c hi n thu t toán v i ư ậ ẽ ướ n. Th i gian nh v y s c ớ ầ ậ ấ c a thu t toán v i đ u i nh t
ầ ờ ệ ậ
• Th i gian t ờ ố ọ ộ ữ ệ m i b d li u đ u vào kích th ờ ọ ượ đ c g i là c ướ n. vào kích th • Th i gian nhi u nh t c n thi ề ờ ọ ộ ữ ệ m i b d li u đ u vào kích th ờ ọ ượ c g i là đ c ướ n. vào kích th • Th i gian trung bình c n thi
ầ ư ậ ế ể ự c
14
ờ ủ ạ ữ ậ t p h u h n các đ u vào kích th ẽ ượ ọ s đ c g i là t đ th c hi n thu t toán trên ờ ướ n. Th i gian nh v y ậ c a thu t toán. th i gian tính trung bình
Ký hiệu tiệm cận Asymptotic Notation
, O, (cid:0) ượ
ố ớ
ậ
ị
ị
(cid:0) Đ c xác đ nh đ i v i các hàm nh n giá tr nguyên
không âm
ố ộ
ủ
ể
Dùng đ so sánh t c đ tăng c a hai hàm
ượ ử ụ
ể
ả ờ
ủ
ậ
Đ c s d ng đ mô t
th i gian tính c a thu t
toán
ể
ờ
Thay vì nói chính xác, ta có th nói th i gian tính là,
ẳ
ạ , (cid:0) ch ng h n
(n2)
15
Ký hiệu (cid:0)
g(n) cho tr ậ (g(n)) là t p các hàm
ồ ạ (g(n)) = {f(n) | t n t
n0 }
ớ c1g(n) (cid:0)
cướ , ta ký hi u ệ (cid:0) ằ i các h ng s f(n) (cid:0) ệ
ậ
g(n) là đánh giá ti m c n đúng
16
ố ớ Đ i v i hàm (cid:0) 0 (cid:0) Ta nói r ng ằ ố c1, c2 và n0 sao cho ọ n (cid:0) c2g(n), v i m i cho f(n)
Ví dụ
(n2)
ủ
ằ
ố n0, c1, và c2 thì b t ấ
ứ
10n2 3n = (cid:0) ị ớ V i giá tr nào c a các h ng s ẳ đ ng th c sau đây là đúng v i
ớ n ≥ n0:
c1n2 ≤ 10n2 3n ≤ c2n2
Ta có th l y
ơ ấ ớ
ệ ố
ấ
ớ ố ể ấ c1 bé h n h s c a s h ng v i s ệ ố ủ ố ạ ẳ ơ c2 l y l n h n h s này, ch ng
mũ cao nh t, còn h n: ạ
c1=9 < 10 < c2 = 11, n0 = 10.
ứ
ủ
ể
17
ố ộ T ng quát, đ so sánh t c đ tăng c a các đa th c, ớ ố
ố ạ
ổ ấ ầ c n nhìn vào s h ng v i s mũ cao nh t
Ký hiệu O
ướ ệ O(g(n)) là t p các hàm
Đ i v i hàm ố ớ O(g(n)) = {f(n) | t n t f(n) (cid:0)
n0 }
g(n) cho tr ồ ạ c, ta ký hi u ố ươ ằ i các h ng s d ậ c và n0 sao cho:
18
ớ cg(n) v i m i ệ ậ Ta nói g(n) là c n trên ti m c n ng ọ n (cid:0) ậ c a ủ f(n)
Ví dụ: Ký hiệu O lớn
f(n) = n2 + 2n + 1 là O(n2)
ứ ầ
ỉ n2 + 2n + 1 ≤ c*n2
Ch ng minh: • C n ch ra: ằ v i ớ c là h ng s nào đó và khi
ố n > n0 nào đó
ọ n ≥ 1
Ta có: 2n2 ≥ 2n khi n ≥ 1 và n2 ≥ 1 khi n ≥ 1 Vì v yậ ớ n2 + 2n + 1 ≤ 4*n2 v i m i ố c = 4, và n0=1 Nh v y h ng s
19
ư ậ ằ
Ví dụ: Ký hiệu O lớn
Rõ ràng: N u ế f(n) là O(n2) thì nó cũng là O(nk) v i ớ k > 2. f(n) = n2 + 2n + 1(cid:0) O(n). Ch ng minh: ả ạ ả ử ứ Ph n ch ng. Gi ể s ố c và s ố n0 đ cho:
ượ ằ ứ ả i, khi đó ph i tìm đ s trái l c h ng
ớ n2 + 2n + 1 ≤ c*n khi n ≥ n0 Suy ra n2 < n2 + 2n + 1 ≤ c*n v i m i ọ n ≥ n0
T đó ta thu đ c: ọ n ≥ n0 ?! ớ n < c v i m i
20
ừ ượ
Ký hiệu (cid:0)
ướ
g(n) cho tr
Đ i v i hàm ố ớ ký hi u ệ (cid:0)
c, ta (g(n)) là t p các hàm: ậ
(cid:0)
i các
ng
ồ ạ c và n0 sao cho
ố ươ f(n)
ọ n (cid:0)
(g(n)) = {f(n)| t n t ằ h ng s d cg(n) (cid:0) ớ v i m i
n0 }
ậ ướ ệ
i ti m c n
Ta nói g(n) là c n d
ậ cho f(n)
21
Ví dụ: Ký hiệu (cid:0)
(n2)
ỉ
c*n2
f(n) = n2 2000n là (cid:0) ứ Ch ng minh: n2 2000n (cid:0) • C n ch ra: ầ ố ằ v i ớ c là h ng s nào đó và khi
n > n0 nào đó
ớ
0.5*n2 v i m i
ọ n ≥ 10000
0
Ta có: n2 2000n (cid:0) (vì n2 2000n 0.5*n2 = 0.5*n2 2000n = n(0.5*n 2000) (cid:0) khi n ≥ 10000) ằ ư ậ Nh v y h ng s
ố c = 1, và n0=1
22
Ví dụ: Ký hiệu (cid:0)
(nk) v i ớ k < 2.
(cid:0)
Rõ ràng: N u ế f(n) là (cid:0) Ch ng minh: Ph n ch ng. Gi ể
ượ ằ (n2) thì nó cũng là (cid:0) (n3). ả ứ ả ạ i, khi đó ph i tìm đ c h ng s trái l
f(n) = n2 2000n (cid:0) ả ử ứ s ố c và s ố n0 đ cho:
c*n3 khi n ≥ n0
c*n3 khi n ≥ n0
23
n2 – 2000n (cid:0) Suy ra n2 (cid:0) ừ T đó ta thu đ n2 – 2000n (cid:0) ượ c: ớ n v i m i 1/c (cid:0) ọ n ≥ n0 ?!
Liên hệ giữa (cid:0)
, (cid:0)
, O
ố ớ
Đ i v i hai hàm b t k
ấ ỳ g(n) và f(n),
f(n) = (cid:0)
(g(n))
ỉ
khi và ch khi
f(n) = O(g(n)) và f(n) = (cid:0)
(g(n)).
t c làứ
(cid:0)
(g(n)) = O(g(n))(cid:0)
(g(n))
24
(cid:0) (cid:0) (cid:0)
Chú ý
Giá tr c a
ả ứ ấ trong ch ng minh ị ủ n0 và c không ph i là duy nh t
ậ ứ ệ công th c ti m c n.
Ch ng minh r ng 100
ứ ằ n + 5 = O(n2)
ớ ọ n ≥ 5
ố ầ ằ
ớ ọ n ≥ 1
• 100n + 5 ≤ 100n + n = 101n ≤ 101n2 v i m i n0 = 5 và c = 101 là các h ng s c n tìm • 100n + 5 ≤ 100n + 5n = 105n ≤ 105n2 v i m i n0 = 1 và c = 105 cũng là các h ng s c n tìm
ố ầ ằ
Ch c n tìm các h ng
ỉ ầ ằ ấ ẳ ứ ả c và n0 nào đó tho mãn b t đ ng th c
25
ứ ệ ậ ị trong đ nh nghĩa công th c ti m c n.
Ký hiệu tiệm cận trong các đẳng thức
ứ
ứ
ể
ể
ớ ố ộ
ậ
ế ượ ử ụ Đ c s d ng đ thay th các bi u th c ch a các toán ạ h ng v i t c đ tăng ch m
Ví d ,ụ
(n)
4n3 + 3n2 + 2n + 1 = 4n3 + 3n2 + (cid:0) = 4n3 + (cid:0)
(n2) = (cid:0)
ế
ộ hàm nào
(f(n)) thay th cho m t
, (cid:0)
ụ
ế
(n2) thay th cho 3
n2 + 2n + 1
(n3) ứ , (cid:0) ẳ Trong các đ ng th c (cid:0) đó g(n) (cid:0) (f(n)) • Trong ví d trên
26
So sánh các hàm số
f (cid:0)
b
g (cid:0)
a (cid:0)
f (n) = O(g(n)) (cid:0) (g(n)) (cid:0) f (n) = (cid:0) (g(n)) (cid:0) f (n) = (cid:0) f (n) = o(g(n)) (cid:0) f (n) = (cid:0) (cid:0) (g(n)) (cid:0)
a (cid:0) b a (cid:0) b a = b a < b a > b
27
Cách nói về thời gian tính
Nói “Th i gian tính là
ể
ấ
ố O(f(n))” hi u là: Đánh giá trong tình ườ ng nói: “Đánh giá O(f(n))” O(f(n)). Th ấ ồ i nh t là
ấ ượ ồ i nh t đ c xác ờ ố ồ hu ng t i nh t (worst case) là ờ th i gian tính trong tình hu ng t • Nghĩa là th i gian tính trong tình hu ng t
ở ờ ộ ị đ nh b i m t hàm nào đó g(n)(cid:0) ố (cid:0) O(f(n))
(cid:0) ố ố ờ
ờ ấ (f(n))” hi u là: Đánh giá trong tình hu ng t ể (f(n)). Th t ng nói: “Đánh giá th i gian tính
(cid:0) ố ườ (f(n))”
“Th i gian tính là (cid:0) nh t (best case) là ấ ố t nh t là trong tình hu ng t • Nghĩa là th i gian tính trong tình hu ng t
ố ấ ượ t nh t đ c xác
28
(cid:0) ở ờ ộ ị đ nh b i m t hàm nào đó ố (f(n)) g(n) (cid:0)
Đồ thị của một số hàm cơ bản
29
Tên gọi của một số tốc độ tăng
Hàm Tên g iọ
log
ế log n n tuy n tính
n log n
n log n n2 ngươ
n3
30
ố ươ 2n ằ nk (k là h ng s d ng) bình ph b c 3ậ hàm mũ đa th cứ
Ví dụ phân tích thuật toán
ậ ế ầ ự ể ả đ gi i bài toán
ầ Ví d .ụ Xét thu t toán tìm ki m tu n t Đ u vào:
ầ ử ặ ế n và dãy sốs1, s2, . . . , sn. ị V trí ph n t có giá tr ị key ho c là n+1 n u không tìm
ầ Đ u ra: th y.ấ
function Linear_Search(s,n,key); begin
i:=0; repeat
i:=i+1; until (i>n) or (key = si); Linear_Search := i;
end;
31
Toán rời rạc
Ví dụ phân tích thuật toán
C n đánh giá th i gian tính t
ầ ấ ồ ấ ố t nh t, t
ủ ủ ầ
ở ố ầ ậ ậ ự ệ ệ
ờ i nh t, trung bình c a ờ ớ ộ n. Rõ ràng th i gian tính c a thu t toán v i đ dài đ u vào là ể thu t toán có th đánh giá b i s l n th c hi n câu l nh i:=i+1 trong vòng l p ặ repeat.
N u ế s1 = key thì câu l nh ệ ờ ầ
ặ i:=i+1 trong thân vòng l p repeat
ệ ố ấ ủ ậ th c hi n 1 l n. Do đó th i gian tính t t nh t c a thu t toán là
N u ế key không có m t trong dãy đã cho, thì câu l nh ậ
(cid:0) ự (1).
ấ ủ ầ ồ ặ ế ờ ệ n l n. Vì th th i gian tính t ệ i:= i+1 i nh t c a thu t toán là
32
Toán rời rạc
ự th c hi n O(n).
Ví dụ phân tích thuật toán
Cu i cùng, ta tính th i gian tính trung bình c a thu t toán.
ủ ậ ố
ủ ứ i c a dãy ( key = si) thì câu
ệ l nh
• N u ế key không có m t trong dãy đã cho thì câu l nh
ệ i l n (ầ i = 1, 2, ..., n), ệ i := i+1
ả
T đó suy ra s l n trung bình ph i th c hi n câu l nh
ờ • N u ế key tìm th y ấ ở ị v trí th ự ả i := i+1 ph i th c hi n ặ ệ n l n. ầ ự ph i th c hi n ố ầ ừ ự ệ ệ ả i := i+1
là
[(1 + 2 + . . . + n) + n] /(n+1) = [n(n+1)/2 + n]/(n+1).
ọ n (cid:0) 1.
Ta có n/4 (cid:0) ớ n. v i m i ờ V y th i gian tính trung bình c a thu t toán là
33
Toán rời rạc
(cid:0) [n(n+1)/2 + n]/(n+1) (cid:0) ậ ủ ậ (n).
Chương 3. Bài toán liệt kê
1. Giới thiệu bài toán
2. Thuật toán và độ phức tạp
3. Phương pháp sinh
4. Thuật toán quay lui
34
Toán rời rạc
3. PHƯƠNG PHÁP SINH
ơ ồ
3.1. S đ thu t toán 3.2. Sinh các c u hình t
ầ ử ủ ậ n ph n tầ ử
c a t p
ị ủ n ph n tầ ử
ậ ổ ợ ơ ả ấ h p c b n • Sinh xâu nh phân đ dài ộ ị n • Sinh t p con ậ m ph n t • Sinh hoán v c a
35
SƠ ĐỒ THUẬT TOÁN
ụ ể ệ
Ph t
ế ệ ề ặ i bài toán li ượ ự ể ả ươ ng pháp sinh có th áp d ng đ gi ư ổ ợ h p đ t ra n u nh hai đi u ki n sau đ t kê ệ c th c hi n:
ứ ự ậ
ị ầ ể
ấ ấ ộ ượ ể c m t th t 1) Có th xác đ nh đ trên t p các c u ượ ừ ệ ổ ợ ị t kê. T đó có th xác đ nh đ h p c n li c ứ ự ố ình cu i cùng trong th t ình đ u tiên và c u h
ị hình t c u hấ ầ đã xác đ nh.
ự ượ ư ả c u h 2) Xây d ng đ
ố ừ ấ ậ c thu t toán t ấ ư cu i cùng đang có, đ a ra c u h ình ch a ph i là ế ế ình k ti p nó.
Thu t toán nói đ n trong đi u ki n 2) đ
ề ệ ượ ọ ậ ậ c g i là Thu t
36
ế ế ế toán Sinh k ti p
Thuật toán sinh
procedure Generate; Begin
ầ ự >;
ấ
ấ >; ư
ấ ư ố ) <Đ a ra c u hình đang có
if (c u hình đang có ch a là cu i cùng ế ế
then end; 37 End. ự Sinh_k _ti p là th t c ế ế
ế ế ề ủ ụ ẽ ấ
ứ ự sinh k ti p đã xây d ng
Th t c này s xây d ng c u h
c u hấ
ình đang có trong th t ậ toán
ệ
ủ ụ th c hi n thu t
ự trong đi u ki n 2)
ệ
.
ủ
ế ế
ự
ình k ti p c a
ị đã xác đ nh. ấ ậ
Chú ý: Do t p các c u hình t ạ ệ
c th t ế ế ượ ể ổ ợ ầ
t kê là
h p c n li
ứ ự
ượ
ị
ể
ữ
h u h n nên luôn có th xác đ nh đ
ị
ứ ự ầ
c n xác đ nh sao cho
trên nó. Tuy nhiên, th t
ậ
ự
c thu t toán Sinh k ti p.
có th xây d ng đ 38 ơ ồ 3.1. S đ thu t toán 3.2. Sinh các c u hình t h p c b n c a t p ầ ử ủ ậ n ph n tầ ử ị ủ n ph n tầ ử 39 Sinh các dãy nh phân đ dài n 40 ộ t kê t ị
t c các dãy nh phân đ dài Bài toán: Li {0, 1}. ấ ả
ệ
n: b1 b2 ... bn, trong đó bi (cid:0) nhiên: ễ ị
ủ
di n nh phân c a m t s nguyên b = b1 b2 ... bn là bi u ể
p(b) ị ứ ự ự
t
ỗ
ị
Ta nói dãy nh phân ứ ự ự ị Th t
Xem m i dãy nh phân
ộ ố
c ướ dãy
b = b1 b2 ... bn đi tr
nhiên
t nh phân
và ký hi u làệ b' = b'1 b'2 ... b'n trong th t
b b' n u ế p(b) < p(b'). 41 41 ệ ị
c li
nhiên trong Ví d :ụ Khi n=3, các
ộ
dãy nh phân đ dài 3
ứ
ượ
t kê theo th
đ
ự ự
t
t
ờ
ả
b ng b n Dễ thấy thứ tự này
trùng với thứ tự từ
điển bb
000000
001001
010010
011011
100100
101101
110110
111111 pp((bb))
00
11
22
33
44
55
66
77 42 Dãy đ u tiên s là 0 0 ... 0,
Dãy cu i cùng là 1 1 ... 1.
Gi ẽ ầ
ố
s T đó ta c ạ ố
ậ ằ ộ
c b ng cách c ng thêm 1 (theo ó qui t c sinh dãy k ti p nh sau:
ầ ả ư
ứ ự i=n, n1, ..., 1) tho mãn ớ ớ ấ ả j > i. Dãy m i thu đ t c bi = 0.
ượ
c ả ử b1 b2 ... bn là dãy đang có.
ế
ồ
ế
N u dãy này g m toàn s 1, k t thúc,
ượ
ế ế
Trái l
i, dãy k ti p nh n đ
ệ ạ
ớ
i.
modun 2, có nh ) vào dãy hi n t
ế ế
ắ
i ạ bi = 1 và bj = 0 v i t 43 ừ
• Tìm i đ u tiên (theo th t
• Gán l
ẽ
s là dãy c n t ầ ìm. ộ ị Xét dãy nh phân đ dài 10: b = 1101011111. Ta có i = 5.
Do đó, đ t ặ b5 = 1, và bi = 0, i = 6, 7, 8, 9, 10, ta ươ ị thu đ ế ế
c xâu nh phân k ti p là 1101100000. 1101011111 44 t 1 1 ... 1 ứ ự ừ ể ủ
đi n c a
*) procedure Next_Bit_String;
ế ế
ị
(* Sinh xâu nh phân k ti p theo th t
xâu đang có b1 b2 ... bn (cid:0) begin i:=n; while bi = 1 do begin bi = 0;
i:=i1; 45 end;
bi := 1;
end; 46 Bµi to¸n ®Æt ra lµ: Cho X = {1, 2, ... , n}.
H·y liÖt kª c¸c tËp con m phÇn tö cña X. Mçi tËp con m phÇn tö cña X cã thÓ biÓu diÔn bëi bé cã thø tù gåm m thµnh
phÇn a = (a1, a2, ... , a m) tho¶ m·n
1 (cid:0) n. a1 < a2 < ... < a m (cid:0) 47 Ta nãi tËp con a = (a1, a2,..., am) ®i tríc
tËp con a' = (a'1, a'2, ... , a'm) trong thø tù
tõ ®iÓn vµ ký hiÖu lµ a a', nÕu tìm ®
îc chØ sè k (1 (cid:0) m ) sao cho k (cid:0)
a1 = a'1 , a 2 = a'2, . . . , a k-1 = a'k-1,
ak < a'k . 48 Các t p con 3 ph n t
ứ ự ừ ể
t ượ ệ c li t 1
1
1
1
1
1
2
2
2
3 2
2
2
3
3
4
3
3
4
4 3
4
5
4
5
5
4
5
5
5 49 ậ
kê theo th t ầ ử ủ X = {1, 2, 3, 4, 5} đ
c a
ư
đi n nh sau Gi ậ
ậ ầ
T p con đ u tiên là
ố
T p con cu i cùng là (1, 2, ... , m)
(nm+1, nm+2, ..., n). s ậ ằ ứ ự ừ ể
t
ế
ắ ệ ổ ự
ố ớ ậ
ừ 50 ả
ư
ậ
ả ử a=(a1, a2, ... , am) là t p con đang có ch a ph i
ế ế
ố
cu i cùng, khi đó t p con k ti p trong th t
đi n có
ự
ể
th xây d ng b ng cách th c hi n các quy t c bi n đ i
:
sau đ i v i t p đang có
a1, a2,..., am ph n tầ ử ai (cid:0) nm+i,
• Tìm t
ả
bên ph i dãy
• Thay ai b i ở ai + 1;
• Thay aj b i ở ai + j i, v iớ j = i+1, i+2,..., m. 6, m = 4. ậ t ượ ậ c t p con (1, 2, 5, 6)
(3, 4, 5, 6)
thay a2 = 3, và a3 = 4, a4 = 5, ta đ ế ế
k ti p (1, 3, 4, 5). 51 51 ế ế ậ ứ ự ừ ể
t ủ ậ procedure Next_Combination;
(* Sinh mt p con k ti p theo th t
c a t p con đi n
(a1, a2,..., am) (cid:0) (nm+1,...,n) *) begin i:=m; while ai = nm+i do i:=i1;
ai:= ai + 1;
for j:=i+1 to m do aj := ai + j i;
end; 52 52 53 Bµi to ¸n: Cho X = {1, 2, ... , n}, h·y liÖt kª c¸c ho¸n vÞ tõ n phÇn tö cña X. Mçi ho¸n vÞ tõ n phÇn tö cña X cã thÓ
biÓu diÔn bëi bé cã thø tù gåm n thµnh
phÇn a = (a1, a2, ... , a n)
tho¶ m·n
ai (cid:0) X , i = 1, 2,..., n , a p (cid:0) aq, p (cid:0) q. 54 Ta nãi ho¸n vÞ a = (a1, a2,..., a n) ®i tríc
ho¸n vÞ a' = (a'1, a'2, ... , a'n) trong thø tù
tõ ®iÓn vµ ký hiÖu lµ a a', nÕu tìm ®
îc chØ sè k (1 (cid:0) n) sao cho: k (cid:0) a1 = a'1 , a 2 = a'2, ... , a k-1 = a'k-1, ak < a'k . 55 C¸c ho¸n vÞ tõ 3 phÇn tö cña X ={1, 2, 3}
®îc liÖt kª theo thø tù tõ ®iÓn nh sau 2
1
1 3
1
2
3
2
1
3
2
3 3
2
3
1
2
1 56 ... , n)
n, n1, ..., 1). ư ả ị ầ
Hoán v đ u tiên: (1, 2,
ị ố
Hoán v cu i cùng: (
Gi s ị
ể ự ị ph i qua trái hoán v đang có ch s ị ế ế
ổ ế ỉ ố ớ ầ
ấ ả ả
ỉ ố j đ u tiên tho
mãn aj < aj+1 (nói cách khác: j là ch s l n nh t tho mãn
aj < aj+1); ấ ớ ố ố ở bên ơ aj trong các s • Tìm ak là s nh nh t còn l n h n
ỏ 57 ạ ừ aj+1 đ nế an . ph iả aj ;
• Đ i ch
ỗ aj v iớ ak ;
ổ
• L t ng
ượ
ậ
c đo n t ố
ả ử a = (a1, a2, ... , an) là hoán v ch a ph i cu i
ờ
cùng, khi đó hoán v k ti p nó có th xây d ng nh
ệ
ự
th c hi n các bi n đ i sau:
• Tìm t
ả
ừ Ví dụ ị s đang có hoán v (3, 6, 2, 5, 4, 1), c n xây ị ế ế ầ
ứ ự ừ ể
đi n.
t Ta có ch s ả ử
Gi
ự
d ng hoán v k ti p nó trong th t
ỉ ố j = 3 (a3 =2 < a4 = 5). ỏ ớ ố ấ
S nh nh t còn l n h n ơ a3 trong các s bên
ỗ a3 v iớ a5 ta thu
ổ ố
ả ủ a3 là a5 = 4. Đ i ch
ph i c a
ượ
c (3
đ , 6, 4, 5, 2, 1), ứ ự Cu i cùng, l c th t đo n ạ a4 a5 a6 ta thu ố
ượ ượ
ậ
t ng
ị ế ế đ c hoán v k ti p (3, 6, 4, 1, 2, 5). 58 S inh ho ¸n vÞ kÕ tiÕp ị ế ế (a1, a2, ..., an) (cid:0) (n, n1, ..., 1) *) procedure Next_Permutation;
(*Sinh hoán v k ti p
begin ấ ả j < aj+1 *) ở ấ ơ bên ph i a j ả j *) ượ c đo n t ỗ j v i aớ k *)
ổ
ạ ừ j+1 đ n aế
a
n *) ỉ ố ớ
(* Tìm j là ch s l n nh t tho a
j:=n1; while aj > aj+1 do j:=j1;
ớ
ỏ
ố
(* Tìm ak là s nh nh t còn l n h n a
k:=n; while aj > ak do k:=k1;
Swap(aj, ak); (* đ i ch a
ậ
(* L t ng
r:=n; s:=j+1; while r>s do begin Swap(ar, as); (* đ i ch a ỗ r v i aớ s *) ổ
r:=r1; s:= s+1; end;
end; 59 1. Giới thiệu bài toán 2. Thuật toán và độ phức tạp 4. Thuật toán quay lui 60 61 3.1. Sơ đồ thuật toán
3.2. Liệt kê các cấu hình tổ hợp cơ bản • Liệt kê xâu nhị phân độ dài n
• Liệt kê tập con m phần tử của tập n phần tử
• Liệt kê hoán vị
3.3. Bài toán xếp hậu 62 ể ả ơ ả ậ
ậ ộ
ề ượ ụ ế Thu t toán quay lui (Backtracking Algorithm) là m t
i quy t nhi u c áp d ng đ gi ề thu t toán c b n đ
ấ
v n đ khác nhau. Bài toán li ệ ữ ạ ậ t kê (Q): Cho A1, A2,..., An là các t p h u h n. Ký hi u ệ (cid:0) ...(cid:0) Ai , i=1, 2, ..., n}. X = A1 A2 (cid:0) An = { (x1, x2, ..., xn): xi (cid:0)
ề ặ
ấ ệ Gi s P là tính ch t cho trên X. V n đ đ t ra là li t kê t ấ ả
t c ả ầ ử ủ ấ
ấ :
c a X tho mãn tính ch t P ấ ả X: x tho mãn tính ch t P }. 63 Các ph n t
c. ượ ượ ọ ờ ả ấ ậ ả ử
các ph n t
D = { x = (x1, x2, ..., xn) (cid:0)
ầ ử ủ ậ D đ
c a t p c g i là các l i gi i ch p nh n đ TÊt c¶ c¸c bµi to¸n liÖt kª tæ hîp c¬ b¶n ®Òu cã thÓ Bµi to¸n liÖt kª x©u nhÞ ph©n ®é dµi n dÉn vÒ viÖc ph¸t biÓu díi d¹ng bµi to¸n (Q) liÖt kª c¸c phÇn tö cña tËp {0, 1}, i=1, 2, ..., n}. Bn = {(x1, ..., x n): xi (cid:0)
Bµi to¸n liÖt kª c¸c tËp con m phÇn tö cña tËp N = n = {(x1,..., x n) (cid:0) 64 {1, 2, ..., n} ®ßi hái liÖt kª c¸c phÇn tö cña tËp:
S (m ,n) = {(x1,..., x m)(cid:0) Nm: 1 ≤ x1 < ... < x m ≤ n }.
TËp c¸c ho¸n vÞ cña c¸c sè tù nhiªn 1, 2, ..., n lµ tËp
(cid:0) Nn: xi ≠ x j ; i ≠ j }. ả ộ ấ k ậ
i b ph n c p ộ ọ ờ
Định nghĩa. Ta g i l
(0≤k≤ n) là b có th t i gi
g m ứ ự ồ k thành ph n ầ Ai , i = 1, 2, ..., k. ờ (a1, a2, ..., ak),
trong đó ai (cid:0)
Khi k = 0, l c ký ệ ả ộ
ượ ọ i b ph n c p 0 đ
ả ỗ ờ i gi
hi u là () và còn đ ậ
c g i là l ượ
i r ng. ấ
i gi ờ ả ầ ủ ả ơ i đ y đ hay đ n gi n N u ế k = n, ta có l
ả ủ
ộ ờ i gi
i c a bài toán. là m t l i gi 65 ậ ượ ự ệ Thu t toán quay lui đ ự ầ ừ ự
c xây d ng d a trên vi c
i gi i. xây d ng d n t ng thành ph n c a l ậ Thu t toán b t đ u t i gi
c nh ng ph n t ứ ả i là ị
S1, b sung nó vào l
ả ộ
ượ ờ
c l ổ
i gi 66 ầ ủ ờ
ả
ơ ở
ắ ầ ừ ờ
ả ỗ
l
i r ng (). Trên c s
ủ
ầ ử
ượ
ị
tính ch t ấ P ta xác đ nh đ
ữ
nào c a
ả
ấ ủ ờ
ứ
ị
ọ
ể
t p ậ A1 có th ch n vào v trí th nh t c a l
i.
i gi
ẽ ọ
ầ ử
ử
ứ
ữ
ư ậ
ữ
Nh ng ph n t
nh v y ta s g i là nh ng ng c
ấ ủ ờ
ị
ế ắ
i
t là UCV) vào v trí th nh t c a l
t t
viên (vi
ệ ậ
ấ ủ
ứ
ả
i. Ký hi u t p các UCV vào v trí th nh t c a
gi
S1. L y ấ a1 (cid:0)
ả
ờ
ờ
i gi
i
l
i gi
ấ
ậ
ỗ
r ng đang có ta thu đ
i b ph n c p 1:
(a1). ờ T i b s ta đang có l i gi ả ộ
i b ph n c p ả ử
ạ ướ ổ
c t ng quát, gi
ậ ấ k1: (a1, a2, ..., ak1). ị Trên c s tính ch t P ượ
ị ầ
ữ
ấ ta xác đ nh đ
c nh ng ph n
ủ ờ
ứ k c a l
ể ọ
ủ ậ Ak có th ch n vào v trí th
i ơ ở
ử
nào c a t p
i. ả t
gi ư ậ Nh ng ph n t ẽ ọ
ị ầ ử
ế ắ
t t ử
nh v y ta s g i là nh ng ng c
ả
i
a1, ệ ậ ứ ứ
ữ
ủ ờ
ứ k c a l
t là UCV) vào v trí th
i gi
ọ
ượ
c ch n là (
Sk. ữ
viên (vi
ầ
ầ ủ
khi k1 thành ph n đ u c a nó đã đ
ử
a2, ..., ak1). Ký hi u t p các ng c viên này là 67 . Khi đó l yấ ak (cid:0) Sk, b ổ ờ Sk ≠ (cid:0)
ả ộ i b ph n c p ậ ấ k1 đang có Tình hu ng 1:
sung nó vào l i gi ả ộ ậ ấ k: i b ph n c p i gi (a1, a2, ..., ak1)
ượ ờ
ta thu đ
c l
(a1, a2, ..., ak1, ak).
Khi đó ộ ờ ả c m t l i, i gi
ự ầ ủ ờ • N u ế k = n thì ta thu đ
ượ
• N u ế k < n, ta ti p t c đi xây d ng thành ph n
ế ụ
ả
i. th ứ k+1 c a l i gi 68 Tình hu ng 2: ề ố ờ Sk=(cid:0) ình hu ng này ta quay tr l
ủ ờ ả ả ộ
i gi
i b
. Đi u đó có nghĩa là l
ph n (ậ a1, a2, ..., ak1) không th ti p t c phát tri n thành
ể
ể ế ụ
ở ạ ìm
ố
ả ầ ủ
ờ
i t
i đ y đ . Trong t
i gi
l
ị
ớ
ử
ứ
ng c viên m i vào v trí th ứ k1 c a l i gi i. ổ N u tế ìm th y UCV nh v y
ấ
ự
ồ ạ ế ụ
i ti p t c đi xây d ng thành ph n th ư ậ , thì b sung nó vào v trí th
ứ
ầ ị
ứ k. k1 r i l N u không t ượ ộ ở ạ ìm đ ì ta l ạ
i quay tr l
ị ế c n a t c th
ớ
ữ ìm UCV m i vào v trí th ượ ớ i thêm m t
ứ k2, ... N u quay
c UCV m i
ìm đ 69 i gi
ứ ế ậ ế
ướ
b
ả ỗ
ạ ậ ờ
i t n l
l
ị
vào v trí th 1, th ẫ
i r ng mà v n không t
ì thu t toán k t thúc. procedure Bactrack(k: integer);
begin k; ỗ ớ Sk do (* V i m i UCV y t ừ k *)
S ậ ờ ả i gi i (a Xây d ng Sự
for y (cid:0)
begin
ak := y;
if k = n then 1, a2, ..., ak) > else Backtrack(k+1);
end; end; 70 Lệnh gọi để thực hiện thuật toán quay lui là:
Bactrack(1) ả ầ ả ặ
ụ ể ậ
Đ cài đ t thu t toán quay lui gi
ế ấ i các bài toán
ề ơ
i quy t hai v n đ c ự ậ ậ Sk. ể ặ ả ệ ể
ổ ợ
t
h p c th ta c n gi
ả
b n sau:
• Tìm thu t toán xây d ng các t p UCV
• Tìm cách mô t
thao tác li
ặ
vòng l p qui t kê các ph n t
ướ for y (cid:0)
c ể
ậ
các t p này đ có th cài đ t
úng (cài đ t ặ
ầ ử ủ
c a ch
Sk do). ệ ộ Hi u qu c a thu t toán li ệ
ệ ị ượ ậ ụ
t kê ph thu c vào
c chính xác các t p UCV ậ
ả ủ
vi c ta có xác đ nh đ
này hay không. 71 ả N u ch c n t
ủ ụ ộ ờ
ỉ ầ ìm m t l
ọ ệ i th
ồ ở ệ
ả ầ ậ ượ ờ
c l i gi ì c n tầ ìm cách ch m ấ
ế
i gi
ứ
d t các th t c g i đ qui l ng nhau sinh b i l nh
ọ
g i Backtrack(1) sau khi ghi nh n đ
i đ u
tiên. ượ ộ N u k t thúc thu t toán mà ta không thu đ ậ
ề c m t
ì đi u đó có nghĩa là bài toán không có ế
ờ
i gi
ờ
i gi ế
ả
i nào th
ả
i. l
l 72 Thu t toán d dàng m r ng cho bài toán li ờ ễ i ả ả ư ậ
ể
i có th mô t ở ộ
nh là b ( ờ ệ
t kê trong đó l
ữ ạ
ộ a1, a2, ..., an,...) đ dài h u h n, tuy
ộ
ả
i cũng
i gi
c và các l gi
nhiên giá tr c a đ dài là không bi
ộ
không nh t thi ế ướ
t tr
t ph i có cùng đ dài.
i câu l nh 1, a2, ..., ak) > ậ ờ ả ị ủ ộ
ả
ế
ấ
ệ
ỉ ầ ử ạ
Khi đó ch c n s a l
if k = n then else Backtrack(k+1); thành 1, a2, ..., ak) > ậ ờ ả
i gi i> then ờ ả if <(a1, a2, ..., ak) là l
else Backtrack(k+1);
ậ
ự
C n xây d ng hàm nh n bi t ( i gi ế a1, a2, ..., ak) đã là l i hay
73 ầ
ch a. ư Gốc (lời giải rỗng) ậ T p UCV S1 x1 (x1) ậ T p UCV S2 khi đã có (x1) x2 (x1, x2) ậ S2 T p UCV
khi đã có (x1, x2) 74 LiÖt kª x©u nhÞ ph©n ®é dµi n 75 LiÖt kª x©u nhÞ ph©n ®é dµi n Bµi to¸n liÖt kª x©u nhÞ ph©n ®é dµi n dÉn vÒ viÖc liÖt kª {0, 1}, i=1, 2, ..., n}. c¸c phÇn tö cña tËp
Bn = {(x1, ..., x n): xi (cid:0)
Ta xÐt c¸ch gi¶i quyÕt hai vÊn ®Ò c¬ b¶n ®Ó cµi ®Æt • Đ cài đ t vòng l p li
ặ
ể ử ụ ễ ấ ể ặ c a thuËt to¸n quay lui:
•Râ rµng ta cã S 1 = {0, 1}. Gi¶ sö ®· cã x©u nhÞ ph©n
cÊp k1 (b1, ..., bk1), khi ®ã râ rµng S k = {0,1}. Nh vËy,
tËp c¸c UCV vµo c¸c vÞ trÝ cña lêi gi¶i ®îc ®· x¸c ®Þnh.
ầ ử ủ Sk, d th y là ta
t kê các ph n t có th s d ng vòng l p ệ
ặ for trên PASCAL: for y:= 0 to 1 do 76 ặ
ho c trên C: for (y=0;y<=1;y++) var procedure Xau(i: integer);
var j: integer;
begin n: integer;
b: array[1..20] of 0..1;
count: word; procedure Ghinhan;
var i: integer;
begin for j := 0 to 1 do
begin
b[i] := j;
if i = n then Ghinhan else Xau(i+1);
end; count := count+1; end; write(count:5, '. '); for i := 1 to n do write(b[i]:2); writeln;
end; BEGIN {Main program}
write('n = '); readln(n);
count := 0; Xau(1);
ể ế
write('Gõ Enter đ k t thúc... '); readln END. 77 include void Xau(int i){
int j;
for (j = 0; j<=1; j++) {
b[i] = j;
if (i==n) Ghinhan();
else Xau(i+1);
}
} void Ghinhan() {
int i, j;
count++;
printf(“Xau thu %i. ",count);
for (i=1 ; i<= n ;i++) { j=b[i];
printf("%i ", j); int main() {
printf(“n = ");
scanf("%i ",&n); printf("\n");
count = 0; Xau(1);
printf(“Count = %d ", count);
getch();
} }
printf("\n");
} 78 C©y liÖt kª d∙y nhÞ ph©n ®é dµi 3 79 Li t kê các mt p con c a 80 ậ t kê các t p con m ph n t ầ ử Bài toán: Li ệ
ủ ậ N = {1, 2, ..., n}.
c a t p ề ẫ ệ ầ ử ủ Bài toán d n v : Li t kê các ph n t c a t p: ậ S(m,n)={(x1,..., xm)(cid:0) Nm: 1 ≤ x1<... 81 Tõ ®iÒu kiÖn: 1 (cid:0) n a1 < a2 < ... < am (cid:0) suy ra S 1 = {1, 2, ..., n-(m -1) }.
Gi¶ sö ®· cã tËp con (a1, ..., ak1).
Tõ ®iÒu kiÖn ak-1 < ak < . . . < am ≤ n, ta suy ra
S k = {ak-1+1, ak-1+2, ..., n-(m k)}. t kê các ph n t ầ ử ủ Sk, d ễ
c a ặ ấ ệ
ặ
ặ
• Đ cể ài đ t vòng l p li
ể ử ụ
th y là ta có th s d ng vòng l p
ủ for y:= a[k1]+1 to nm+k do ... 82 c a PASCAL:
c a ủ C: for (y=a[k1]+1;y<=nm+k;y++) ... var n, m: integer; a: array[0..20] of byte;
count: word; procedure MSet(i: integer);
var j: integer;
begin
for j := a[i1] +1 to nm+i do
begin
a[i] := j; procedure Ghinhan;
var i: integer;
begin if i =m then Ghinhan else MSet(i+1); count := count+1; write(count:5, '. '); end;
end; for i := 1 to m do write(a[i]:4); BEGIN {Main program} writeln;
end; write('n, m = '); readln(n, m);
count := 0; MSet(1);
ể ế
write('Gõ Enter đ k t thúc... '); readln END. 83 #include j=a[i];
printf("%i ", j); void MSet(int i){
int j;
for (j = a[i1] +1; j<= nm+i; j++) {
a[i] = j;
if (i==m) Ghinhan();
else MSet(i+1);
}
}
int main() {
printf("n, m = ");
scanf("%i %i",&n, &m); printf("\n");
a[0]=0; count = 0; MSet(1);
printf(“Count = %d ", count);
getch();
} }
printf("\n");
} 84 85 86 TËp c¸c ho¸n vÞ cña c¸c sè tù nhiªn 1, 2, ..., n lµ tËp (cid:0) n = {(x1,..., x n) (cid:0) Nn: xi ≠ xj , i ≠ j }. Bài toán: Liệt kê tất cả các phần n 87 Râ rµng S 1 = N. Gi¶ sö ta ®ang cã ho¸n
vÞ bé phËn (a1, a2, ..., ak-1), tõ ®iÒu kiÖn
ai ≠ aj, víi mäi i ≠ j ta suy ra
S k = N \ { a1, a2, ..., ak-1}. Nh vËy ta ®· cã c¸ch x¸c ®Þnh ®îc tËp c¸c UCV vµo c¸c vÞ trÝ cña lêi gi¶i. Mô tả Sk? 88 Xây dựng hàm nhận biết UCV: (cid:0) ỉ ậ 89 function UCV(j,k: integer): boolean;
ị
(* UCV nh n giá tr true khi và ch khi j
Sk *)
var i: integer;
begin
for i:=1 to k-1 do
if j = a[i] then
begin
UCV:= false; exit;
end;
UCV:= true;
end; ướ for y (cid:0)
c “ Sk do ” có th ể ư ệ
Câu l nh qui
ặ cài đ t nh sau
for y:=1 to n do
if UCV(y,k) then
begin (* y là UCV vào v trí k *)
. . . end 90 91 92 #include int UCV(int j, int k)
{
int i;
for (i=1; i<=k1; i++)
if (j == b[i]) return 0;
return 1;
} int Ghinhan() {
int i, j;
count++;
printf("Hoan vi thu %i. ",count);
for (i=1 ; i<= n ;i++) {
printf("%i ", b[i]); }
printf("\n");
} 93 94 int Hoanvi(int i){
int j;
for (j = 1; j<=n; j++)
if (UCV(j,i)==1)
{ b[i] = j;
if (i==n) Ghinhan();
else Hoanvi(i+1);
}
} int main() {
printf(“=========\n");
printf("n = ");
scanf("%i",&n);
printf("\n");
count = 0; Hoanvi(1);
printf("Count = %d ", count);
getch();
} 95 96 Giả sử ta có 8 con hậu...
...và bàn cờ quốc tế 97 98 Hai con hậu bất kỳ
không được xếp trên
cùng một dòng ... 99 Hai con hậu bất kỳ
không được xếp trên
cùng một cột ... 100 Hai con hậu bất kỳ
không được xếp trên
cùng một đường chéo! 101 n con hậu Kích thước n*n n cột n dòng 102 Xét bài toán xếp n con
hậu lên bàn cờ kích
thước n x n. 103 Li ệ ấ ả t kê t t c các cách x p ằ ộ 104 ờ n(cid:0) n
ậ
ế n quân H u trên bàn c
ượ ẫ
c l n nhau, nghĩa là sao cho
sao cho chúng không ăn đ
ố
không có hai con nào trong s chúng n m trên cùng m t
ộ ườ
ộ ộ
dòng hay m t c t hay m t đ ờ
ủ
ng chéo c a bàn c . ộ ố ờ ừ ộ ế ễ ủ
ể ể Đánh s các c t và dòng c a bàn c t
ậ ế n.
n i. dòng ề Các đi u ki n đ t ra đ i v i b ố ớ ộ (a1, a2 ,..., an):
j (nghĩa là hai con h u • ai (cid:0) j (nghĩa là hai c ượ (ai, i) và (aj, j) không đ 105 ng chéo). Như vậy bài toán xếp Hậu dẫn về bài toán liệt kê các phần tử của tập: D={(a1, a2, ..., an)(cid:0) Nn: ai ≠ aj và |ai – aj| ≠ |i – j|, i ≠ j }. 106 107 108 109 Toán rời rạc - NĐN 110 110 ả ậ
ạ ầ ế
Rõ ràng là bài toán x p h u không ph i là
ẳ
i, ch ng h n bài toán không
n=2, 3. Do đó đi u này c n ề
ậ ả
ờ
i gi
luôn có l
ả
ờ
i khi
i gi
có l
ế
ượ
c thông báo khi k t thúc thu t toán.
đ ở ậ ư Thu t toán tr ình bày ệ
ị
ị ả trên là ch a hi u
ả
qu . Nguyên nhân là ta đã không xác đ nh
ậ
ượ
c chính xác các t p UCV vào các v trí
đ
ủ ờ
c a l i gi i. 111 112 ROW 1, COL 1 113 Xếp con hậu ở dòng 1
vào vị trí cột 1 ROW 1, COL 1 đã đặt 114 1 Thử xếp con hậu ở dòng 2 vào vị trí cột 1 ROW 2, COL 1 ROW 1, COL 1 đã đặt 115 1 Thử xếp con hậu ở dòng 2 vào vị trí cột 2 ROW 2, COL
2 ROW 1, COL 1 đã đặt 116 1 Thử xếp con hậu ở dòng 2 vào vị trí cột 3 ROW 2, COL 3 ROW 1, COL 1 đã đặt 117 1 Chấp nhận xếp con hậu ở
dòng 2 vào vị
trí cột 3 ROW 2, COL 3 ROW 1, COL 1 đã đặt 118 2 Thử xếp con hậu ở
dòng 3
vào cột đầu tiên ROW 3, COL 1 ROW 2, COL 3 ROW 1, COL 1 đã đặt 119 2 Thử cột tiếp theo ROW 3, COL 2 ROW 2, COL 3 ROW 1, COL 1 đã đặt 120 2 Thử cột tiếp theo ROW 3, COL 3 ROW 2, COL 3 ROW 1, COL 1 đã đặt 121 2 Thử cột tiếp theo ROW 3, COL 4 ROW 2, COL 3 ROW 1, COL 1 đã đặt 122 2 ROW 3, COL 4 ROW 2, COL 3 ROW 1, COL 1 đã đặt 123 2 Quay lại dịch chuyển con hậu
ở dòng 2 ROW 2, COL 3 ROW 1, COL 1 đã đặt 124 1 Đẩy con hậu ở
dòng 2 sang
cột thứ 4. ROW 2, COL 4 ROW 1, COL 1 đã đặt 125 1 Xếp được con
hậu ở dòng 2
ta tiếp tục xếp
con hậu ở
dòng 3 ROW 2, COL 4 ROW 1, COL 1 đã đặt 126 2 Thử xếp con
hậu ở dòng 3
vào cột 1 ROW 2, COL 4 ROW 1, COL 1 đã đặt 127 2 Thử xếp con
hậu ở dòng 3
vào cột 2 ROW 2, COL 4 ROW 1, COL 1 đã đặt 128 2 ROW 2, COL 4 Xếp được con
hậu ở dòng 3
ta tiếp tục xếp
con hậu ở
dòng 4: Thử
cột 1 ROW 1, COL 1 đã đặt 129 2 Thử xếp được
con hậu ở
dòng 4 vào cột
2 ROW 2, COL 4 ROW 1, COL 1 đã đặt 130 2 Thử xếp được
con hậu ở
dòng 4 vào cột
3 ROW 2, COL 4 ROW 1, COL 1 đã đặt 131 2 Thử xếp được
con hậu ở
dòng 4 vào cột
4 ROW 2, COL 4 ROW 1, COL 1 đã đặt 132 2 Không xếp
được con hậu
ở dòng 4 ROW 2, COL 4 ROW 1, COL 1 đã đặt 133 2 Quay lại tìm vị
trí mới cho con
hậu ở dòng 3:
Thử cột 3 ROW 2, COL 4 ROW 1, COL 1 đã đặt 134 2 Quay lại tìm vị
trí mới cho con
hậu ở dòng 3:
Thử cột 4 ROW 2, COL 4 ROW 1, COL 1 đã đặt 135 2 Không có cách
xếp mới cho
con hậu ở
dòng 3 ROW 2, COL 4 ROW 1, COL 1 đã đặt 136 2 Quay lại tìm
cách xếp mới
cho con hậu ở
dòng 2: Không
có ROW 2, COL 4 ROW 1, COL 1 đã đặt 137 2 ROW 2, COL 4 Quay lại tìm
cách xếp mới
cho con hậu ở
dòng 1:
Chuyển sang
cột 2 ROW 1, COL 1 đã đặt 138 2 Mé t lê i g i¶i c ña bµi to ¸n xÕp
hËu khi n = 8 139 The End Toán rời rạc - NĐN 140 140 141 141 142 Toán rời rạcGiải thích
3. PHƯƠNG PHÁP SINH
ậ
ấ
ổ ợ ơ ả
• Sinh xâu nh phân đ dài
ộ
ị
n
• Sinh t p con
ậ
m ph n t
• Sinh hoán v c a
ộ
ị
Sinh các dãy nhị phân độ dài n
Ví dụ
Thuật toán sinh kế tiếp
Ví dụ
1
1101100000
Thuật toán sinh xâu kế tiếp
ậ
ầ ử
Sinh các t p con
ủ ậ n ph n t
c a t p
m ph n t
ầ ử
Sinh các tập con m phần tử của tập n phần tử
Thứ tự từ điển
Ví dụ
Thuật toán sinh kế tiếp
Ví dụ
ụ
Ví d : n =
ầ
ả ử
ậ
s đang có t p con (1, 2, 5, 6), c n xây
Gi
ứ ự ừ
ế ế
ự
d ng t p con k ti p nó trong th t
đi n. ể
Ta có i=2:
Sinh m-tập kế tiếp
Sinh các hoán v ị
ầ ử
ủ ậ n ph n t
c a t p
Sinh các hoán vị của tập n phần tử
Thứ tự từ điển
Ví dụ
Thuật toán sinh kế tiếp
Chương 3. Bài toán liệt kê
3. Phương pháp sinh
Chương 3. Bài toán liệt kê
3. THUẬT TOÁN QUAY LUI
Backtracking Algorithm
NỘI DUNG
SƠ ĐỒ THUẬT TOÁN
Ví dụ
Lời giải bộ phận
Ý tưởng chung
Bước tổng quát
Xét hai tình huống
ố
Tình huống ngõ cụt
Thuật toán quay lui
Hai vấn đề mấu chốt
Chú ý
Chú ý
Cây liệt kê lời giải
theo thuật toán quay lui
Chương trình trên Pascal
Chương trình trên C
ệ
ậ
ủ nt pậ
Liệt kê các m-tập con của n-tập
Giải quyết 2 vấn đề mấu chốt
Chương trình trên Pascal
Chương trình trên C
Cây liệt kê S(5,3)
ệ
Li
ị
t kê hoán v
Liệt kê hoán vị
tử của (cid:0)
Giải quyết 2 vấn đề mấu chốt
Mô tả Sk
Mô tả Sk
ị
Chương trình trên Pascal
var
n, count: integer;
a: array[1..20] of integer;
procedure Ghinhan;
var i: integer;
begin
count := count+1; write(count:5, '. ');
for i := 1 to n do write(a[i]:3); writeln;
end;
function UCV(j,k: integer): boolean;
var i: integer;
begin
for i:=1 to k-1 do
if j = a[i] then begin
UCV:= false; exit;
end;
UCV:= true;
end;
procedure Hoanvi(i: integer);
var j: integer;
begin
for j := 1 to n do
if UCV(j, i) then
begin
a[i] := j;
if i = n then Ghinhan else Hoanvi(i+1);
end;
end;
BEGIN {Main program}
write('n = '); readln(n);
count := 0;
Hoanvi(1);
write(‘Press Enter to finish... '); readln;
END.
Cây liệt kê hoán vị của 1, 2, 3
The nQueens Problem
The n-Queens Problem
The n-Queens Problem
Có thể xếp các con
hậu sao cho không
có hai con nào ăn
nhau hay không ??
The n-Queens Problem
The n-Queens Problem
The n-Queens Problem
The n-Queens Problem
The n-Queens Problem
Bài toán xếp hậu
Biểu diễn lời giải
ượ ằ
ậ ở
ộ
c n m trên cùng m t
ớ ọ i (cid:0)
| i – j |, v i m i
hai ô
ộ ườ
ằ
1 đ n
ở ộ
M t cách x p h u có th bi u di n b i b có
thành ph n (ầ a1, a2 ,..., an), trong đó ai là to đ
ạ ộ
ậ ở
ộ ủ
c t c a con H u
ặ
ệ
ớ ọ i (cid:0)
aj , v i m i
hai dòng i và j không đ
c t);ộ
• | ai – aj | (cid:0)
ậ ở
con h u
n m trên cùng m t đ
Phát biểu bài toán
Hàm nhận biết ứng cử viên
int UCVh(int j, int k) {
// UCVh nhận giá trị 1
// khi và chỉ khi j (cid:0) Sk
int i;
for (i=1; i
if ((j == a[i])||(fabs(j-a[i])== k-i)) return 0;
return 1;
}
Chương trình trên C
#include
int UCVh(int j, int k) {
/* UCVh nhận giá trị 1 khi và chỉ khi j (cid:0) Sk */
int i;
for (i=1; i
int Hau(int i){ int j;
for (j=1; j<=n; j++)
if (UCVh(j, i)){
a[i] = j;
if (i == n) Ghinhan();
else Hau(i+1);
}
}
int main() {
printf("Input n = "); scanf("%i",&n);
printf("\n==== RESULT ====\n");
count = 0; Hau(1);
if (count == 0) printf("No solution!\n");
getch();
printf("\n Press Enter to finish... ");
getchar();
}
Chú ý
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
...không có vị
trí đặt con hậu
ở dòng 3.
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Thuật toán làm việc như thế nào
Questions?
