8.9K 674 107

Đã đăng vào thg 7 4, 2023 6:55 SA 13 phút đọc

1.1K

Quay lui (Phần 2)

III. Một số bài toán áp dụng giải thuật quay lui

Bây giờ, tôi sẽ giới thiệu tới các bạn một số bài toán ví dụ kinh điển về giải thuật quay lui. Hãy cùng nhau phân tích chúng và đối chiếu lại với phương pháp chung ở bài viết trước để hiểu rõ hơn về lý thuyết phương pháp nhé!

1. Bài toán xếp hậu

Đề bài

Một bàn cờ vua $n \times n$ đang để trống. Cần đặt $n$ quân hậu khác nhau vào bàn cờ vua sao cho không có hai quân hậu nào tấn công được nhau, biết rằng hai quân hậu sẽ tấn công nhau nếu như chúng đứng cùng hàng, cùng cột hoặc cùng đường chéo.

Input:

Chứa duy nhất số nguyên dương $n$ - kích thước bàn cờ.

Ràng buộc:

$1 \le n \le 8$ .

Output:

In ra tất cả các cách xếp $n$ quân hậu lên bàn cờ $n \times n$ .

Ý tưởng

Trong bài toán xếp hậu, nghiệm có thể được biểu diễn dưới dạng một vector $\{x_1, x_2,..., x_n\}$ thỏa mãn ba điều kiện sau:

$x_i$ là tọa độ cột của quân hậu đang đứng ở dòng thứ $i \ (1 \le x_i \le n)$ .
Các quân hậu không được đứng cùng một cột, nghĩa là $x_i \ne x_j, \forall i \ne j$ .
Hai quân hậu khác nhau không được nằm chung một đường chéo. Đường chéo ở đây có thể là các đường chéo chính (từ trên xuống dưới, từ trái qua phải) hoặc các đường chéo phụ (từ dưới lên trên, từ phải qua trái) (xem hình vẽ).
Dễ nhận thấy, hai ô $(x_1, y_1)$ và $(x_2, y_2)$ sẽ nằm trên cùng đường chéo chính nếu như $x_1 - y_1 = x_2 - y_2,$ và sẽ nằm trên cùng đường chéo phụ nếu như $x_1 + y_1 = x_2 + y_2$ . Vậy điều kiện để hai quân hậu xếp ở hai ô $(i, x_i)$ và $(j, x_j)$ không nằm cùng một đường chéo là:
$\begin{cases}i - x_i \ne j - x_j. \\ i + x_i \ne j + x_j. \end{cases}$

Vậy tựu chung lại, khi đã xây dựng được vector nghiệm $\{x_1, x_2,..., x_{i - 1}\},$ thì $x_i$ tiếp theo được chọn phải thỏa mãn các điều kiện dưới đây:

$\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$

Để xác định được tập $S_i$ là các ứng cử viên cho thành phần $x_i,$ ta có thể thực hiện bằng cách sử dụng các mảng đánh dấu để chương trình trở nênn đơn giản hơn. Cụ thể, khi đặt một quân hậu $j$ vào ô $(j, x_j),$ ta sẽ đánh dấu luôn cột $x_j,$ đường chéo chính có số hiệu $j - x_j$ và đường chéo phụ có số hiệu $j + x_j,$ thể hiện rằng trên cột này và các đường chéo này đã có một quân hậu.

Độ phức tạp của giải thuật sẽ là $O(n^n),$ do ta có $n$ thành phần cần sinh và mỗi thành phần lại có $n$ khả năng.

Cài đặt

Dưới đây là chương trình cài đặt bằng mô hì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 dạ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 ở hàng thứ i vào cột thứ j có đượ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;
}

// Tìm vị trí cột để đặt quân hậu trên hà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 đã tạo được xong một vector nghiệm thì in nó ra.
            if (i == n)
                printf_result();
            // Ngược lại thì tiếp tục tạo thành phần thứ i + 1.
            else 
                backtrack(i + 1, n);
            
            // Xóa quân hậu ở cột j hàng i đi, khởi tạo lại cột và các đường ché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 $k$ của $n$

Đề bài

Cho một tập gồm $n$ số nguyên dương $\{1, 2, 3,..., n\}$ . Một tổ hợp chập $k$ của $n$ là một cách chọn ra $k$ phần tử bất kỳ trong tập hợp, các phần tử không được lặp lại và không quan trọng về thứ tự.

Hãy tìm tất cả các tổ hợp chập $k$ của $n?$

Input:

Một dòng duy nhất chứa hai số nguyên dương $n$ và $k$ .

Ràng buộc:

$1 < n, k, \le 10$ .

Output:

In ra tất cả các tổ hợp chập $k$ của $n,$ mỗi tổ hợp trên một dòng theo cú pháp ở đầu ra mẫu.

