Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 4: Kỹ thuật quay lui (Backtracking) - Ngô Hữu Phước

Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 4: Kỹ thuật quay lui (Backtracking) @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University1 Bài 4. Kỹ thuật quay lui Backtracking Nội dung: 4.1. Khái niệm về kỹ thuật quay lui (6) 4.2. Bài toán 8 con hậu - Eight Queen Problem (7) 4.3. Bài toán mã đi tuần - Knight Tour Problem (5) 4.4. Bài toán chiếc ba lô - Knapsack Problem (6) Tham khảo: 1. Lecture 11 – Backtracking.htm @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University2 4.1. Khái niệm kỹ thuật quay lui (1/6)  Kỹ thuật quay lui là quá trình phân tích từ trên xuống trong không gian tìm kiếm.  Trong trường hợp tổng quát, giả sử lời giải là một vector: a = (a[1], a[2], , a[n]) trong đó, mỗi phần tử a[i] chọn từ tập hữu hạn S[i] (các khả năng của a[i]). @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University3 4.1. Khái niệm kỹ thuật quay lui (2/6)  Ta sẽ giải quyết bài toán với kích thước k, có dạng: a = (a[1], a[2], , a[k]) và cố gắng mở rộng bằng việc thêm phần tử tiếp theo vào trong vector.  Sau khi thêm phần tử, kiểm tra xem có thể thực hiện tiếp được không.  Nếu vẫn có khả năng mở rộng, tiếp tục thực hiện; Nếu không, xóa phần tử a[k] và làm lại bài toán từ tập S[k]. @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University4 4.1. Khái niệm kỹ thuật quay lui (3/6) Gọi S[1], tập các khả năng của a tại bước đầu tiên. k = 1 While k > 0 do While S[k][] do (*advance*) a[k] = an element in S[k] If (a[1], a[2],, a[k]) is solution, print it! k = k + 1 Tính S[k], tập khả năng của a tại bước k. k = k - 1 (*backtrack*) @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University5 4.1. Khái niệm kỹ thuật quay lui (4/6) Sub Backtrack(a, k) If a is a solution, get it Else k = k +1 compute S[k] While S[k][] do a[k] = an element in S[k] S[k] = S[k] – a[k] Backtrack(a, k) End Sub @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University6 4.1. Khái niệm kỹ thuật quay lui (5/6)  Kỹ thuật đệ quy có thể được dùng trong kỹ thuật quay lui (đơn giản trong ứng dụng).  Kỹ thuật quay lui chắc chắn đúng khi liệt kê các khả năng có thể.  Để tăng hiệu quả của kỹ thuật, có thể cắt bớt không gian tìm kiếm. @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University7 4.1. Khái niệm kỹ thuật quay lui (6/6) Trong phần này, giải quyết một số bài toán, có sử dụng kỹ thuật quay lui:  Bài toán 8 hậu - Eight Queen Problem.  Bài toán mã đi tuần - Knight Tour Problem.  Bài toán chiếc ba lô - Knapsack Problem. @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University8 4.2. Eight Queen Problem (1/7) @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University9 Bài toán: đặt 8 con hậu trên bàn cờ sao cho không có 2 con hậu nằm trên cùng một hàng, cột và hàng ngang. Một lời giải Không phải lời giải 4.2. Eight Queen Problem (2/7) @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University10 Thực hiện: • Trạng thái: Sắp đặt từ 0 đến 8 con hậu lên bàn cờ. • Trạng thái khởi tạo: không có con hậu nào đặt lên bàn cờ. • Đặt từng con hậu lên bàn cờ. • Kiểm tra kết quả: 8 con hậu đã đặt lên bàn cờ, không có con hậu nào ăn được nhau.  648 cách đặt 8 con hậu 4.2. Eight Queen Problem (3/7) @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University11 Một vài cách đặt 8 con hậu lên bàn cờ (trong số 92 lời giải) 4.2. Eight Queen Problem (4/7) Ý tưởng:  Mỗi lần đệ quy, tìm cách đặt 1 con hậu lên một cột (hoặc hàng) riêng.  Với mỗi lần gọi, tình trạng bàn cờ đã biết (các con hậu đã đặt)  Nếu tại một cột, không đặt được con hậu mới, con hậu ở cột (hàng) đó được bỏ ra khỏi bàn cờ và chuyển xuống cột (hàng) trước đó. @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University12 4.2. Eight Queen Problem (5/7)  Nếu xét theo cột, tại một cột, tất cả các hàng đã xét, quay trở lại bước trước đó (xét cột trước).  Nếu con hậu không đặt được lên cột i, khi đó không thử trên cột i+1, quay lại cột i-1, bỏ con hậu đã đi sai.  Với cách tiếp cận này, có thể giảm bớt phép thử. @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University13 4.2. Eight Queen Problem (6/7) #include "stdio.h" #include "conio.h" #include "math.h" #define N 8 int k=0; typedef enum {FALSE, TRUE} bools; void printMatrix(int a[][N], int n); int getMarkedCol(int a[][N], int n, int row); bools feasible(int a[][N], int n, int row, int col); void N_Queens(int a[][N], int n, int row); void main() { int a[N][N] ; int i=0, j=0; for(i=0; i<N; i++) for(j=0; j<N; j++) a[i][j]=0; N_Queens(a,N,0); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University14 // In ma tran chua cac con hau void printMatrix(int a[][N], int n) { int i, j; for(i=0; i<n; i++) { for(j=0; j<n; j++) printf("%d ", a[i][j]); printf("\n"); } printf("\n"); } // Lay cac cot da danh dau trong hang row int getMarkedCol(int a[][N], int n, int row) { int j; for(j=0; j<n; j++) if(a[row][j] == TRUE) return j; printf("Loi: Khong co cot danh dau trong hang %d.\n", row); return -1; } 4.2. Eight Queen Problem (6/7) // Kiem tra xem con hau tiep theo co the dat o hang // row, cot col khong bools feasible(int a[][N], int n, int row, int col) { int i; int markedCol ; for(i=0; i<row; i++) { markedCol = getMarkedCol (a,n,i); if(markedCol == col || abs(row-i) == abs(col- markedCol)) return FALSE ; } return TRUE; } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University15 // Bai toan N hau void N_Queens(int a[][N], int n, int row) { int j; if(row < n) { for(j=0; j<n; ++j) if(feasible(a, n, row, j)) { a[row][j] = TRUE; N_Queens (a, n, row+1); a[row][j] = FALSE; } } else { k++; printf("Trang thai thu %d\n",k); printMatrix(a, n); } } 4.3. Knight Tour Problem (1/5) @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University16 4.3. Knight Tour Problem (2/5) Bài toán:  Trên bàn cờ 8 × 8 có một con mã (cách đi được định nghĩa thông thường).  Bắt đầu từ một góc của bàn cờ và thăm tất cả các ô cờ khác (63 ô cờ còn lại), sao cho mỗi ô cờ chỉ đến 1 lần.  Bài toán này được gọi là “mã đi tuần”. @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University17 4.3. Knight Tour Problem (3/5) Cách tiếp cận bài toán:  Có nhiều cách tiếp cận để giải bài toán này.  Một trong số đó là cách giải của J.C. Warnsdorff được đưa ra năm 1823.  Theo cách của J.C. Warnsdorff, con mã đi theo theo thứ tự được mã hóa (quy ước cách đi theo hình vẽ).  Từ một vị trí, con mã có thể đi tối đa đến 8 vị trí khác. Tùy theo vị trí trên bàn cờ, các vị trí có thể này được mã hóa theo thứ tự từ 1 đến 8. @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University18 4.3. Knight Tour Problem (4/5) #include "stdio.h" #include "conio.h" #include "stdlib.h“ #define M 5 #define SizeStep 8 void printVariant(int a[][M], int n); void knight(int a[][M], int n, int row, int col, int num); //dinh nghia cach di cho con ma int rowchange[] = {-2, -1, 1, 2, 2, 1,-1,-2}; int colchange[] = {-1, -2, -2,-1, 1, 2, 2, 1}; void main() { int a[M][M] ; int i=0, j=0; int m,n; for(i=0; i<M; i++) for(j=0; j<M; j++) { @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University19 for(m=0;m<M;m++) for(n=0;n<M;n++) a[m][n]=0 ; a[i][j]=1; knight(a, M, i, j, 2); } getch(); } void printVariant(int a[][M], int n) { // in ket qua int i, j; for(i=0; i<n; ++i) { for(j=0; j<n; j++) printf("%2d ", a[i][j]); printf("\n"); } } 4.3. Knight Tour Problem (5/5) void knight(int a[][M], int n, int row, int col, int num) { // tim vi tri ke tiep // vi tri ke tiep co gia nho nhat // vi tri hien tai la (row,col) int i; for(i=0; i<SizeStep; i++) { int newrow = row+rowchange[i]; int newcol = col+colchange[i]; if(newrow>=0 && newrow=0 && newcol<n && a[newrow][newcol]==0) { a[newrow][newcol]=num; if(num==n*n) { printVariant(a, M); @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University20 printf("\nNhan Enter de chon ket qua khac, nhan ESC de thoat!\n"); if(char c=getch()==27) exit(1); } else knight(a, n, newrow, newcol, num+1); a[newrow][newcol]=0; } } } 4.4. Knapsack Problem (1/9)  Bài toán: Cho N vật, mỗi vật có trọng lượng w(i) và giá trị v(i). Một chiếc ba lô có khả năng đựng tối đa (theo trọng lượng) là K. Chọn các vật như thế nào để tổng giá trị của chúng là lớn nhất và tổng trọng lượng không vượt quá K?  Ý tưởng: Ta ch ọn các vật có giá trị cao nhất vào ba lô. Tuy nhiên, các vật có trọng lượng khác nhau, do đó cần chọn một cách cẩn thận!!! @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University21 4.4. Knapsack Problem (2/9)  Trường hợp đơn giản: Giả sử các vật có cùng trọng lượng. Rõ ràng, dễ đưa ra lời giải! Lấy các vật có giá trị lớn.  Có thể sử dụng tỷ số giữa giá trị và trọng lượng và sử dụng tỷ số này? @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University22 4.4. Knapsack Problem (3/9)  Xem xét ví dụ sau với K = 9.  Với ví dụ trên, vật 4 có tỷ lệ cao nhất.  Nếu ta lấy vật 4 này, khi đó, chỉ có thể đưa vật 1 thêm vào ba lô. Tổng giá trị là: 7 + 15 = 22.  Tuy nhiên, nếu chọn đúng, nên lấy vật 1 và vật 2, mỗi vật chọn 1 lần, tổng giá trị là: 7 + 16 = 23. @Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University23 Vật Trọng lượng Giá trị Tỷ lệ 1 3 7 7/3 2 6 16 8/3 3 7 19 19/7 4 5 15 3 4.4. Knapsack 01 - Problem (4/9) #include "conio.h" #include "stdio.h" #define M 10 typedef enum {FALSE, TRUE} bools; // Tham so // K: trong luong toi da cua ba lo // used[]: cac vat co trong ba lo, // 0: chua lay, 1: da lay // weight[]: trong luong cua tung vat // value[]: gia tri cua tung vat // current[0]: trong luong hien tai // current[1]: gia tri hien tai // current[2]: gia tri max // pack[]: cac vat da lay o trang thai toi uu int nCalls=0; void knapSack(int K, bools used[], int item, int weight[], int value[], bools pack[], int current[], int n); @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University24 void main() { bools used[M]; bools pack[M]; int weght[M]; int value[M]; int current[3]; int K; for(int i=0;i<M;i++) used[i]=pack[i]=FALSE; current[0]=current[1]=current[2]=0; int n; printf("Nhap so vat: "); scanf("%d",&n); printf("Nhap trong luong toi da cho ba lo:"); scanf("%d",&K); 4.4. Knapsack 01 - Problem (5/9) for(int i=0;i<n;i++) { printf("Nhap trong luong vat %d:",i); scanf("%d",&weght[i]); printf("Nhap gia tri vat %d:",i); scanf("%d",&value[i]); } knapSack(K,used,0,weght,value,pack,current,n); printf("Tong so lan goi ham: %d\n",nCalls); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University25 void knapSack(int K, bools used[], int item, int weight[], int value[], bools pack[], int current[], int n){ nCalls++; // So loi goi // Kiem tra da xem xet den vat cuoi if (item == n) { // Kiem tra lai truong hop da lay vat if (current[1] > current[2]) { printf("Tong gia tri hien tai: %d\n",current[1]); // Luu thong tin hien tai current[2] = current[1]; for (int k = 0; k < n; k++) pack[k] = used[k]; printf("Cac vat duoc chon: "); for(int i=0;i<n;i++) 4.4. Knapsack 01 - Problem (6/9) if(pack[i]) printf("%d, ",i); printf("\n"); } } else { // Khi chua kiem tra het cac vat if (current[0] + weight[item] <= K) { // Lay vat item nay used[item] = TRUE; current[0] += weight[item]; current[1] += value[item]; knapSack(K, used, item+1, weight, value, pack, current, n); // Khi khong lay vat nay used[item] = FALSE; current[0] -= weight[item]; @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University26 current[1] -= value[item]; } // Khong lay duoc vat nay, tiep tuc thu vat khac. knapSack(K, used, item+1, weight, value, pack, current, n); } } 4.4. Knapsack Problem (7/9) #include "conio.h" #include "stdio.h" #define M 10 // Tham so // K: trong luong toi da cua ba lo // used[]: cac vat co trong ba lo, // 0: chua lay, 1: da lay // weight[]: trong luong cua tung vat // value[]: gia tri cua tung vat // current[0]: trong luong hien tai // current[1]: gia tri hien tai // current[2]: gia tri max // pack[]: cac vat da lay o trang thai toi uu int nCalls=0; void knapSack(int K, int used[], int item, int weight[], int value[], int pack[], int current[], int n); @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University27 void main() { int used[M]; int pack[M]; int weght[M]; int value[M]; int current[3]; int K; for(int i=0;i<M;i++) used[i]=pack[i]=0; current[0]=current[1]=current[2]=0; int n; printf("Nhap so vat: "); scanf("%d",&n); printf("Nhap trong luong toi da cho ba lo:"); scanf("%d",&K); 4.4. Knapsack Problem (8/9) for(int i=0;i<n;i++) { printf("Nhap trong luong vat %d:",i); scanf("%d",&weght[i]); printf("Nhap gia tri vat %d:",i); scanf("%d",&value[i]); } knapSack(K,used,0,weght,value,pack,current,n); printf("Tong so lan goi ham: %d\n",nCalls); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University28 void knapSack(int K, int used[], int item, int weight[], int value[], int pack[], int current[], int n) { nCalls++; // So loi goi // Kiem tra da xem xet den vat cuoi if (item == n) { // Kiem tra lai truong hop da lay vat if (current[1] > current[2]) { printf("Tong gia tri hien tai: %d\n",current[1]); // Luu thong tin hien tai current[2] = current[1]; for (int k = 0; k < n; k++) pack[k] = used[k]; printf("Cac vat duoc chon: "); 4.4. Knapsack Problem (9/9) for(int i=0;i<n;i++) if(pack[i]) printf("Vat %d, so lan chon %d ",i,pack[i]); printf("\n"); } } else { // Thu xem co the lay bao nhieu vat used[item] = (K - current[0]) / weight[item]; current[0] += used[item] * weight[item]; current[1] += used[item] * value[item]; while ( used[item] > 0 ) { knapSack(K, used, item+1, weight, value, pack, current, n); // Bo mot vat cuoi ra, neu khong lay duoc used[item]--; @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University29/29 current[0] -= weight[item]; current[1] -= value[item]; } // Neu khong lay vat do lan nao ca knapSack(K, used, item+1, weight, value, pack, current, n); } }