Quay lui---Backtracking

Quy lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Ok. Có vẻ vẫn chưa được rõ ràng lắm. Giờ chúng ta xem xét một vài ví dụ và khái quát hóa phương pháp quay lui.

Bài toán n quân hậu (n Queens)

Bài toán như sau:

Problem 1: Cho một bàn cờ hình vuông kích thước n \times nn quân hậu. Hãy tìm cách đặt n quân hậu trên bàn cờ sao cho không có 2 quân hậu nào có thể ăn được nhau.

 

Mã hóa lời giải: ta thấy để các quân hâu không ăn được nhau, ta phải xếp n quân hậu trên n hàng của bàn cờ. Ta dùng mảng Q[1,2,\ldots,n], trong đó Q[i] = j nếu quân hậu ở hàng thứ i được đặt ở cột j.

Ý tưởng chính của thuật toán: giả sử chúng ta đã đặt được r-1 quân hậu, 1 \leq r < n, trên r-1 hàng đầu tiên sao cho không có 2 quân hậu nào ăn được nhau. Cụ thể các phần tử Q[1,2,\ldots, r-1] sẽ khác 0 và các phần tử Q[r,r+1. \ldots, n] đều bằng 0. Chúng ta tìm cách đặt một quân hậu trên hàng thứ r. Ta sẽ thử lần lượt đặt vào cột thứ 1,2,\ldots, n. Nếu đặt vào cột thứ j mà bị một trong r quân hậu đã đặt trước đó ăn, ta sẽ thử cột thứ j+1. Nếu ta tìm được một ví trí đặt khả dĩ (a feasible position), ta sẽ đặt vào đó và gọi đệ quy để đặt hàng thứ r+1. Giả mã như sau:

RecursiveQueen(Q[1,2,\ldots, n],r):
    if(r = n+ 1)
        print Q
   else
        for j \leftarrow 1 to n
            legal \leftarrow True
            for i \leftarrow 1 to r-1              \ll check conflict \gg
                if (Q[i] = j) or (Q[i] = j+r-i) or (Q[i] = j-r+i)
                    legal \leftarrow False
            if legal = True
                Q[r] \leftarrow j
                RecursiveQueen(Q[1,2,\ldots, n],r+1)

 
Code của giả mã bằng C. Code đầy đủ được cho ở cuối bài.

 
void recursive_queen(int _array[], int n, int r){
   int i=1, j = 1;
   int legal = 0;
   if(r == n +1){
	print_queen(_array, n);
	exit(0);
   } else{
	for(j = 1; j <= n ; j++){
	    legal = 1; // legal = true
	    for(i = 1; i <= r-1; i++){
		if(_array[i] == j || _array[i] == j + r - i ||_array[i] == j - r + i){
		   legal = 0; // legal = false
		 }
	   }
	   if(legal == 1) {
	        // legal = true
	       _array[r] = j;
	       recursive_queen(_array, n, r+1);
	   }
        }
   }
}

 
Cây đệ quy là một cách nhìn khác của thuật toán. Tưởng tượng ta có một cây với gốc tượng trưng cho cấu hình ban đầu của bàn cờ (mảng Q[1,2,\ldots,n] gồm toàn 0). Nút con của gốc, gọi là nút level 1, là các cách đặt một quân hậu vào hàng thứ 1. Nút con của một nút level 1, gọi là nút level 2, là các cách đặt khả dĩ một quân hậu vào hàng thứ 2. Cứ như thế đến nút level n (tại sao chỉ có n level) ta sẽ thu được một cây gọi là cây đệu quy. Có thể thấy rằng thuật toán quay lui ở trên thực ra chính là một cách duyệt cây theo chiều sâu cho đến khi tìm được một nút ở level n. Hình minh họa sau với n=4 được lấy từ [1]
queen
Có thể thấy thuật toán trên có thời gian cỡ O(n!). Tuy nhiên nếu bạn cần một lời giải bất kì, bài toán này có công thức giải và bạn chỉ mất thời gian để in lời giải ra (O(n))[3].

Sudoku

Sudoku là một trò chơi khá phổ biến và chắc ai (readers of this bog) cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9x9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3x3 chính là các số khác nhau từ 1 đến 9. Ví dụ một câu đố và lời gải tương ứng như sau (hình được lấy từ wikipedia):
sudoku

Trong bài này mình sẽ giới thiệu cách giải sudoku bằng thuật toán quay lui. Ý tưởng của thuật toán cũng giống bài toán n quân hậu. Mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán (ở đây chú ý mảng chỉ có kích thước 9\times 9). Thủ tục Feasible(S,x,y,k) kiểm trả xem giá trị k có khả dĩ với ô S[x][y] không.

