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 đang để trống. Cần đặt 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 - kích thước bàn cờ.
Ràng buộc:
- .
Output:
- In ra tất cả các cách xếp quân hậu lên bàn cờ .
Ý 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 thỏa mãn ba điều kiện sau:
- là tọa độ cột của quân hậu đang đứng ở dòng thứ .
- Các quân hậu không được đứng cùng một cột, nghĩa là .
- 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 ô và sẽ nằm trên cùng đường chéo chính nếu như và sẽ nằm trên cùng đường chéo phụ nếu như . Vậy điều kiện để hai quân hậu xếp ở hai ô và không nằm cùng một đường chéo là:
Vậy tựu chung lại, khi đã xây dựng được vector nghiệm thì tiếp theo được chọn phải thỏa mãn các điều kiện dưới đây:
Để xác định được tập là các ứng cử viên cho thành phần 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 vào ô ta sẽ đánh dấu luôn cột đường chéo chính có số hiệu và đường chéo phụ có số hiệu 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à do ta có thành phần cần sinh và mỗi thành phần lại có 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 của
Đề bài
Cho một tập gồm số nguyên dương . Một tổ hợp chập của là một cách chọn ra 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 của
Input:
- Một dòng duy nhất chứa hai số nguyên dương và .
Ràng buộc:
- .
Output:
- In ra tất cả các tổ hợp chập của 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 thỏa mãn các điều kiện sau:
- nhận giá trị trong tập .
- 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 với mọi .
- Nhận xét: do đó tập của thành phần chỉ bao gồm các giá trị từ tới . Riêng trường hợp ta sẽ coi như .
Ta cần tạo ra thành phần của nghiệm, mỗi thành phần có thể có tối đa giá trị. Độ phức tạp của giải thuật sẽ rơi vào khoảng .
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 của
Đề bài
Cho hai số nguyên và . Một chỉnh hợp không lặp chập của là một cách chọn ra phần tử trong 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 của phần tử theo thứ tự từ điển?
Input:
- Dòng duy nhất chứa hai số nguyên và .
Ràng buộc:
- .
Output:
- Các chỉnh hợp chập của phần tử 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 thỏa mãn các điều kiện sau:
- nhận giá trị trong tập .
- .
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 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 để đánh dấu giá trị đã được lựa chọn hay chưa.
Độ phức tạp giải thuật là do mỗi thành phần ta vẫn phải thử chọn trong 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 từ một cây ATM bên đường. Bên trong cây ATM hiện đang có tờ tiền có mệnh giá .
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 và - số lượng tờ tiền hiện có và số tiền cần trả.
- Dòng thứ hai chứa số nguyên dương phân tách nhau bởi dấu cách - mệnh giá các tờ tiền.
Ràng buộc:
- .
- .
- .
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 .
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 trong đó bit thứ bằng nếu tờ tiền thứ được sử dụng để trả tiền, bằng trong trường hợp ngược lại.
Tập là nghiệm nếu:
Độ phức tạp của giải thuật là do mỗi thành phần có thể ở một trong hai trường hợp hoặc .
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 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 với các hàng được đánh số từ tới từ trên xuống dưới, các cột được đánh số từ tới từ trái qua phải.
Hãy tìm một hành trình cho quân mã di chuyển từ ô đ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 .
Ràng buộc:
- .
Output:
- In ra một ma trậ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 .
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à 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: thỏa mãn các điều kiện sau:
- .
- Các bước đi của quân mã có hình chữ
L
, tức là: - Giả sử đã tạo được dãy bước đi thì khi tiếp tục chọn ô cần thỏa mãn: .
- .
Để 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 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ừ ô thử tất cả các trường hợp có thể di chuyển đến trên bàn cờ từ một ô bất kỳ và đánh dấu lại số thứ tự của bước đi trên vị trí . Các bạn cần sử dụng thêm một biến để kiểm soát số bước đi đã thực hiện được, nếu như nó bằng nghĩa là bài toán đã có nghiệm, lúc đó chỉ cần in ra ma trận là biết cách đi của quân mã.
Ta có tổng cộng thành phần cần sinh, mà mỗi thành phần lại có thể có 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à .
Trong code dưới đây, tôi sử dụng thêm một mảng để mô tả các phương án di chuyển tới 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à .
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 . 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
- https://vi.wikipedia.org/wiki/Quay_lui_(khoa_học_máy_tính)
- https://www.geeksforgeeks.org/backtracking-algorithms/?ref=ghm#
- Sách Giải thuật và Lập trình - thầy Lê Minh Hoàng.
- Tài liệu giáo khoa chuyên Tin quyển 1 - thầy Hồ Sĩ Đàm.
©️ Tác giả: Vũ Quế Lâm từ Viblo
All Rights Reserved