Bài giảng Cơ sở lập trình nâng cao - Chương 4: Phương pháp thiết kế thuật toán Quay lui - Tôn Quang Toại

CƠ SỞ LẬP TRÌNH NÂNG CAO 
Biên soạn: Ths.Tôn Quang Toại 
TonQuangToai@yahoo.com 
TPHCM, NĂM 2013 
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN – QUAY LUI – 
Chương 4 
Nội dung 
Giới thiệu 
Phương pháp 
Sơ đồ cài đặt 
Các ví dụ 
Ưu điểm và khuyết điểm 
Hình ảnh 
Giới thiệu 
Định nghĩa [Quay lui – Backtracking]: 
Quay lui là một phương pháp thiết kế thuật toán để tìm nghiệm của bài toán bằng cách xét tất cả các phương án . 
Một phương án gồm nhiều thành phần, và phương pháp quay lui sẽ xây dựng từng thành phần trong mỗi bước . 
Trong quá trình xây dựng thành phần thứ i (tìm nghiệm cho thành phần thứ i), nếu không thể xây dựng được thì quay lại chọn nghiệm khác cho thành phần thứ (i-1) 
Bài toán 
Phát biểu bài toán: Giả sử nghi ệ m c ủa b à i to án cần tìm c ó d ạng X=(x 1 , x 2 , , x k , ), trong đó 
x i là 1 thành phần nghiệm của bài toán 
x i có một miền giá trị D i nào đó (x i D i ). 
Số lượng thành phần x i có thể xác định hay không xác định 
Bài toán có những ràng buộc là F 
Yêu cầu: Hãy xây dựng 1 nghiệm hay tất cả các nghiệm của bài toán thỏa điều kiện F 
Phương pháp 
Phương pháp Quay lui 
Phương pháp Quay lui xây dựng dần nghiệm X của bài toán : Bắt đầu từ x 1 được chọn ra từ tập D 1 , rồi đến x 2 được chọn ra từ tập D 2 , ... bằng cách thử mọi khả năng có thể xảy ra. 
Một cách tổng quát: Nếu chúng ta đã xác định được lời giải bộ phận gồm ( i -1) thành phần X(i-1) = (x 1 , x 2 , ..., x i-1 ), bây giờ chúng ta tìm giá trị cho thành phần x i bằng cách xét mọi khả năng có thể có của x i trong tập D i . Với mỗi khả năng j (j D i ) , chúng ta kiểm tra xem có thể thỏa điều kiện là nghiệm thành phần của bài toán không 
Phương pháp 
Có 2 khả năng xảy ra: 
Nếu khả năng j thỏa điều kiện thì 
Gán x i = j 
Tiếp theo t ìm nghiệm cho thành phần x i+1 
Nếu đã thử mọi khả năng của j mà không thỏa điều kiện bài toán thì có nghĩa là đi theo con đường 	X(i-1) = (x 1 , x 2 , ..., x i-1 ) sẽ không thể dẫn đến kết quả. C húng ta quay về bước trước để xác định lại x i-1 (bằng cách chọn 1 giá trị khác trong D i-1 ) . 
Phương pháp 
Quá trình này dừng cho đến khi tìm được nghiệm của bài toán hay vét qua hết khả năng mà không thể tìm được nghiệm của bài toán 
Phương pháp 
Cây tìm kiếm (Cây không gian tìm kiếm): Quá trình tìm kiếm lời giải theo phương pháp Quay lui sẽ sinh ra 1 cây tìm kiếm 
x 1 
x 2 
x 3 
Phương pháp 
Đặc điểm của phương pháp Quay lui 
Xây dựng dần từng thành phần trong 1 phương án 
Trong quá trình xây dựng phương án nó thực hiện: 
Tiến: Để mở rộng các thành phần của phương án 
Lui: Nếu không thể mở rộng phương án 
Xét mọi khả năng có thể xảy ra 
Phương pháp quay lui còn được gọi với những tên khác như: Vét cạn (Exhaustion), Duyệt, thử và sai (Trial and Error),  
Phương pháp 
Các bước sử dụng phương pháp Quay lui 
Bước 1 [Biểu diễn nghiệm]: Biểu diễn nghiệm bài toán dưới dạng một vector 	X=(x 1 , x 2 , x 3 , , x k , ) 
Bước 2 [Tìm miền giá trị thô]: Xác định các miền giá trị cơ bản D i cho các x i (D i =[min i , max i ]) 
Bước 3 [Ràng buộc]: Tìm những ràng buộc của x i và giữa x i và x j . Từ đó có thể xác định lại các D i 
Bước 4: Xác định những điều kiện F khác để X là nghiệm của bài toán 
Phương pháp 
Xác định miền giá trị D i (Bước 3): 
Xác định cận trên và cận dưới của miền D i (D i =[min i , max i ]) 
Chi tiết việc xác định D i 
Nếu các D i và D j độc lập nhau thì không cần chỉnh sửa D i trong bước 2 
Nếu D i bị thay đổi do việc chọn lựa ở những thành phần x j (j<i) trước đó thì chúng ta cần xác định lại D i khi chọn lựa x j ở bước j 
Dùng biến mảng trạng thái để lưu sự biến đổi của miền giá trị 
Sơ đồ cài đặt 
Nếu các D i và D j độc lập nhau: 
void BackTrack_1A( int i){	 if (thỏa điều kiện bài toán F)	Tìm được 1 nghiệm	 else 	 for (j D i )	{	x i = j;	BackTrack_1A(i+1);	}} 
Sơ đồ cài đặt 
Nếu các D i và D j độc lập nhau: 
void BackTrack_1B( int i){	 for (j D i )	{	x i = j;	 if (thỏa điều kiện bài toán F)	Tìm được 1 nghiệm	 else 	BackTrack_1B(i+1);	}} 
Sơ đồ cài đặt 
Nếu các D i và D j phụ thuộc nhau: 
void BackTrack_2A( int i){	 if (thỏa điều kiện bài toán F)	Tìm được 1 nghiệm	 else 	 for (j D i và status[j]==0)	{	 status[j] = 1; 	x i = j;	BackTrack_2A(i+1);	 status[j]=0; 	}} 
Sơ đồ cài đặt 
Nếu các D i và D j phụ thuộc nhau : 
void BackTrack_2B( int i){	 for (j D i và status[j]==0)	{	 status[j]=1; 	x i = j;	 if (thỏa điều kiện bài toán F)	Tìm được 1 nghiệm	 else 	BackTrack_2B(i+1);	 status[j]=0; 	}} 
Sơ đồ cài đặt 
Sơ đồ tổng quát 
void BackTrack_3A( int x[], int i , data input){	 int D[MAXCANDIDATES];	 int nD;	 if (IsSolution(x, i))	ProcessSolution(x, i, input);	 else 	{	ConstructCandidates(x, i, input, D, &nD);	 for (j D )	{	x[i] = j;	BackTrack_3A(x, i+1, input);	}  	}} 
Sơ đồ cài đặt 
Sơ đồ tổng quát 
void BackTrack_3B( int x[], int i, data input){	 int D[MAXCANDIDATES];	 int nD;	ConstructCandidates(x, i, input, D, &nD);	 for (j D )	{ 	x[i] = j;	 if (IsSolution(x, i, input))	ProcessSolution(x, I, input);	 else 	BackTrack_3B(x, i+1, input);	}} 
Các ví dụ: {1} Tổ hợp 
Một tổ hợp chập k của tập n phần tử (k ≤ n) là một tập hợp con gồm k phần tử của tập n phần tử 
Ví dụ: Tập {1, 2, 3, 4, 5} có các tổ hợp chập 2 là: 
Số lượng tổ hợp chập k của tập n phần tử: 
Các ví dụ: {1} Tổ hợp 
Bài toán: Hãy tìm tất cả các tổ hợp chập k của tập n phần tử 
Bước 1: Biểu diễn nghiệm X 
Bước 2: Tìm miền giá trị D i của x i 
Bước 3: Ràng buộc giữa x i và x j 
Bước 4: Xác định điều kiện F để X là nghiệm 
Các ví dụ: {1} Tổ hợp 
Cấu trúc dữ liệu 
#define MAX 20 int x[MAX+1]; int n, k; 
Các ví dụ: {1} Tổ hợp 
cài đặt 
void ToHop( int i){} 
Các ví dụ: {2} Chỉnh hợp lặp 
Một chỉnh hợp lặp chập k của tập n phần tử (k ≤ n) là một bộ (có thứ tự) gồm k phần tử của tập n phần tử và các thành phần của bộ có thể trùng nhau 
Ví dụ: Tập {1, 2, 3, 4, 5} có các chỉnh hợp lặp chập 2 là: 
Số lượng chỉnh hợp lặp chập k của tập n phần tử: 
Các ví dụ: {2} Chỉnh hợp lặp 
Bài toán: Hãy tìm tất cả các chỉnh hợp lặp chập k của tập n phần tử 
Bước 1: Biểu diễn nghiệm X 
Bước 2: Tìm miền giá trị D i của x i 
Bước 3: Ràng buộc giữa x i và x j 
Bước 4: Xác định điều kiện F để X là nghiệm 
Các ví dụ: {2} Chỉnh hợp lặp 
Cấu trúc dữ liệu 
#define MAX 20 int x[MAX+1]; int n, k; 
Các ví dụ: {2} Chỉnh hợp lặp 
cài đặt 
void ChinhHopLap( int i){} 
Các ví dụ: {3} Chỉnh hợp không lặp 
Một chỉnh hợp không lặp chập k của tập n phần tử (k ≤ n) là một bộ (có thứ tự) gồm k phần tử của tập n phần tử và các thành phần của bộ không được trùng nhau 
Ví dụ: Tập {1, 2, 3, 4, 5} có các chỉnh hợp không lặp chập 2 là: 
Số lượng chỉnh hợp không lặp chập k của tập n phần tử: 
Các ví dụ: {3} Chỉnh hợp không lặp 
Bài toán: Hãy tìm tất cả các chỉnh hợp không lặp chập k của tập n phần tử 
Bước 1: Biểu diễn nghiệm X 
Bước 2: Tìm miền giá trị D i của x i 
Bước 3: Ràng buộc giữa x i và x j 
Bước 4: Xác định điều kiện F để X là nghiệm 
Các ví dụ: {3} Chỉnh hợp không lặp 
Cấu trúc dữ liệu 
#define MAX 20 int x[MAX+1]; int n, k; int status[MAX+1]; 
Các ví dụ: {3} Chỉnh hợp không lặp 
cài đặt 
void ChinhHopKhongLap( int i){} 
Các ví dụ: {4} Xếp 8 Hậu 
Bài toán: Hãy đặt 8 con hậu lên bàn cờ vua 8x8, sao cho không con hậu nào được ăn con hậu nào, tức là chúng 
Không cùng hàng 
Không cùng cột 
Không cùng đường chéo 
Các ví dụ: {4} Xếp 8 Hậu 
Bước 1: Biểu diễn nghiệm X 
Bước 2: Tìm miền giá trị D i của x i 
Bước 3: Ràng buộc giữa x i và x j 
Bước 4: Xác định điều kiện F để X là nghiệm 
Các ví dụ: {4} Xếp 8 Hậu 
Cấu trúc dữ liệu 
#define MAX 8 int x[MAX+1]; 
int cot[MAX+1]; 
int cheoChinh[  ]; 
int cheoPhu[  ]; 
Các ví dụ: {4} Xếp 8 Hậu 
cài đặt 
void Xep8Hau( int i){} 
Ưu điểm và khuyết điểm 
Ưu điểm 
Luôn đảm bảo tìm nghiêm đúng 
Cho phép liệt kê mọi nghiệm của bài toán 
Khuyết điểm 
Độ phức tạp thuật toán lớn 
Thời gian thực thi lâu 
Chỉ giải những bài toán có kích thước nhỏ 
HẾT CHƯƠNG 4