Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Chương 3: Bài toán liệt kê tổ hợp - Nguyễn Đức Nghĩa

Toán rời rạc 
Phần thứ nhất 
LÝ THUYẾT TỔ HỢP 
Combinatorial Theory 
Fall 2009 
Toán rời rạc 
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 
Chương 3 
BÀI TOÁN LIỆT KÊ 
Toán rời rạc 
Toán rời rạc 
NỘI DUNG 
Giới thiệu bài toán 
Thuật toán và độ phức tạp 
Phương pháp sinh 
Thuật toán quay lui 
Giíi thiÖu bµi to¸n 
Bài toán đưa ra danh sách tất cả cấu h ì nh tổ hợp thoả mãn một số tính chất cho trước được gọi là bài toán liệt kê tổ hợp. 
Do số lượng cấu hình tổ hợp cần liệt kê thường là rất lớn ngay cả khi kích thước cấu hình chưa lớn: 
Số hoán vị của n phần tử là n! 
Số tập con m phần tử của n phần tử là n!/(m!(n-m)! 
Do đó ần có quan niệm thế nào là giải bài toán liệt kê tổ hợp 
Giíi thiÖu bµi to¸n 
Bài toán liệt kê tổ hợp là giải được nếu như ta có thể x ác định một thuật toán để theo đó có thể lần lượt xây dựng được tất cả các cấu h ì nh cần quan tâm. 
Một thuật to á n liệt kê phải đảm bảo 2 yêu cầu cơ bản: 
K hông được lặp lại một cấu h ì nh, 
không được bỏ sót một cấu h ì nh. 
Toán rời rạc 
Chương 3. Bài toán liệt kê 
Giới thiệu bài toán 
Thuật toán và độ phức tạp 
Phương pháp sinh 
Thuật toán quay lui 
Khái niệm bài toán tính toán 
Định nghĩa. Bài toán tính toán F là ánh xạ từ 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: 
 F : {0, 1} * {0, 1} *. 
Ví dụ: 
Mỗi số nguyên x đều có thể biểu diễn dưới dạng xâu nhị phân là cách viết trong hệ đếm nhị phân của nó. 
Hệ phương trình tuyến tính Ax = b có thể biểu diễn dướ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ơ b . 
Đa thức một biến: 
 P ( x ) = a 0 + a 1 x + ... + a n x n , 
 hoàn toàn xác định bởi dãy số n, a 0 , a 1 , ..., a n , mà để biểu diễn dãy số này chúng ta có thể sử dụng xâu nhị phân. 
Khái niệm thuật toán 
Định nghĩa. Ta hiểu thuật toán giả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 bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của bài toán. 
Thuật toán có các đặc trưng sau đây: 
Đầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nào đó. 
Đầu ra (Output): Với mỗi tập các dữ liệu đầu vào, thuật toán đưa ra các dữ liệu tương ứng với lời giải của bài toán. 
Chính xác (Precision): Các bước của thuật toán được mô tả chính xác. 
Khái niệm thuật toán 
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) bước với mọi đầu vào. 
Đơn trị (Uniqueness): Các kết quả trung gian của từng bước thực hiện thuật toán đượ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ước trước. 
Tổng quát (Generality): Thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho. 
Độ 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 cần thiết để thực hiện thuật toán mà ta sẽ gọi là thời gian tính 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ố! 
Định nghĩa. Ta gọi kích thước dữ liệu đầu vào ( hay độ dài dữ liệu vào ) là số bít cần thiết để biểu diễn nó. 
Ví dụ: Nếu x, y là đầu vào cho bài toán nhân 2 số nguyên, thì kích thước dữ liệu vào của bài toán là n = log | x | + log | y | . 
Ta sẽ tìm cách đánh giá thời gian tính của thuật toán bởi một 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? 
Định nghĩa. Ta gọi phép toán cơ bản là phép toán có thể thực hiện với thời gian bị chặn bởi một hằng số không phụ thuộc vào kích thước dữ liệu. 
Để tính toán thời gian tính của thuật toán ta sẽ đếm số phép toán cơ bản mà nó phải thực hiện. 
Các loại thời gian tính 
Chúng ta sẽ quan tâm đến : 
Thời gian tối thiểu cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n . Thời gian như vậy sẽ được gọi là thời gian tính tốt nhất của thuật toán với đầu vào kích thước n . 
Thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào kích thước n . Thời gian như vậy sẽ được gọi là thời gian tính tồi nhất của thuật toán với đầu vào kích thước n . 
Thời gian trung bình cần thiết để thực hiện thuật toán trên tập hữu hạn các đầu vào kích thước n . Thời gian như vậy sẽ được gọi là thời gian tính trung bình của thuật toán. 
Ký hiệu tiệm cận Asymptotic Notation 
 Q , O , W 
