Thuật Toán 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 n$ và $n$ 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,\dots ,n]$, trong đó $Q\left[i\right]=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\le 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,\dots ,r-1]$ sẽ khác $0$ và các phần tử $Q[r,r+1.\dots ,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,\dots ,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,\dots ,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 $\left(Q\right[i]=j)$ or $\left(Q\right[i]=j+r-i)$ or $\left(Q\right[i]=j-r+i)$
                    $legal\leftarrow$ False
            if $legal=$ True
                $Q\left[r\right]\leftarrow j$
                RecursiveQueen($Q[1,2,\dots ,n],r+1$)

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

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,\dots ,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]

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\left(n\right)$)[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):

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\left[x\right]\left[y\right]$ không.

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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,\dots ,9][1,2,\dots ,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):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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,\dots ,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\}$ và $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 \left\{x\right\}$ có tổng bằng $T-x$
2. Tồn tại một tập con của $X\setminus \left\{x\right\}$ có tổng bằng $T$

Giả mã như sau:

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

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

1 2 3 4 5 6 7

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\left(n\right)=2T(n-1)+O\left(1\right)=O\left(2^n\right)$

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,\dots ,n]$. Tìm một dãy dài nhất ($k$ lớn nhất) các chỉ số $1\le i_1$ < $i_2$<$\dots$<$i_k\le n$ sao cho $A\left[i_1\right]\le A\left[i_2\right]\le \dots \le A\left[i_k\right]$ bằng phương pháp quay lui. (Gợi ý: xét $A\left[1\right]$, nếu $A\left[1\right]$ nằm trong dãy con tăng, đệ quy trên $A[2,3,\dots ]$ tìm dãy con tăng dài nhất mà mọi phần tử đều lớn hoưn $A\left[1\right]$. Nếu $A\left[1\right]$ không nằm trong dãy con tăng, đệ quy trên $A[2,3,\dots ,n]$).

Bài 2 (Dãy gia tốc) Một dãy $X[1,2,\dots ,n]$ gọi là gia tốc nếu $2X\left[i\right]$ > $X[i-1]+X[i+1]$. Cho một dãy $A[1,2,\dots ,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$.