Sample Input:

4 2

Sample Output:

Ý tưởng

Nghiệm của bài toán có thể được mô tả dưới dạng một tập các thành phần $\{x_1, x_2,..., x_k\}$ thỏa mãn các điều kiện sau:

$x_i$ nhận giá trị trong tập $\{1, 2, 3,..., n\}$ .
Vì các tổ hợp không phân biệt nhau về thứ tự sắp xếp phần tử, nên để đơn giản hóa, ta sẽ ràng buộc $x_i < x_{i + 1}$ với mọi $i = 1, 2,..., k - 1$ .
Nhận xét: $1 \le x_1 < x_2 < \cdots < x_k \le n,$ do đó tập $S_i$ của thành phần $x_i$ chỉ bao gồm các giá trị từ $x_{i - 1} + 1$ tới $n - k + i$ . Riêng trường hợp $i = 1,$ ta sẽ coi như $x_0 = 0$ .

Ta cần tạo ra $k$ thành phần của nghiệm, mỗi thành phần có thể có tối đa $n$ giá trị. Độ phức tạp của giải thuật sẽ rơi vào khoảng $O(k^n)$ .

Cà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 $k$ của $n$

Đề bài

Cho hai số nguyên $n$ và $k$ . Một chỉnh hợp không lặp chập $k$ của $n$ là một cách chọn ra $k$ phần tử trong $n$ và có xét tới tí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 $k$ của $n$ phần tử $1, 2, \dots, n$ theo thứ tự từ điển?

Input:

Dòng duy nhất chứa hai số nguyên $n$ và $k$ .

Ràng buộc:

$1 \le k \le n \le 10$ .

Output:

Các chỉnh hợp chập $k$ của $n$ phần tử $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:

Ý 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 các thành phần $\{x_1, x_2,..., x_k\}$ thỏa mãn các điều kiện sau:

$x_i$ nhận giá trị trong tập $\{1, 2, 3,..., n\}$ .
$x_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 $x_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 $\text{used}[v]$ để đánh dấu giá trị $v$ đã được lựa chọn hay chưa.

Độ phức tạp giải thuật là $O(n^k),$ do mỗi thành phần ta vẫn phải thử chọn trong $n$ 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

Đề bài

Một khách hàng muốn rút số tiền $T$ từ một cây ATM bên đường. Bên trong cây ATM hiện đang có $n$ tờ tiền có mệnh giá $a_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:

Dòng đầu tiên chứa hai số nguyên dương $n$ và $T$ - số lượng tờ tiền hiện có và số tiền cần trả.
Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách - mệnh giá các tờ tiền.

Ràng buộc:

$1 \le T \le 1000$ .
$1 \le n \le 20$ .
$1 \le a_i \le 200; \forall i: 1 \le i \le n$ .

Output:

In ra danh sách các tờ tiền được sử dụng. Nếu không tồn tại cách trả tiền thì đưa ra $-1$ .

Sample Input:

10 390
200 10 20 20 50 50 50 100 100

Sample Output:

20 20 50 50 50 100 100

Ý tưởng

Ta biểu diễn nghiệm của bài toán dưới dạng một dãy nhị phân $0 - 1,$ trong đó bit thứ $i$ bằng $1$ nếu tờ tiền thứ $i$ được sử dụng để trả tiền, bằng $0$ trong trường hợp ngược lại.

Tập $\{x_1, x_2,..., x_n\}$ là nghiệm nếu:

$\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 tạp của giải thuật là $O(2^n),$ do mỗi thành phần $x_i$ có thể ở một trong hai trường hợp $0$ hoặc $1$ .

Cà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 đã tìm thấy nghiệm thì in ra nghiệm và dừng luôn toàn bộ chương trình.
    if (sum == T)
    {
        for (int i = 1; i <= n; ++i)
            if (mark[i])
                cout << a[i] << ' ';

        exit(0);
    }
}

// Thử chọn giá trị 0 - 1 cho thà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 tìm thấy nghiệm thì in ra -1.
    cout << -1;
	
    return 0;
}

5. Hành trình của quân mã

Đề bài

Trên bàn cờ vua $8 \times 8,$ mỗi bên sở hữu hai quân mã (knights). Cách di chuyển của quân mã trên bàn cờ giống hình chữ L, được mô tả theo như hình vẽ dưới đây:

Mở rộng bài toán một chút, xét bàn cờ vua kích thước $n \times n$ với các hàng được đánh số từ $1$ tới $n$ từ trên xuống dưới, các cột được đánh số từ $1$ tới $n$ từ trái qua phải.

Hãy tìm một hành trình cho quân mã di chuyển từ ô $(1, 1),$ đi qua tất cả các ô trên bàn cờ, mỗi ô đúng một lần?