Đượ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à, chẳng hạn , Q ( n 2 ) 
Ký hiệu  
  ( g ( n )) = { f ( n ) | tồn tại các hằng số c 1 , c 2 và n 0 sao cho 
 0 c 1 g ( n ) f ( n ) c 2 g ( n ) , với mọi n n 0 } 
 Đối với hàm g ( n ) cho trước , ta ký hiệu  ( g ( n )) là tập các hàm 
Ta nói rằng g ( n ) là đánh giá tiệm cận đúng cho f ( n ) 
Ví dụ 
10 n 2 - 3 n = Q ( n 2 ) 
Với giá trị nào của các hằng số n 0 , c 1 , và c 2 thì bất đẳng thức sau đây là đúng với n ≥ n 0 : 
 c 1 n 2 ≤ 10 n 2 - 3 n ≤ c 2 n 2 
Ta có thể lấy c 1 bé hơn hệ số của số hạng với số mũ cao nhất, còn c 2 lấy lớn hơn hệ số này, chẳng hạn: 
 c 1 =9 < 10 < c 2 = 11, n 0 = 10. 
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 
 Đối với hàm g ( n ) cho trước, ta ký hiệu O ( g ( n )) là tập các hàm 
 O ( g ( n )) = { f ( n ) | tồn tại các hằng số dương c và n 0 sao cho: 
 f ( n ) cg ( n ) với mọi n n 0 } 
Ta nói g ( n ) là cận trên tiệm cận của f ( n ) 
Ví dụ: Ký hiệu O lớn 
Chứng minh: f ( n ) = n 2 + 2 n + 1 là O ( n 2 ) 
Cần chỉ ra: n 2 + 2 n + 1 ≤ c * n 2 
 với c là hằng số nào đó và khi n > n 0 nào đó 
Ta có: 
 2 n 2 ≥ 2 n khi n ≥ 1 
 và n 2 ≥ 1 khi n ≥ 1 
Vì vậy 
 n 2 + 2 n + 1 ≤ 4* n 2 với mọi n ≥ 1 
Như vậy hằng số c = 4, và n 0 =1 
Ví dụ: Ký hiệu O lớn 
Rõ ràng: Nếu f ( n ) là O ( n 2 ) thì nó cũng là O ( n k ) với k > 2. 
Chứng minh: f ( n ) = n 2 + 2 n + 1 O ( n ). 
Phản chứng. Giả sử trái lại, khi đó phải tìm được hằng số c và số n 0 để cho: 
 n 2 + 2 n + 1 ≤ c * n khi n ≥ n 0 
Suy ra 
 n 2 < n 2 + 2 n + 1 ≤ c * n với mọi n ≥ n 0 
Từ đó ta thu được: 
 n < c với mọi n ≥ n 0 ?! 
Ký hiệu  
 Đối với hàm g ( n ) cho trước, ta ký hiệu  ( g ( n )) là tập các hàm: 
  ( g ( n )) = { f ( n )| tồn tại các hằng số dương c và n 0 sao cho 
	 cg ( n ) f ( n ) 
	với mọi n n 0 } 
Ta nói g ( n ) là cận dưới tiệm cận cho f ( n ) 
Ví dụ: Ký hiệu  
Chứng minh: f ( n ) = n 2 - 2000 n là  ( n 2 ) 
Cần chỉ ra: n 2 - 2000 n c * n 2 
 với c là hằng số nào đó và khi n > n 0 nào đó 
Ta có: 
 n 2 - 2000 n 0.5* n 2 với mọi n ≥ 10000 
(vì n 2 - 2000 n - 0.5* n 2 = 0.5* n 2 - 2000 n 
 = n (0.5* n - 2000) 0 
khi n ≥ 10000) 
Như vậy hằng số c = 1, và n 0 =1 
Ví dụ: Ký hiệu  
Rõ ràng: Nếu f ( n ) là  ( n 2 ) thì nó cũng là  ( n k ) với k < 2. 
Chứng minh: f ( n ) = n 2 - 2000 n  ( n 3 ). 
Phản chứng. Giả sử trái lại, khi đó phải tìm được hằng số c và số n 0 để cho: 
 n 2 – 2000 n c * n 3 khi n ≥ n 0 