Sudoku(S[1,2,\ldots, 9][1,2,\ldots, 9],x,y):
    if y = 10
        if x = 9
            print S
       else
            Sudoku(S[1,2,\ldots, 9][1,2,\ldots, 9],x+1,1)
    else if S[x,y] = \emptyset
        for k \leftarrow 1 to 9
            if Feasible(S,x,y,k)
                S[x,y] \leftarrow k
                Sudoku(S[1,2,\ldots, 9][1,2,\ldots, 9],x,y+1)
                S[x,y] \leftarrow \emptyset        \ll for next branching \gg
    else                                    \ll S[x,y] is given \gg
        Sudoku(S[1,2,\ldots, 9][1,2,\ldots, 9],x,y+1)

 
Code của giả mã trên bằng C:

 
void solve_sudoku(int S[][9], int x, int y){
	if(y == 9){
		if(x == 8){
			printSolution(S);
			exit(0);
		} else {
			solve_sudoku(S, x+1,0);
		}
	} else if(S[x][y] == 0){
		int k = 0;
		for (k = 1; k <=9; k++){
			if(feasible(S,x,y,k)){
				S[x][y] = k;
				solve_sudoku(S, x, y+1);
				S[x][y] = 0;
			}
		}
	} else {
		solve_sudoku(S,x,y+1);
	}
}

 
Giả mã của thủ tục Feasible(S,x,y,k) như sau:

Feasible(S[1,2,\ldots, 9][1,2,\ldots, 9],x,y, k):
    for i \leftarrow 1 to 9
        if S[x,i]=k
            return False
    for i \leftarrow 1 to 9
        if S[i,y]=k
            return False
    a \leftarrow \lfloor (x-1)/3 \rfloor, b \leftarrow \lfloor (y-1)/3 \rfloor
    for i \leftarrow 3a+1 to 3a+3
        for j \leftarrow 3b+1 to 3b+3
           if S[i,j] = k
                return False
    return True

 
Code bằng C của giả mã (code đầy đủ được cho ở cuối bài):

 
int feasible(int S[][9], int x, int y, int k){
	int i = 0, j = 0;
	for(i = 0; i <9 ; i++){
		if(S[x][i] == k) return 0;
	}
	for(i = 0; i <9 ; i++){
			if(S[i][y] == k) return 0;
		}
	int a = x/3, b = y/3;
	for(i = 3*a; i < 3*a+3; i++){
		for(j = 3*b; j < 3*b+3; j++){
			if(S[i][j] == k) return 0;
		}
	}
	return 1;

}

 

Subset Sum

Subset Sum là một trong những bài toán NP-hard. Trong bài này chúng ta sẽ thiết kế thuật toán quay lui để giải bài toán Subset Sum.

Problem 2: Cho một mảng n phần tử X[1,2,\ldots, n] và một số T. Có tồn tại một tập con các phần tử của mảng X sao cho tổng của chúng bằng T.

 
Ví dụ: X = \{8,6,7,5,3,10,9\}T = 12. Lời giải là true vì tập con \{7,5\} của X có tổng bằng 12.

Ý tưởng của thuật toán quay lui dựa trên quan sát sau: xét một phần tử x \in X, tồn tại một dãy con có tổng bằng T nếu một trong hai điều kiện sau là đúng:

  1. Tồn tại một tập con của X \setminus \{x\} có tổng bằng T - x
  2. Tồn tại một tập con của X \setminus \{x\} có tổng bằng T

Giả mã như sau:

SubsetSum(X[1,2,\ldots, n],r,T):
    if T = 0
        return True
    else if T > 0 or n == 0
        return False
    return SubsetSum(X[1,2,\ldots,n-1],T) Or
                SubsetSum(X[1,2,\ldots,n-1],T- X[n])

 
Code của giả mã bằng C:

 
int subset_sum(int X[], int r, int T){
	if(T == 0) return 1;
	if(T < 0 || r == -1) return 0;
	if(subset_sum(X, r-1, T-X[r]) == 1) return 1;
	if(subset_sum(X,r-1, T) == 1) return 1;
	return 0;
}

 

Phân tích thời gian: Ở mỗi bước của thuật toán quay lui, ta gọi đệ quy hai lần trên mảng con của X với kích thước nhỏ hơn 1. Ta có:

 T(n) = 2T(n-1) + O(1) = O(2^n)

 

Code: queen, sudoku, subsetsum, data of subsetsum

Tài liệu tham khảo

[1] J. Erickson. Algorithm Lecture Notes, UIUC.
[2] n queen on stackexchange: http://cstheory.stackexchange.com/questions/12682/is-the-n-queens-problem-np-hard
[3] B. Bernhardsson, Explicit Solutions to the N-queens Problem for All N, SIGART Bull. 2(2)(1991)7.

Bài Tập