Input:

Chứa duy nhất số nguyên dương $n$ .

Ràng buộc:

$1 \le n \le 10$ .

Output:

In ra một ma trận $n \times n$ với số trên từng ô thể hiện thứ tự bước đi của quân mã khi tới ô đó. Nếu không tìm được phương án di chuyển thì in ra $-1$ .

Sample Input:

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

Ý tưởng

Tổng số bước đi cần sử dụng là $n \times n,$ nhưng các bước đi này lại ở trên một ma trận có hàng cột. Vì vậy, vector nghiệm của bài toán sẽ ở dạng một tập các tọa độ hàng cột: $\big\{(x_1, y_1), (x_2, y_2),..., (x_{n \times n}, y_{n \times n})\big\}$ thỏa mãn các điều kiện sau:

$1 \le x_i, y_i \le n$ .
Các bước đi của quân mã có hình chữ L, tức là:
$1 \le |x_i - x_{i - 1}|, |y_i - y_{i - 1}| \le 2; \forall i: 2 \le i \le n \times n.$
Giả sử đã tạo được dãy bước đi $\big\{(x_1, y_1), (x_2, y_2),..., (x_i, y_i)\big\},$ thì khi tiếp tục chọn ô $(x_i, y_i)$ cần thỏa mãn: $(x_i, y_i) \ne (x_j, y_j); \forall j: 1 \le j < i$ .
$x_1 = 1, y_1 = 1$ .

Để cho đơn giản, chúng ta có thể biểu diễn nghiệm của bài toán bằng một ma trận $\text{visited}[x][y],$ mỗi ô sẽ lưu một số nguyên dương là số thứ tự bước đi của quân mã khi tới ô đó. Khởi đầu từ ô $(1, 1),$ thử tất cả các trường hợp có thể di chuyển đến trên bàn cờ từ một ô $(x, y)$ bất kỳ và đánh dấu lại số thứ tự của bước đi trên vị trí $\text{visited}[x][y]$ . Các bạn cần sử dụng thêm một biến $\text{step\_used}$ để kiểm soát số bước đi đã thực hiện được, nếu như nó bằng $n \times n$ nghĩa là bài toán đã có nghiệm, lúc đó chỉ cần in ra ma trận $\text{visited}$ là biết cách đi của quân mã.

Ta có tổng cộng $n \times n$ thành phần cần sinh, mà mỗi thành phần lại có thể có $8$ khả năng di chuyển, vậy độ phức tạp của giải thuật trong trường hợp tệ nhất là $O(8^{n^2})$ .

Trong code dưới đây, tôi sử dụng thêm một mảng $step[8][2]$ để mô tả các phương án di chuyển tới $8$ hướng của một quân mã. Dùng mảng này sẽ thuận tiện hơn để xét các hướng đi. Kết thúc quá trình quay lui, nếu không có phương án nào được in ra thì kết quả sẽ là $-1$ .

Cà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 bảng kết quả nếu đã có kết quả.
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) có thể chọn là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ử các cách đi cho quân mã.
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 xét về phương pháp

Nhìn chung, quay lui là một phương pháp chạy khá chậm, do nó phải xét hết mọi trường hợp có thể của kết quả và tìm ra đáp án đúng. Tuy nhiên, lợi thế của phương pháp này là kết quả luôn luôn chính xác $100\%$ . Ngoài ra, từ phương pháp quay lui, người ta có thể cài đặt được những cải tiến như Nhánh và cận để loại bỏ bớt các trường hợp không cần thiết, giảm độ phức tạp tính toán.

Tuy nhiên, phần lớn các bài toán sử dụng giải thuật quay lui đều sẽ cho ra độ phức tạp cấp số mũ. Do đó, nó vẫn có những nhược điểm như sau:

Rơi vào tình trạng "thrashing": Quá trình tìm kiếm có 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 quả bị 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ô hạn hoặc kết quả sai.

Vì những điều trên, giải thuật quay lui thường chỉ phù hợp với những bài toán có kích thước nhỏ, đặc biệt là trong lập trình thi đấu.

V. Tài liệu tham khảo

III. Một số bài toán áp dụng giải thuật quay lui

1. Bài toán xếp hậu

Đề bài

Ý tưởng

Cài đặt

2. Tổ hợp chập kkk của nnn

Đề bài

Ý tưởng

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

Đề bài

Ý tưởng

Cài đặt

4. Cây ATM

Đề bài

Ý tưởng

Cài đặt

5. Hành trình của quân mã

Đề bài

Ý tưởng

Cài đặt

IV. Nhận xét về phương pháp

V. Tài liệu tham khảo

Mục lục

2. Tổ hợp chập $k$ của $n$

3. Chỉnh hợp không lặp chập $k$ của $n$