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,\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 &lt;= n ; j++){
legal = 1; // legal = true
for(i = 1; i &lt;= 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 &lt;=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 &lt;9 ; i++){
if(S[x][i] == k) return 0;
}
for(i = 0; i &lt;9 ; i++){
if(S[i][y] == k) return 0;
}
int a = x/3, b = y/3;
for(i = 3*a; i &lt; 3*a+3; i++){
for(j = 3*b; j &lt; 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]$ không âm 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 \{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 &lt; 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 hơ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à ô . Do đó sau mỗi lần thử đặt vào ô , mình gán lại ô này bằng . 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 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 là ô (cả hai ô ban đầu là rỗng). Nếu bạn vẽ cây đệ quy ra, bạn sẽ thấy mỗi lần thử , bạn sẽ gán mọi giá trị có thể có cho ô tiêp theo . Sau khi thử , bạn thử . Khi thử , bạn lại phải thử lại toàn bộ giá trị có thể của . Do đó, trước khi thử gán , bạn phải đảm bảo để 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

      1. Phat’s avatar

        Nếu như vậy thì sau lần cuối cùng thế k vào hàm feasible(lần lặp cuối cùng) thì S[x][y] cũng dc gán = 0 thì đáng lý ra các ô S[x][y] = rỗng ban đầu sau đó cũng đều = 0 hết chứ sao nó lại lưu lại được 1 giá trị khác 0 vậy bạn ? Mình vẫn chưa hiểu lắm, mong bạn giúp đỡ mình. Cảm ơn nhiều nhé bạn.

        Reply

        1. Hung Le’s avatar

          Khi lần cuối cùng bạn gán một giá trị vào, và gọi đệ quy lần cuối thì lúc đó thủ tục sẽ in ra luôn (2 câu lệnh if đầu tiên của thủ tục SUDOKU). Sau khi đã in ra rồi thì thủ tục sẽ exit. Nếu để ý phần code bằng C minh họa thì sẽ có câu lệnh exit(0) để thoát luôn khỏi chương trình ngay sau khi nó tìm được lời giải.

          Reply

          1. Phat’s avatar

            Ohhhh ra là vậy, mình hiểu r, cảm ơn bạn nhiều nha.

          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

                2. Châu’s avatar

                  Em chào anh , em cũng đang bắt đầu làm quen với các thuật toán cơ bản này. Anh cho em hỏi ở bài nQueens tại sao lại là Q[i]=j+r-i và Q[i]=j-r+i vậy ạ ?

                  Reply

                  1. dummy’s avatar

                    Hi Châu,
                    Đó là điều kiện kiểm tra xem nếu đặt vào ô [r,j] thì ở đường chéo xuôi và ngược giao nhau tại [r,j] đã đặt quân hậu nào trước đó hay chưa.

                    Best,
                    Hùng

                    Reply

                  2. doraemon’s avatar

                    Anh có thể đưa bài giải của phần bài tập không ạ? Em mần nát óc mấy hôm nay mà chưa giải nổi

                    Reply

                    1. Hung Le’s avatar

                      Hi bạn,
                      Cụ thể bạn muốn gợi ý bài nào? Mình có lẽ sẽ không có lời giải hoàn chỉnh nhưng sẽ gợi ý đến mức cụ thể nhất có thể.

                      Hùng

                      Reply

                      1. doraemon’s avatar

                        Bài 1 anh ơi. Em không biết phải làm thế nào để nó quay lui trong bài toán này. Em cảm ơn anh trước

                        Reply

                        1. Hung Le’s avatar

                          Hmm,
                          Mình không biết gợi ý này có hữu dụng hay không, bạn có thể thử ngẫm nghĩ. Bạn dùng thêm một biến $j$ để lưu trữ phần tử cuối cùng trong dãy con tăng đã tìm được khi tới bước đệ quy hiện tại. Sau đó xét thêm một phần tử mới $A[i]$ trong bước đệ quy hiện tại và so sánh $A[i]$ với $A[j].$ Nếu $A[i] \geq A[j]$ thì bạn có thể lựa chọn cho $A[i]$ vào dãy con tăng hay không và đệ quy tiếp. Nếu không thì bạn bỏ qua $A[i]$ và xét $A[i+1]$

                          Best,
                          Hùng

                          Reply

                        2. thangnq’s avatar

                          Bài toán Subset sum hình như thiếu điều kiện mảng X là mảng không âm.
                          Thanks

                          Reply

                          1. Hung Le’s avatar

                            Đúng rồi, cám ơn bạn. Mình đã bổ sung

                            Reply

                          2. Nguyễn Thái Hùng’s avatar

                            em có thể làm quen anh không ạ?
                            anh có dùng facebook không?

                            Reply

                            1. Hung Le’s avatar

                              Hi bạn,
                              Bạn có the like fanpage và inbox mình từ đó.

                              Hùng

                              Reply

Reply to Hùng Lê Cancel reply

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