Bài 1 (Longest Increasing Subsequence) Cho một mảng n phần tử A[1,2,\ldots,n]. Tìm một dãy dài nhất (k lớn nhất) các chỉ số 1 \leq i_1 < i_2 < \ldots < i_k \leq n sao cho A[i_1] \leq A[i_2] \leq \ldots \leq A[i_k] bằng phương pháp quay lui. (Gợi ý: xét A[1], nếu A[1] nằm trong dãy con tăng, đệ quy trên A[2,3,\ldots] tìm dãy con tăng dài nhất mà mọi phần tử đều lớn hoưn A[1]. Nếu A[1] không nằm trong dãy con tăng, đệ quy trên A[2,3,\ldots,n]).

Bài 2 (Dãy gia tốc) Một dãy X[1,2,\ldots,n] gọi là gia tốc nếu 2X[i] >  X[i-1] + X[i+1]. Cho một dãy A[1,2,\ldots,n], tìm dãy con gia tốc dài nhất của A. Tìm công thức đệ quy cho bài toán, dựa vào đó thiết kế giải thuật quay lui.

Bài 3 Hãy sửa đổi thuật toán quay lui ở trên của bài toán Subset Sum để in ra ít nhất một dãy con có tổng bằng T của X.

Facebook Comments

Tags: , , , ,

  1. MuaXuan’s avatar

    Chào anh, em đọc code giải sudoku của anh có đoạn em không hiểu lắm ạ:

    if(feasible(S, x, y, k) != 0) {
    S[x][y] = k;
    solve_sudoku(S, x, y+1);
    S[x][y] = 0;
    }

    tại sao sau khi gọi lại hàm solve_sudoku(S, x, y+1) lại phải gán S[x][y] = 0 vậy ạ?

    Reply

    1. Hung Le’s avatar

      Hi bạn MuaXuan,
      Nếu bạn để ý kĩ, hàm feasible(S,x,y,k) của mình đúng nếu đầu vào là ô S[x][y] \not= k. Do đó sau mỗi lần thử đặt k vào ô S[x][y], mình gán lại ô này bằng 0. Thực ra, nếu để ý kĩ, bạn sẽ thấy ta không nhất thiết phải làm như vậy. Bạn có thể đặt lệnh gán S[x][y] = 0 ra ngoài vòng lặp for(k = 1; k <= 9; k++). Lý do ta phải gán bằng 0 là như sau: Giả sử ô trước khi gán giá trị cho S[x][y] là ô S[x][y-1] (cả hai ô S[x][y], S[x][y-1] ban đầu là rỗng). Nếu bạn vẽ cây đệ quy ra, bạn sẽ thấy mỗi lần thử S[x][y-1] = 1, bạn sẽ gán mọi giá trị có thể có cho ô tiêp theo S[x][y]. Sau khi thử S[x][y-1] = 1, bạn thử S[x][y-1] = 2. Khi thử S[x][y-1] = 2, bạn lại phải thử lại toàn bộ giá trị có thể của S[x][y]. Do đó, trước khi thử gán S[x][y-1] = 2, bạn phải đảm bảo S[x][y] = 0 để code chạy đúng. Hi vọng mình trả lời đúng câu hỏi của bạn. Nếu bạn vẫn thấy chưa hoàn toàn trả lời được, bạn có thể comment mình sẽ giải thích thêm.

      Reply

    2. MuaXuan’s avatar

      Ban đầu em cũng nghĩ như vậy nhưng không chắc nên đã hỏi, cảm ơn anh đã trả lời 🙂

      Reply

      1. Hùng Lê’s avatar

        Không có gì! Cám ơn bạn đã ghé thăm.

        Reply

      2. Thinh Nguyen’s avatar

        Ở phần giả mã của bài "n Queens": Không biết có phải là e hiểu sai không nhưng nghĩ vòng lặp lớn phải cho "j" chạy từ 1 -> n chứ sao lại là "i" ạ?

        Reply

        1. Hùng Lê’s avatar

          Đúng rồi bạn. Mình gõ sai. Trong phần code thật thì mình để là j. Cám ơn bạn đã chỉ ra lỗi.

          Reply

        2. hoahuongduong’s avatar

          anh có thể gợi ý bài dãy gia tốc được không ạ ?

          Reply

        3. Thi’s avatar

          cho mình hỏi có thể áp dụng giải thuật quay lui này để giải bài toán mã đi tuần được không?

          Reply

          1. Hùng Lê’s avatar

            Hi bạn,
            Câu trả lời là có nhé. Quay lui có thể áp dụng cho tất cả các bài toán mà bạn gặp trong thực tế. Vấn đề chỉ là nhanh hay chậm mà thôi.

            Hùng

            Reply

Reply

Your email address will not be published. Required fields are marked *