Suy ra 
 n 2 n 2 – 2000 n c * n 3 khi n ≥ n 0 
Từ đó ta thu được: 
 	 1 /c n với mọi n ≥ n 0 ?! 
Liên hệ giữa Q , W , O 
Đối với hai hàm bất kỳ g ( n ) và f ( n ),  f ( n ) =  ( g ( n )) 
 khi và chỉ khi 
 f ( n ) = O ( g ( n )) và f ( n ) =  ( g ( n )). 
 tức là 
  ( g ( n )) = O ( g ( n )) Ç W ( g ( n )) 
Chú ý 
Giá trị của n 0 và c không phải là duy nhất trong chứng minh công thức tiệm cận. 
Chứng minh rằng 100 n + 5 = O ( n 2 ) 
100 n + 5 ≤ 100 n + n = 101 n ≤ 101 n 2 	với mọi n ≥ 5 
	 n 0 = 5 và c = 101 là các hằng số cần tìm 
100 n + 5 ≤ 100 n + 5 n = 105 n ≤ 105 n 2 với mọi n ≥ 1 
	 n 0 = 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à n 0 nào đó thoả mãn bất đẳng thức 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ụ, 
4 n 3 + 3 n 2 + 2 n + 1 = 4 n 3 + 3 n 2 +  ( n ) 
= 4 n 3 +  ( n 2 ) =  ( n 3 ) 
Trong các đẳng thức ,  ( f ( n )) thay thế cho một hàm nào đó g ( n ) Î  ( f ( n )) 
Trong ví dụ trên ,  ( n 2 ) thay thế cho 3 n 2 + 2 n + 1 
So sánh các hàm số 
 f  g a  b 
f ( n ) = O ( g ( n )) a b 
f ( n ) =  ( g ( n )) a b 
f ( n ) =  ( g ( n )) a = b 
f ( n ) = o ( g ( n )) a < b 
f ( n ) = w ( g ( n )) a > b 
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 huống tồi nhất (worst case) là O ( f ( n )). Thường nói: “Đánh giá thời gian tính trong tình huống tồi nhất là O ( f ( n ))” 
Nghĩa là thời gian tính trong tình huống tồi nhất được xác định bởi một hàm nào đó g ( n ) Î O ( f ( n )) 
“Thời gian tính là W ( f ( n )) ” hiểu là: Đánh giá trong tình huống tốt nhất (best case) là W ( f ( n )). Thường nói: “Đánh giá thời gian tính trong tình huống tốt nhất là W ( f ( n )) ” 
Nghĩa là thời gian tính trong tình huống tốt nhất được xác định bởi một hàm nào đó g ( n ) Î W ( f ( n )) 
Đồ thị của một số hàm cơ bản 
Tên gọi của một số tốc độ tăng 
Hàm 
Tên gọi 
log n 
log 
n 
tuyến tính 
n log n 
n log n 
n 2 
bình phương 
n 3 
bậc 3 
2 n 
hàm mũ 
n k ( k là hằng số dương) 
đa thức 
Toán rời rạc 
Ví dụ phân tích thuật toán 
Ví dụ. Xét thuật toán tìm kiếm tuần tự để giải bài toán 
Đầu vào: n và dãy số s 1 , s 2 , . . . , s n . 
Đầu ra: Vị trí phần tử có giá trị key hoặc là n +1 nếu không tìm thấy. 
	 function Linear_Search(s,n,key); 
	 begin 
	i:=0; 
	 repeat 
	i:=i+1; 
	 until (i>n) or (key = s i ); 
	Linear_Search := i; 
	 end; 
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 thuật toán với độ dài đầu vào là n. Rõ ràng thời gian tính của 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 s 1 = 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à  (1). 
Nếu key không có mặt trong dãy đã cho, thì câu lệnh i := i+ 1 thực hiện n lần. Vì thế thời gian tính tồi nhất của thuật toán là O ( n ). 
Toán rời rạc 
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. 
Nếu key tìm thấy ở vị trí thứ i của dãy ( key = s i ) thì câu lệnh i := i +1 phải thực hiện i lần ( i = 1, 2, ..., n ), 
Nếu key không có mặt trong dãy đã cho thì câu lệnh i := i +1 phải thực hiện n lần. 
Từ đó suy ra số lần trung bình phải thực hiện câu lệnh i := i +1 là 
	 [(1 + 2 + . . . + n ) + n ] /( n +1) = [ n ( n +1)/2 + n ]/( n +1). 
