+7

Quay lui (Phần 2)

III. Một số bài toán áp dụng giải thuật quay lui

Bây giờ, tôi sẽ giới thiệu tới các bạn một số bài toán ví dụ kinh điển về giải thuật quay lui. Hãy cùng nhau phân tích chúng và đối chiếu lại với phương pháp chung ở bài viết trước để hiểu rõ hơn về lý thuyết phương pháp nhé!

1. Bài toán xếp hậu

Đề bài

Một bàn cờ vua n×nn \times n đang để trống. Cần đặt nn quân hậu khác nhau vào bàn cờ vua sao cho không có hai quân hậu nào tấn công được nhau, biết rằng hai quân hậu sẽ tấn công nhau nếu như chúng đứng cùng hàng, cùng cột hoặc cùng đường chéo.

Input:

  • Chứa duy nhất số nguyên dương nn - kích thước bàn cờ.

Ràng buộc:

  • 1n81 \le n \le 8.

Output:

  • In ra tất cả các cách xếp nn quân hậu lên bàn cờ n×nn \times n.

Ý tưởng

Trong bài toán xếp hậu, nghiệm có thể được biểu diễn dưới dạng một vector {x1,x2,...,xn}\{x_1, x_2,..., x_n\} thỏa mãn ba điều kiện sau:

  • xix_i là tọa độ cột của quân hậu đang đứng ở dòng thứ i (1xin)i \ (1 \le x_i \le n).
  • Các quân hậu không được đứng cùng một cột, nghĩa là xixj,ijx_i \ne x_j, \forall i \ne j.
  • Hai quân hậu khác nhau không được nằm chung một đường chéo. Đường chéo ở đây có thể là các đường chéo chính (từ trên xuống dưới, từ trái qua phải) hoặc các đường chéo phụ (từ dưới lên trên, từ phải qua trái) (xem hình vẽ).
    Dễ nhận thấy, hai ô (x1,y1)(x_1, y_1) và (x2,y2)(x_2, y_2) sẽ nằm trên cùng đường chéo chính nếu như x1y1=x2y2,x_1 - y_1 = x_2 - y_2, và sẽ nằm trên cùng đường chéo phụ nếu như x1+y1=x2+y2x_1 + y_1 = x_2 + y_2. Vậy điều kiện để hai quân hậu xếp ở hai ô (i,xi)(i, x_i) và (j,xj)(j, x_j) không nằm cùng một đường chéo là:

    {ixijxj.i+xij+xj.\begin{cases}i - x_i \ne j - x_j. \\ i + x_i \ne j + x_j. \end{cases}

Vậy tựu chung lại, khi đã xây dựng được vector nghiệm {x1,x2,...,xi1},\{x_1, x_2,..., x_{i - 1}\}, thì xix_i tiếp theo được chọn phải thỏa mãn các điều kiện dưới đây:

{xixjjxjixjj+xji+xi;j:1ji1\begin{cases}x_i \ne x_j \\ j - x_j \ne i - x_j \\ j + x_j \ne i + x_i \end{cases}; \forall j: 1 \le j \le i - 1

Để xác định được tập SiS_i là các ứng cử viên cho thành phần xi,x_i, ta có thể thực hiện bằng cách sử dụng các mảng đánh dấu để chương trình trở nênn đơn giản hơn. Cụ thể, khi đặt một quân hậu jj vào ô (j,xj),(j, x_j), ta sẽ đánh dấu luôn cột xj,x_j, đường chéo chính có số hiệu jxjj - x_j và đường chéo phụ có số hiệu j+xj,j + x_j, thể hiện rằng trên cột này và các đường chéo này đã có một quân hậu.

Độ phức tạp của giải thuật sẽ là O(nn),O(n^n), do ta có nn thành phần cần sinh và mỗi thành phần lại có nn khả năng.

Cài đặt

Dưới đây là chương trình cài đặt bằng mô hình đệ quy.

#include <bits/stdc++.h>
#define task "XEPHAU."
#define inf 1e9 + 7

using namespace std;

const int maxn = 9;
int n, cnt, res[maxn], column[maxn], main_diagonal[maxn], secondary_diagonal[maxn];

// In nghiệm theo dạng: index. x1 x2 ... xn.
void printf_result()
{
    cout << ++cnt << ". ";
    
    for (int i = 1; i <= n; ++i)
        cout << res[i] << ' ';
        
    cout << endl;
}

// Kiểm tra xem đặt quân hậu ở hàng thứ i vào cột thứ j có được hay không?
bool check(int i, int j) 
{
    if (column[j] == 1 || main_diagonal[i - j] == 1 || secondary_diagonal[i + j] == 1)
        return false;
        
    return true;
}

// Tìm vị trí cột để đặt quân hậu trên hàng thứ i.
void backtrack(int i, int n)
{
    // Thử từng cột.
    for (int j = 1; j <= n; ++j)
        if (check(i, j)) 
        {
            res[i] = j;
            column[j] = 1;
            main_diagonal[i - j] = 1
            secondary_diagonal[i + j] = 1;
            
            // Nếu đã tạo được xong một vector nghiệm thì in nó ra.
            if (i == n)
                printf_result();
            // Ngược lại thì tiếp tục tạo thành phần thứ i + 1.
            else 
                backtrack(i + 1, n);
            
            // Xóa quân hậu ở cột j hàng i đi, khởi tạo lại cột và các đường chéo.
            column[j] = 0;
            main_diagonal[i - j] = 0;
            secondary_diagonal[i + j] = 0;
        }
}

int main()
{
    int n;
    cin >> n;
	
    backtrack(1, n);
	
    return 0;
}

2. Tổ hợp chập kk của nn

Đề bài

Cho một tập gồm nn số nguyên dương {1,2,3,...,n}\{1, 2, 3,..., n\}. Một tổ hợp chập kk của nn là một cách chọn ra kk phần tử bất kỳ trong tập hợp, các phần tử không được lặp lại và không quan trọng về thứ tự.

Hãy tìm tất cả các tổ hợp chập kk của n?n?

Input:

  • Một dòng duy nhất chứa hai số nguyên dương nn và kk.

Ràng buộc:

  • 1<n,k,101 < n, k, \le 10.

Output:

  • In ra tất cả các tổ hợp chập kk của n,n, mỗi tổ hợp trên một dòng theo cú pháp ở đầu ra mẫu.

Sample Input:

4 2

Sample Output:

1. 1 2
2. 1 3
3. 1 4
4. 2 3
5. 2 4
6. 3 4

Ý tưởng

Nghiệm của bài toán có thể được mô tả dưới dạng một tập các thành phần {x1,x2,...,xk}\{x_1, x_2,..., x_k\} thỏa mãn các điều kiện sau:

  • xix_i nhận giá trị trong tập {1,2,3,...,n}\{1, 2, 3,..., n\}.
  • Vì các tổ hợp không phân biệt nhau về thứ tự sắp xếp phần tử, nên để đơn giản hóa, ta sẽ ràng buộc xi<xi+1x_i < x_{i + 1} với mọi i=1,2,...,k1i = 1, 2,..., k - 1.
  • Nhận xét: 1x1<x2<<xkn,1 \le x_1 < x_2 < \cdots < x_k \le n, do đó tập SiS_i của thành phần xix_i chỉ bao gồm các giá trị từ xi1+1x_{i - 1} + 1 tới nk+in - k + i. Riêng trường hợp i=1,i = 1, ta sẽ coi như x0=0x_0 = 0.

Ta cần tạo ra kk thành phần của nghiệm, mỗi thành phần có thể có tối đa nn giá trị. Độ phức tạp của giải thuật sẽ rơi vào khoảng O(kn)O(k^n).

Cài đặt:

#include <bits/stdc++.h>
#define task "Tohop."
#define inf 1e9 + 7

using namespace std;

const int maxn = 11;
int n, k, cnt, x[maxn];

void enter()
{
    cin >> n >> k;
}

void result()
{
    cout << ++cnt << ". ";
    for (int i = 1; i <= k; ++i)
        cout << x[i] << ' ';
    cout << endl;
}

void backtrack(int i)
{
    for (int j = x[i - 1] + 1; j <= n - k + i; ++j)
    {
        x[i] = j;
        
        if (i == k) 
            print_result();
        else 
            backtrack(i + 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    enter();
    back_track(1);
    
    return 0;
}

3. Chỉnh hợp không lặp chập kk của nn

Đề bài

Cho hai số nguyên nnkk. Một chỉnh hợp không lặp chập kk của nn là một cách chọn ra kk phần tử trong nn và có xét tới tính thứ tự.

Yêu cầu: Hãy liệt kê ra các chỉnh hợp không lặp chập kk của nn phần tử 1,2,,n1, 2, \dots, n theo thứ tự từ điển?

Input:

  • Dòng duy nhất chứa hai số nguyên nnkk.

Ràng buộc:

  • 1kn101 \le k \le n \le 10.

Output:

  • Các chỉnh hợp chập kk của nn phần tử 1,2,,n;1, 2, \dots, n; mỗi chỉnh hợp in ra trên một dòng theo thứ tự từ điển.

Sample Input 1:

2 2

Sample Output 1:

1 2
2 1

Sample Input 2:

3 2

Sample Output 2:

1 2
1 3
2 1
2 3
3 1
3 2

Ý tưởng

Dễ thấy, nghiệm của bài toán vẫn có thể đưa về biểu diễn dưới dạng một tập các thành phần {x1,x2,...,xk}\{x_1, x_2,..., x_k\} thỏa mãn các điều kiện sau:

  • xix_i nhận giá trị trong tập {1,2,3,...,n}\{1, 2, 3,..., n\}.
  • xixj;ijx_i \ne x_j; \forall i \ne j.

Do chỉnh hợp khác với tổ hợp ở chỗ mỗi chỉnh hợp đều xét tới tính thứ tự, nên ta sẽ không cần ràng buộc xi<xi+1x_i < x_{i + 1} như đối với tổ hợp. Tuy nhiên, để đảm bảo các phần tử trong mỗi chỉnh hợp đều phân biệt, ta sẽ cần sử dụng một mảng used[v]\text{used}[v] để đánh dấu giá trị vv đã được lựa chọn hay chưa.

Độ phức tạp giải thuật là O(nk),O(n^k), do mỗi thành phần ta vẫn phải thử chọn trong nn giá trị.

Cài đặt

#include <iostream>

using namespace std;

bool used[11];
int s[11];
int n, k;

void back_track(int i)
{
    // Nếu đã sinh đủ k thành phần thì dừng.
    if (i > k)
    {
        for (int j = 1; j <= k; ++j)
            cout << s[j] << ' ';
        cout << '\n';

        return;
    }

    // Bắt đầu sinh các cấu hình.
    for (int v = 1; v <= n; ++v) 
    {
        // Nếu giá trị v chưa được sử dụng thì chọn nó.
        if (!used[v]) 
        {
            s[i] = v; 
            used[v] = true;

            back_track(i + 1); 

            used[v] = false; // Trả đệ quy.
        }   
    }
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    back_track(1);

    return 0;
}

4. Cây ATM

Đề bài

Một khách hàng muốn rút số tiền TT từ một cây ATM bên đường. Bên trong cây ATM hiện đang có nn tờ tiền có mệnh giá a1,a2,,ana_1, a_2,…, a_n.

Hãy tìm một cách trả tiền của máy ATM cho khách hàng?

Input:

  • Dòng đầu tiên chứa hai số nguyên dương nn và TT - số lượng tờ tiền hiện có và số tiền cần trả.
  • Dòng thứ hai chứa nn số nguyên dương a1,a2,,ana_1, a_2, \dots, a_n phân tách nhau bởi dấu cách - mệnh giá các tờ tiền.

Ràng buộc:

  • 1T10001 \le T \le 1000.
  • 1n201 \le n \le 20.
  • 1ai200;i:1in1 \le a_i \le 200; \forall i: 1 \le i \le n.

Output:

  • In ra danh sách các tờ tiền được sử dụng. Nếu không tồn tại cách trả tiền thì đưa ra 1-1.

Sample Input:

10 390
200 10 20 20 50 50 50 100 100

Sample Output:

20 20 50 50 50 100 100

Ý tưởng

Ta biểu diễn nghiệm của bài toán dưới dạng một dãy nhị phân 01,0 - 1, trong đó bit thứ ii bằng 11 nếu tờ tiền thứ ii được sử dụng để trả tiền, bằng 00 trong trường hợp ngược lại.

Tập {x1,x2,...,xn}\{x_1, x_2,..., x_n\} là nghiệm nếu:

{0xi1;i:1in.x1×a1+x2×a2++xn×an=T.\begin{cases}0 \le x_i \le 1; \forall i: 1 \le i \le n. \\ x_1 \times a_1 + x_2 \times a_2 + \cdots + x_n \times a_n = T.\end{cases}

Độ phức tạp của giải thuật là O(2n),O(2^n), do mỗi thành phần xix_i có thể ở một trong hai trường hợp 00 hoặc 11.

Cài đặt

#include <bits/stdc++.h>
#define task "ATM."

using namespace std;

const int maxn = 21;
int n, T, sum, a[maxn], mark[maxn];

void enter()
{
    cin >> n >> T;
	
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

void check()
{
    // Nếu đã tìm thấy nghiệm thì in ra nghiệm và dừng luôn toàn bộ chương trình.
    if (sum == T)
    {
        for (int i = 1; i <= n; ++i)
            if (mark[i])
                cout << a[i] << ' ';

        exit(0);
    }
}

// Thử chọn giá trị 0 - 1 cho thành phần thứ i.
void backtrack(int i)
{
    for (int j = 0; j <= 1; ++j)
    {
        mark[i] = j;
        sum = sum + a[i] * mark[i];
		
        if (i == n) 
            check();
        else 
            create(i + 1);
			
        sum -= a[i] * mark[i];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    enter();
    backtrack(1);
	
    // Trường hợp không tìm thấy nghiệm thì in ra -1.
    cout << -1;
	
    return 0;
}

5. Hành trình của quân mã

Đề bài

Trên bàn cờ vua 8×8,8 \times 8, mỗi bên sở hữu hai quân mã (knights). Cách di chuyển của quân mã trên bàn cờ giống hình chữ L, được mô tả theo như hình vẽ dưới đây:

Mở rộng bài toán một chút, xét bàn cờ vua kích thước n×nn \times n với các hàng được đánh số từ 11 tới nn từ trên xuống dưới, các cột được đánh số từ 11 tới nn từ trái qua phải.

Hãy tìm một hành trình cho quân mã di chuyển từ ô (1,1),(1, 1), đi qua tất cả các ô trên bàn cờ, mỗi ô đúng một lần?

Input:

  • Chứa duy nhất số nguyên dương nn.

Ràng buộc:

  • 1n101 \le n \le 10.

Output:

  • In ra một ma trận n×nn \times n với số trên từng ô thể hiện thứ tự bước đi của quân mã khi tới ô đó. Nếu không tìm được phương án di chuyển thì in ra 1-1.

Sample Input:

5

Sample Output:

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

Ý tưởng

Tổng số bước đi cần sử dụng là n×n,n \times n, nhưng các bước đi này lại ở trên một ma trận có hàng cột. Vì vậy, vector nghiệm của bài toán sẽ ở dạng một tập các tọa độ hàng cột: {(x1,y1),(x2,y2),...,(xn×n,yn×n)}\big\{(x_1, y_1), (x_2, y_2),..., (x_{n \times n}, y_{n \times n})\big\} thỏa mãn các điều kiện sau:

  • 1xi,yin1 \le x_i, y_i \le n.
  • Các bước đi của quân mã có hình chữ L, tức là:

    1xixi1,yiyi12;i:2in×n.1 \le |x_i - x_{i - 1}|, |y_i - y_{i - 1}| \le 2; \forall i: 2 \le i \le n \times n.

  • Giả sử đã tạo được dãy bước đi {(x1,y1),(x2,y2),...,(xi,yi)},\big\{(x_1, y_1), (x_2, y_2),..., (x_i, y_i)\big\}, thì khi tiếp tục chọn ô (xi,yi)(x_i, y_i) cần thỏa mãn: (xi,yi)(xj,yj);j:1j<i(x_i, y_i) \ne (x_j, y_j); \forall j: 1 \le j < i.
  • x1=1,y1=1x_1 = 1, y_1 = 1.

Để cho đơn giản, chúng ta có thể biểu diễn nghiệm của bài toán bằng một ma trận visited[x][y],\text{visited}[x][y], mỗi ô sẽ lưu một số nguyên dương là số thứ tự bước đi của quân mã khi tới ô đó. Khởi đầu từ ô (1,1),(1, 1), thử tất cả các trường hợp có thể di chuyển đến trên bàn cờ từ một ô (x,y)(x, y) bất kỳ và đánh dấu lại số thứ tự của bước đi trên vị trí visited[x][y]\text{visited}[x][y]. Các bạn cần sử dụng thêm một biến step_used\text{step\_used} để kiểm soát số bước đi đã thực hiện được, nếu như nó bằng n×nn \times n nghĩa là bài toán đã có nghiệm, lúc đó chỉ cần in ra ma trận visited\text{visited} là biết cách đi của quân mã.

Ta có tổng cộng n×nn \times n thành phần cần sinh, mà mỗi thành phần lại có thể có 88 khả năng di chuyển, vậy độ phức tạp của giải thuật trong trường hợp tệ nhất là O(8n2)O(8^{n^2}).

Trong code dưới đây, tôi sử dụng thêm một mảng step[8][2]step[8][2] để mô tả các phương án di chuyển tới 88 hướng của một quân mã. Dùng mảng này sẽ thuận tiện hơn để xét các hướng đi. Kết thúc quá trình quay lui, nếu không có phương án nào được in ra thì kết quả sẽ là 1-1.

Cài đặt

#include <bits/stdc++.h>
#define task "Madituan."

using namespace std;

const int step[8][2] = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, 
                        {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};
const int maxn = 10;
int n, step_used = 1, visited[maxn][maxn];

// In ra bảng kết quả nếu đã có kết quả.
void printf_result(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
            cout << visited[i][j] << ' ';
            
        cout << endl;
    }
}

// Kiểm tra xem ô (next_x, next_y) có thể chọn làm bước đi tiếp theo không.
bool check_valid(int next_x, int next_y)
{
    return (next_x > 0 && next_y > 0 && next_x <= n && next_y <= n 
            && !visited[next_x][next_y]);
}

// Thử các cách đi cho quân mã.
void backtrack(int n, int x, int y)
{
    visited[x][y] = step_used;
    
    if (step_used == n * n)
    {
        printf_result(n);
        exit(0);
    }
    
    for (int i = 0; i <= 7; ++i)
    {
        int next_x = x + step[i][0], next_y = y + step[i][1];
        if (check_valid(next_x, next_y))
        {
            ++step_used;
            
            backtrack(next_x, next_y);
            
            visited[next_x][next_y] = 0;
            --step_used;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    if (n == 1)
    {
        cout << -1;
        return 0;
    }
    
    backtrack(n, 1, 1);
    
    cout << -1;
    
    return 0;
}

IV. Nhận xét về phương pháp

Nhìn chung, quay lui là một phương pháp chạy khá chậm, do nó phải xét hết mọi trường hợp có thể của kết quả và tìm ra đáp án đúng. Tuy nhiên, lợi thế của phương pháp này là kết quả luôn luôn chính xác 100%100\%. Ngoài ra, từ phương pháp quay lui, người ta có thể cài đặt được những cải tiến như Nhánh và cận để loại bỏ bớt các trường hợp không cần thiết, giảm độ phức tạp tính toán.

Tuy nhiên, phần lớn các bài toán sử dụng giải thuật quay lui đều sẽ cho ra độ phức tạp cấp số mũ. Do đó, nó vẫn có những nhược điểm như sau:

  • Rơi vào tình trạng "thrashing": Quá trình tìm kiếm có thể gặp phải bế tắc với cùng một nguyên nhân.
  • Thực hiện các công việc dư thừa: Mỗi lần chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
  • Không sớm phát hiện được các khả năng kết quả bị sai trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết đc nhánh tìm kiếm sẽ đi vào lặp vô hạn hoặc kết quả sai.

Vì những điều trên, giải thuật quay lui thường chỉ phù hợp với những bài toán có kích thước nhỏ, đặc biệt là trong lập trình thi đấu.

V. Tài liệu tham khảo


©️ Tác giả: Vũ Quế Lâm từ Viblo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.