Ta có 
 n /4 [ n ( n +1)/2 + n ]/( n +1) n . với mọi n 1. 
Vậy thời gian tính trung bình của thuật toán là  ( n ). 
Toán rời rạc 
Chương 3. Bài toán liệt kê 
Giới thiệu bài toán 
Thuật toán và độ phức tạp 
Phương pháp sinh 
Thuật toán quay lui 
3. PHƯƠNG PHÁP SINH 
3.1. Sơ đồ thuật toán 
3.2. Sinh các cấu hình tổ hợp cơ bản 
Sinh xâu nhị phân độ dài n 
Sinh tập con m phần tử của tập n phần tử 
Sinh hoán vị của n phần tử 
SƠ ĐỒ THUẬT TOÁN 
Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp đặt ra nếu như hai điều kiện sau được thực hiện: 
1) Có thể xác định được một thứ tự trên tập các cấu h ì nh tổ hợp cần liệt kê. Từ đó có thể xác định được cấu h ì nh đầu tiên và cấu h ì nh cuối cùng trong thứ tự đã xác định. 
2) Xây dựng được thuật toán từ cấu h ì nh chưa phải là cuối cùng đang có, đưa ra cấu h ì nh kế tiếp nó. 
Thuật toán nói đến trong điều kiện 2) được gọi là Thuật toán Sinh kế tiếp 
Thuật toán sinh 
procedure Generate; 
Begin 
	; 
	Stop:= false ; 
	 while not stop do 
	 begin 
	; 
	 if ( cấu hình đang có chưa là cuối cùng ) 
 then <Sinh_kế_tiếp 
 else Stop:= true ; 
	end; 
 End. 
Giải thích 
Sinh_kế_tiếp là thủ tục thực hiện thuật toán sinh kế tiếp đã xây dựng trong điều kiện 2) . T hủ tục này sẽ xây dựng cấu h ì nh kế tiếp của cấu h ì nh đang có trong thứ tự đã xác định. 
Chú ý: Do tập các cấu hình tổ hợp cần liệt kê là hữu hạn nên luôn có thể xác định được thứ tự trên nó. Tuy nhiên, thứ tự cần xác định sao cho có thể xây dựng được thuật toán Sinh kế tiếp. 
3. PHƯƠNG PHÁP SINH 
3.1. Sơ đồ thuật toán 
3.2. Sinh các cấu hình tổ hợp cơ bản 
Sinh xâu nhị phân độ dài n 
Sinh tập con m phần tử của tập n phần tử 
Sinh hoán vị của n phần tử 
Sinh các dãy nhị phân độ dài n 
41 
Sinh các dãy nhị phân độ dài n 
Bài toán: Liệt kê tất cả các dãy nhị phân độ dài n : b 1 b 2 ... b n , trong đó b i {0, 1}. 
Thứ tự tự nhiên: 
Xem mỗi dãy nhị phân b = b 1 b 2 ... b n là biểu diễn nhị phân của một số nguyên p ( b ) 
Ta nói dãy nhị phân b = b 1 b 2 ... b n đi trước dãy nhị phân b' = b' 1 b' 2 ... b' n trong thứ tự tự nhiên và ký hiệu là b b' nếu p ( b ) < p ( b' ). 
Ví dụ 
Ví dụ: Khi n =3, các dãy nhị phân độ dài 3 được liệt kê theo thứ tự tự nhiên trong bảng bờn 
Dễ thấy thứ tự này trùng với thứ tự từ điển 
b 
p ( b ) 
000 
0 
001 
1 
010 
2 
011 
3 
100 
4 
101 
5 
110 
6 
111 
7 
Thuật toán sinh kế tiếp 
Dãy đầu tiên sẽ là 0 0 ... 0, 
Dãy cuối cùng là 1 1 ... 1. 
Giả sử b 1 b 2 ... b n 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 được bằng cách cộng thêm 1 (theo modun 2, có nhớ) vào dãy hiện tại. 
Từ đó ta c ó qui tắc sinh dãy kế tiếp như sau: 
T ì m i đầu tiên (theo thứ tự i=n, n -1 , ..., 1) thoả mãn b i = 0 . 
Gán lại b i = 1 và b j = 0 với tất cả j > i. Dãy mới thu được sẽ là dãy cần t ì m. 
Ví dụ 
Xét dãy nhị phân độ dài 10: b = 1101011111. 
 Ta có i = 5 . 
Do đó, đặt b 5 = 1, và b i = 0 , i = 6, 7, 8, 9, 10, ta thu đươc xâu nhị phân kế tiếp là 1101100000. 
 1101011111 
	 1	 
 1101100000 
Thuật toán sinh xâu kế tiếp 
procedure Next_Bit_String; 
(* Sinh xâu nhị phân kế tiếp theo thứ tự từ điển của 
	 xâu đang có b 1 b 2 ... b n 1 1 ... 1 	 *) 
begin 
	i:=n; 
 	 while b i = 1 do 
	 begin 
 	b i = 0; 
 	i := i- 1 ; 
 	 end; 
 	b i := 1 ; 
end; 
Sinh các tập con m phần tử của tập n phần tử 
Sinh các tập con m phần tử của tập n phần tử 
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 = ( a 1 , a 2 , ... , a m ) 
 tho¶ m·n 
 	 1 a 1 < a 2 < ... < a m n. 
Thứ tự từ điển 
Ta nãi tËp con a = ( a 1 , a 2 ,..., a m ) ®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 k m ) sao cho 
 a 1 = a' 1 , a 2 = a' 2 , . . . , a k -1 = a' k -1 , 
 a k < a' k . 
Ví dụ 
Các tập con 3 phần tử của X = {1, 2, 3, 4, ... i giải rỗng đang có ta thu được lời giải bộ phận cấp 1: ( a 1 ). 
Bước tổng quát 
Tại bước tổng quát, giả sử ta đang có lời giải bộ phận cấp k -1: ( a 1 , a 2 , ..., a k -1 ). 
Trên cơ sở tính chất P ta xác định được những phần tử nào của tập A k có thể chọn vào vị trí thứ k của lời giải. 
Những phần tử như vậy ta sẽ gọi là những ứng cử viên (viết tắt là UCV) vào vị trí thứ k của lời giải khi k -1 thành phần đầu của nó đã được chọn là ( a 1 , a 2 , ..., a k -1 ). Ký hiệu tập các ứng cử viên này là S k . 
Xét hai tình huống 
Tình huống 1: S k ≠  . Khi đó lấy a k S k , bổ sung nó vào lời giải bộ phận cấp k -1 đang có 
 ( a 1 , a 2 , ..., a k -1 ) 
 ta thu được lời giải bộ phận cấp k: 
 ( a 1 , a 2 , ..., a k -1 , a k ) . 
Khi đó 
Nếu k = n th ì ta thu được một lời giải, 
Nếu k < n , ta tiếp tục đi xây dựng thành phần thứ k+ 1 của lời giải. 
Tình huống ngõ cụt 
Tình huống 2: S k = . Điều đó có nghĩa là lời giải bộ phận ( a 1 , a 2 , ..., a k - 1 ) không thể tiếp tục phát triển thành lời giải đầy đủ. Trong t ì nh huống này ta quay trở lại t ì m ứng cử viên mới vào vị trí thứ k -1 của lời giải. 
Nếu t ì m thấy UCV như vậy , th ì bổ sung nó vào vị trí thứ k -1 rồi lại tiếp tục đi xây dựng thành phần thứ k . 
Nếu không t ì m được th ì ta lại quay trở lại thêm một bước nữa t ì m UCV mới vào vị trí thứ k -2, ... Nếu quay lại tận lời giải rỗng mà vẫn không t ì m được UCV mới vào vị trí thứ 1, th ì thuật toán kết thúc. 
Thuật toán quay lui 
	 procedure Bactrack(k: integer ); 
	begin 
 Xây dựng S k ; 
	for y S k do (* Với mỗi UCV y từ S k *) 
	begin 
	 	 a k := y; 
	 if k = n then 
	 else Backtrack(k+1); 
	end; 
	end; 
 Lệnh gọi để thực hiện thuật toán quay lui là: Bactrack(1) 
Hai vấn đề mấu chốt 
Để cài đặt thuật toán quay lui giải các bài toán tổ hợp cụ thể ta cần giải quyết hai vấn đề cơ bản sau: 
Tìm thuật toán xây dựng các tập UCV S k . 
T ì m cách mô tả các tập này để có thể cài đặt thao tác liệt kê các phần tử của ch ú ng (cài đặt vòng lặp qui ước for y S k do). 
Hiệu quả của thuật toán liệt kê phụ thuộc vào việc ta có xác định được chính xác các tập UCV này hay không. 
Chú ý 
N ếu chỉ cần t ì m một lời giải th ì cần t ì m cách chấm 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 được lời giải đầu tiên. 
Nếu kết thúc thuật toán mà ta không thu được một lời giải nào th ì điều đó có nghĩa là bài toán không có lời giải. 
Chú ý 
Thuật toán dễ dàng mở rộng cho bài toán liệt kê trong đó lời giải có thể mô tả như là bộ ( a 1 , a 2 , ..., a n ,... ) độ dài hữu hạn, tuy nhiên giá trị của độ dài là không biết trước và các lời giải cũng không nhất thiết phải có cùng độ dài. 
 Khi đó chỉ cần sửa lại câu lệnh 
 if k = n then 
	 else Backtrack(k+1); 
 thành 
	 if then 
	 else Backtrack(k+1) ; 
C ần xây dựng hàm nhận biết ( a 1 , a 2 , ..., a k ) đã là lời giải hay chưa. 
Cây liệt kê lời giải theo thuật toán quay lui 
Gốc (lời giải rỗng) 
x 1 
( x 1 ) 
x 2 
( x 1 , x 2 ) 
Tập UCV S 1 
Tập UCV S 2 khi đã có ( x 1 ) 
Tập UCV S 2 
 khi đã có ( x 1 , x 2 ) 
LiÖt kª x©u nhÞ ph©n ®é dµi n 
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ª c¸c phÇn tö cña tËp 
 B n = {( x 1 , ..., x n ): x i {0, 1} , i =1, 2, ..., n }. 
Ta xÐt c¸ch gi¶i quyÕt hai vÊn ®Ò c¬ b¶n ®Ó cµi ®Æt 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 k- 1 ( b 1 , ..., b k- 1 ), 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. 
Đ ể cài đặt vòng lặp liệt kê các phần tử của S k , dễ thấy là ta có thể sử dụng vòng lặp for 
 trên PASCAL : for y:= 0 to 1 do 
 hoặc trên C: for (y=0;y<=1;y++) 
Chương trình trên Pascal 
var	n: integer; 
	b: array[1..20] of 0..1; 
	count: word; 
procedure Ghinhan; 
var i: integer; 
begin 
	count := count+1; 
 write(count:5, '. '); 
	for i := 1 to n do write(b[i]:2); 
 writeln; 
end; 
procedure Xau(i: integer); 
var j: integer; 
begin 
	for j := 0 to 1 do 
	begin 
 	 b[i] := j; 
	 if i = n then Ghinhan else Xau(i+1); 
	end; 
end; 
BEGIN {Main program} 
	write('n = '); readln(n); 
	count := 0; Xau(1); 
	write('Gõ Enter để kết thúc... '); readln 
END. 
Chương trình trên C 
include 
#include 
#include 
int n, count; 
int b[20]; 
void Ghinhan() { 
 int i, j; 
 count++; 
 printf(“Xau thu %i. ",count); 
 for (i=1 ; i<= n ;i++) { 
	 j=b[i]; 
	 printf("%i ", j); 
 } 
 printf("\n"); 
} 
void Xau(int i){ 
 int j; 
 for (j = 0; j<=1; j++) { 
 b[i] = j; 
 if (i==n) Ghinhan(); 
 else Xau(i+1); 
 } 
} 
int main() { 
 printf(“n = "); 
 scanf("%i ",&n); printf("\n"); 
 count = 0; Xau(1); 
 printf(“Count = %d ", count); 
 getch(); 
} 
C©y liÖt kª d·y nhÞ ph©n ®é dµi 3 
Liệt kê các m -tập con của n -tập 
Liệt kê các m-tập con của n-tập 
Bài toán: Liệt kê các tập con m phần tử của tập N = {1, 2, ..., n }. 
 Bài toán dẫn về: Liệt kê các phần tử của tập: 
 S ( m,n )={( x 1 ,..., x m ) N m : 1 ≤ x 1 <...<x m ≤ n } 
Giải quyết 2 vấn đề mấu chốt 
Tõ ®iÒu kiÖn: 1 a 1 < a 2 < ... < a m n 
	suy ra 	S 1 = {1, 2, ..., n -( m -1) }. 
Gi¶ sö ®· cã tËp con ( a 1 , ..., a k- 1 ). 
 Tõ ®iÒu kiÖn a k -1 < a k < . . . < a m ≤ n , ta suy ra 
 S k = { a k -1 +1, a k -1 +2, ..., n -( m-k )}. 
Để c ài đặt vòng lặp liệt kê các phần tử của S k , dễ thấy là ta có thể sử dụng vòng lặp 
 của PASCAL: for y:= a[k-1]+1 to n-m+k do ... 
 của C : for ( y=a[k-1]+1;y<=n-m+k;y++) ... 
Chương trình trên Pascal 
var n, m: integer; 
	a: array[0..20] of byte; 
	count: word; 
procedure Ghinhan; 
var i: integer; 
begin 
	count := count+1; 
 write(count:5, '. '); 
	for i := 1 to m do write(a[i]:4); 
 writeln; 
end; 
procedure MSet(i: integer); 
var j: integer; 
begin 
 for j := a[i-1] +1 to n-m+i do 
 begin 
 a[i] := j; 
	 if i =m then Ghinhan else MSet(i+1); 
 end; 
end; 
BEGIN {Main program} 
	write('n, m = '); readln(n, m); 
	count := 0; MSet(1); 
	write('Gõ Enter để kết thúc... '); readln 
END. 
Chương trình trên C 
#include 
#include 
#include 
int n, m, count; 
int a[20]; 
void Ghinhan() { 
 int i, j; 
 count++; 
 printf("Tap con thu %i. ",count); 
 for (i=1 ; i<= m ;i++) { 
	 j=a[i]; 
	 printf("%i ", j); 
 } 
 printf("\n"); 
} 
void MSet(int i){ 
 int j; 
 for (j = a[i-1] +1; j<= n-m+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(); 
} 
Cây liệt kê S(5,3) 
Liệt kê hoán vị 
Liệt kê hoán vị 
TËp c¸c ho¸n vÞ cña c¸c sè tù nhiªn 1, 2, ..., n lµ tËp 
  n = {( x 1 ,..., x n ) N n : x i ≠ x j , i ≠ j }. 
Bài toán: Liệt kê tất cả các phần tử của  n 
Giải quyết 2 vấn đề mấu chốt 
Râ rµng S 1 = N . Gi¶ sö ta ®ang cã ho¸n vÞ bé phËn ( a 1 , a 2 , ..., a k -1 ), tõ ®iÒu kiÖn a i ≠ a j , víi mäi i ≠ j ta suy ra 
	 S k = N \ { a 1 , a 2 , ..., a k -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ả S k ? 
Mô tả S k 
Xây dựng hàm nhận biết UCV: 
function UCV(j,k: integer): boolean; 
(* UCV nhận giá trị true khi và chỉ khi j S k *) 
var i: integer; 
begin 
 for i:=1 to k-1 do 
 if j = a[i] then 
 begin 
 UCV:= false; exit; 
 end; 
 UCV:= true; 
end; 
Mô tả S k 
Câu lệnh qui ước “ for y S k do ” có thể 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	 	 
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. 
#include 
#include 
#include 
int n, count; 
int b[20]; 
int Ghinhan() { 
 int i, j; 
 count++; 
 printf("Hoan vi thu %i. ",count); 
 for (i=1 ; i<= n ;i++) { 
	 printf("%i ", b[i]); 
 } 
 printf("\n"); 
} 
int UCV(int j, int k) 
{ 
int i; 
 for (i=1; i<=k-1; i++) 
 if (j == b[i]) return 0; 
 return 1; 
} 
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(); 
} 
Cây liệt kê hoán vị của 1, 2, 3 
The n -Queens Problem 
The n -Queens Problem 
Giả sử ta có 8 con hậu... 
...và bàn cờ quốc tế 
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 
Hai con hậu bất kỳ không được xếp trên cùng một dòng ... 
The n-Queens Problem 
Hai con hậu bất kỳ không được xếp trên cùng một cột ... 
The n-Queens Problem 
Hai con hậu bất kỳ không được xếp trên cùng một đường chéo! 
The n-Queens Problem 
Kích thước n*n 
n con hậu 
n dòng 
n cột 
The n-Queens Problem 
Xét bài toán xếp n con hậu lên bàn cờ kích thước n x n. 
Bài toán xếp hậu 
Liệt kê tất cả các cách xếp n quân Hậu trên bàn cờ n n sao cho chúng không ăn được lẫn nhau, nghĩa là sao cho 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ờ. 
Biểu diễn lời giải 
Đánh số các cột và dòng của bàn cờ từ 1 đến n . Một cách xếp hậu có thể biểu diễn bởi bộ có n thành phần ( a 1 , a 2 ,..., a n ), trong đó a i là toạ độ cột của con Hậu ở dòng i . 
Các điều kiện đặt ra đối với bộ ( a 1 , a 2 ,..., a n ): 
 a i a j , với mọi i j (nghĩa là hai con hậu ở hai dòng i và j không được nằm trên cùng một cột); 
| a i – a j | | i – j |, với mọi i j (nghĩa là hai con hậu ở hai ô ( a i , i ) và ( a j , j ) không được nằm trên cùng một đường chéo). 
Phát biểu bài toán 
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 ={( a 1 , a 2 , ..., a n ) N n : 
 a i ≠ a j và | a i – a j | ≠ | i – j |, i ≠ j }. 
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 S k 
 int i; 
 for (i=1; i<k; i++) 
 if ((j == a[i])||(fabs(j-a[i])== k-i)) return 0; 
 return 1; 
} 
Chương trình trên C 
#include 
#include 
int n, count; 
int a[20]; 
int Ghinhan() { 
 int i; 
 count++; printf("%i. ",count); 
 for (i=1; i<=n;i++) printf("%i ",a[i]); 
 printf("\n"); 
} 
int UCVh(int j, int k) { 
/* UCVh nhận giá trị 1 khi và chỉ khi j S k */ 
 int i; 
 for (i=1; i<k; i++) 
 if ((j==a[i])||(fabs(j-a[i])==k-i)) return 0; 
 return 1; 
} 
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(); 
} 
110 
Toán rời rạc - NĐN 
Chú ý 
Rõ ràng là bài toán xếp hậu không phải là luôn có lời giải, chẳng hạn bài toán không có lời giải khi n= 2, 3. Do đó điều này cần đượ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. 
Thuật toán làm việc như thế nào 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
1 
đã đặt 
Xếp con hậu ở dòng 1 
 vào vị trí cột 1 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
1 
đã đặt 
ROW 2, COL 1 
Thử xếp con hậu ở dòng 2 vào vị trí cột 1 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
1 
đã đặt 
ROW 2, COL 2 
Thử xếp con hậu ở dòng 2 vào vị trí cột 2 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
1 
đã đặt 
ROW 2, COL 3 
Thử xếp con hậu ở dòng 2 vào vị trí cột 3 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 3 
Chấp nhận xếp con hậu ở dòng 2 vào vị trí cột 3 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 3 
ROW 3, COL 1 
Thử xếp con hậu ở 
dòng 3 
vào cột đầu tiên 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 3 
ROW 3, COL 2 
Thử cột tiếp theo 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 3 
ROW 3, COL 3 
Thử cột tiếp theo 
Thuật toán làm việc như thế nào 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 3 
ROW 3, COL 4 
Thử cột tiếp theo 
Thuật toán làm việc như thế nào 
...không có vị trí đặt con hậu ở dòng 3. 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 3 
ROW 3, COL 4 
Thuật toán làm việc như thế nào 
 Quay lại dịch chuyển con hậu ở dòng 2 
ROW 1, COL 1 
1 
đã đặt 
ROW 2, COL 3 
Thuật toán làm việc như thế nào 
Đẩy con hậu ở dòng 2 sang cột thứ 4. 
ROW 1, COL 1 
1 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Xếp được con hậu ở dòng 2 ta tiếp tục xếp con hậu ở dòng 3 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Thử xếp con hậu ở dòng 3 vào cột 1 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Thử xếp con hậu ở dòng 3 vào cột 2 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
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 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Thử xếp được con hậu ở dòng 4 vào cột 2 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Thử xếp được con hậu ở dòng 4 vào cột 3 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Thử xếp được con hậu ở dòng 4 vào cột 4 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Không xếp được con hậu ở dòng 4 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Quay lại tìm vị trí mới cho con hậu ở dòng 3: Thử cột 3 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Quay lại tìm vị trí mới cho con hậu ở dòng 3: Thử cột 4 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Không có cách xếp mới cho con hậu ở dòng 3 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
Quay lại tìm cách xếp mới cho con hậu ở dòng 2: Không có 
ROW 1, COL 1 
2 
đã đặt 
ROW 2, COL 4 
Thuật toán làm việc như thế nào 
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 
2 
đã đặt 
ROW 2, COL 4 
Mét lêi gi¶i cña bµi to¸n xÕp hËu khi n = 8 
140 
Toán rời rạc - NĐN 
 The End 
141 
Questions? 
Toán rời rạc