Backtrack – duyệt – quay lui cho người mới bắt đầu (Phần 1): Sinh nhị phân, sinh hoán vị

Mục lục

1. Tư tưởng Backtrack

Backtrack là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của Backtrack 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. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

Backtrack dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Các bước trong việc liệt kê cấu hình dạng \(X = x_1, x_2 ,…, x_n\)

Xét tất cả các giá trị \(x_1\) có thể nhận, thử \(x_1\) nhận các giá trị đó. Với mỗi giá trị của \(x_1\)
Xét tất cả giá trị \(x_2\) có thể nhận, lại thử \(x_2\) cho các giá trị đó. Với mỗi giá trị \(x_2\) lại xét khả năng giá trị của \(x_3\)…tiếp tục như vậy cho tới bước \(n\):
…
….
Xét tất cả giá trị \(x_n\) có thể nhận, thử cho \(x_n\) nhận lần lượt giá trị đó.
Thông báo cấu hình tìm được.

Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu (Depth-First Search).

Mã giả thuật toán quay lui

void backtracking(i) {
  if(i > n){
    if (nghiemThoaMan()) {
      print(X);
    }
    return;
  } 
  for(j in D) {
    if (check(j, i)) { //Có thể đặt giá trị j vào vị trí i 
      X[i] = j; //Đặt j
      backtracking(i+1);
      X[i] = 0; //Bỏ chọn j 
    }
  } 
}

2. Bài toán liệt kê các xâu nhị phân độ dài n

Phát biểu bài toán

Cho số \(n\). Liệt kê các xâu nhị phân độ dài \(n\) \((1 ≤ n ≤ 20)\) mà không có hai số 1 liền nhau theo thứ tự từ điển.
Ví dụ: \(n = 3\) ta có các xâu nhị phân độ dài \(3\) mà không có hai số \(1\) liền nhau như sau:

Phân tích bài toán

Bài toán yêu cầu xây dựng vector nghiệm có \(n\) phần tử, dạng: \(X = x_1, x_2,…, x_n \)
Trong đó

\(0≤x_i ≤1\)
\(x_i ∗ x_{i−1} = 0\)

Code bài toán duyệt nhị phân bằng C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define MAXN 21
int n;
int x[MAXN];

//Hàm kiểm tra nghiệm X có thỏa mãn không xuất hiện 2 số 1 liền nhau hay không?
bool check(){
    for(int i = 2; i <= n; i++)
        if(x[i]*x[i-1] == 1) return false;
    return true;
}

//Hàm in nghiệm X 
void printX(){
    for(int i = 1; i <= n; i++)
        cout<<x[i];
    cout<<endl;
}
//Hàm quay lui
void backtrack(int i){
  //Nếu i>n => đã điền xong các giá trị của vector nghiệm X 
  if(i>n){
    //Nếu nghiệm X thỏa mãn yêu cầu đề bài thì in ra màn hình 
    if (check()){
      printX(); 
    }
    return; 
  }
  //Thử các giá trị có thể đặt được của x[i] 
  for(int j = 0; j <= 1; j++){
    x[i] = j;
    //Đặt xong vị trí i thì gọi hàm quay lui để đặt vị trí i + 1 
    backtrack(i + 1);
  } 
}
 
int main() { 
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);
  cin>>n;
  //Xây dựng nghiệm bắt đầu từ vị trí 1 
  backtrack(1);
  return 0;
}

Mô tả thuật toán khi chạy

Cải tiến thuật toán

Để cải tiến thuật toán duyệt, ta có thể đặt cận để cắt bớt 1 số nhánh mà biết chắc nếu đi sâu xuống cũng không có kết quả. Kỹ thuật này được gọi là duyệt nhánh cận
Như bài toán trên, ngay trong hàm đệ quy, trước khi đặt giá trị \(x_i\) bất kì, ta kiểm tra xem \(x_{i-1} * x_i\) có bằng \(0\) hay không trước. Nếu \(x_{i-1} * x_i = 0\) thì ta sẽ gọi \(backtrack(i+1)\) còn nếu không thì dù xây dựng tiếp hết dãy \(X\) thì kiểu gì nghiệm này cũng sẽ không được chấp nhận.

Code bài toán duyệt nhị phân cải tiến

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define MAXN 21
int n;
int x[MAXN];

//Hàm in nghiệm X 
void printX(){
    for(int i = 1; i <= n; i++)
        cout<<x[i];
    cout<<endl;
}
//Hàm quay lui
void backtrack(int i){
  //Nếu i>n => đã điền xong các giá trị của vector nghiệm X 
  if(i>n){
    //nghiệm X chắc chắn thỏa mãn yêu cầu đề bài nên chỉ cần in ra màn hình 
    printX(); 
    return; 
  }
  //Thử các giá trị có thể đặt được của x[k] 
  for(int j = 0; j <= 1; j++)
    if(x[i-1] * j == 0){
    x[i] = j;
    //Đặt xong vị trí i thì gọi hàm quay lui để đặt vị trí i+1 
    backtrack(i+1);
  } 
}
 
int main() { 
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);
  cin>>n;
  //Xây dựng nghiệm bắt đầu từ vị trí 1 
  backtrack(1);
  return 0;
}

Mô tả thuật toán duyệt cải tiến khi chạy

Kết luận

Bài toán trên các vector nghiệm \(X\) được sắp xếp theo thứ tự từ điển là do trong hàm backtrack, ta xét các trường hợp có thể đặt được cho mỗi phần tử \(x_k\) theo thứ tự từ điển, đặt thử 0 trước, đặt thử 1 sau.

Thuật toán duyệt nhị phân có độ phức tạp \(O(a^n* n)\)
Trong đó: \(a\) là số lượng giá trị mà một phần tử \(x_i\) có thể nhận, \(n\) là độ dài vector nghiệm \(X\)

Lý do: thuật toán duyệt liệt kê tất cả các nghiệm có thể có của bài toán. Do có \(n\) phần tử, mỗi phần tử có \(a\) cách đặt. Vậy số lượng vector nghiệm tạo được bằng \(a_n\). Mặt khác, mỗi một vector nghiệm tạo ra ta mất \(n\) phép toán để kiểm tra xem nghiệm đó có thỏa mãn hay không. Thuật toán duyệt nhị phân có độ phức tạp \(O(a^n * n)\)

Thuật toán duyệt nhị phân cải tiến có độ phức tạp \(O(a^n)\)

Lý do: thuật toán duyệt liệt kê tất cả các nghiệm có thể có của bài toán là \(a_n\). Tuy nhiên, các nghiệm được kiểm soát từ trong hàm backtrack để đảm bảo chắc chắn tạo ra nghiệm đúng nên ta không mất \(n\) phép toán để kiểm tra nữa.

3. Bài toán liệt kê các hoán vị độ dài n

Phát biểu bài toán

Cho số \(n\). Liệt kê các hoán vị độ dài \(n\) \((1 ≤ n ≤ 10)\) theo thứ tự từ điển.
Ví dụ: \(n = 3\) ta có các dãy hoán vị độ dài 3 như sau:

Phân tích bài toán

Bài toán yêu cầu xây dựng vector nghiệm có \(n\) phần tử, dạng: \(X = x_1, x_2,…, x_n \)
Trong đó:

\(1 ≤ x_i ≤ n\)
\(x_i ≠ x_j\) với mọi \(1 ≤ i, j ≤ n\)

Để kiểm tra điều kiện các số trong nghiệm \(X\) đôi một khác nhau, ta dùng một mảng \(d\) với ý nghĩa: \(d[i] = 0\) nếu số \(i\) chưa được điền, \(d[i] = 1\) nếu số \(i\) đã được điền. Vậy trong hàm backtrack, trước khi đặt một giá trị \(x_k = i\) ta cần kiểm tra giá trị \(i\) đã được dùng hay chưa, và sau khi đặt thì sẽ đánh dấu là số \(i\) đã được đặt

Code bài toán duyệt hoán vị bằng C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define MAXN 11
int n;
int x[MAXN], d[MAXN];

//Hàm in nghiệm X 
void printX(){
    for(int i = 1; i <= n; i++)
        cout<<x[i]<<" ";
    cout<<endl;
}
//Hàm quay lui
void backtrack(int i){
  if(i>n){ //Nếu i>n => đã điền xong các giá trị của vector nghiệm X 
    //Nghiệm X chắc chắn thỏa mãn do đã được kiểm soát bằng cận trước đó
    //Vậy nên ta không cần kiểm tra nữa mà in ra luôn 
    printX();
    return;
  }
  //Thử các trường hợp có thể đặt được của vị trí k 
  for(int j = 1; j <= n; j++)
    if(d[j] == 0){  //Nếu số j chưa được đặt trước đó 
      x[i] = j;
      d[j] = 1;//Đánh dấu số j đã được sử dụng
      backtrack(i+1);//Đặt xong vị trí i thì đặt tiếp i+1
      //Sau khi đi sâu xuống nhánh con và quay lui trở lại 
      //Đồng nghĩa với việc sắp tới sẽ đặt thử giá trị mới cho vị trí i
      //Vậy ta sẽ phải bỏ đánh dấu là số j đã được sử dụng 
      d[j] = 0;
    } 
}
 
int main() { 
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);
  cin>>n;
  //Xây dựng nghiệm bắt đầu từ vị trí 1 
  backtrack(1);
  return 0;
}

Mô tả thuật toán duyệt hoán vị khi chạy

Kết luận

Bài toán trên các vector nghiệm \(X\) được sắp xếp theo thứ tự từ điển là do trong hàm backtrack, ta xét các trường hợp có thể đặt được cho mỗi phần tử \(x_k\) theo thứ tự từ điển, đặt thử \(0\) trước, đặt thử \(1, 2, 3 …n\) sau.

Nếu không đặt cận ngay trong hàm đệ quy thì thuật toán duyệt hoán vị sẽ có độ phức tạp là \(O(n^n∗n)\) do có \(n^n\) nghiệm được tạo ra (\(n\) phần tử, mỗi phần tử nhận giá trị \(1 .. n)\) và hàm kiểm tra nghiệm có phải hoán vị hay không cũng có độ phức tạp là \(O(n)\)
Thuật toán duyệt hoán vị có độ phức tạp \(O(n!)\)

Trong đó: \(n\) là độ dài vector nghiệm \(X\)

Lý do: thuật toán duyệt liệt kê tất cả các nghiệm có thể có của bài toán. Do số lượng hoán vị độ dài \(n\) bằng \(n!\) nên số lượng vector

4. Một số dấu hiệu của việc dùng Backtrack

Mỗi phần tử có hai trạng thái: chọn hoặc không chọn, tương đương với 1 và 0
=> Dùng duyệt nhị phân
Hỏi thứ tự sắp xếp của các phần tử sao cho điều kiện nào đó tối ưu
=> Dùng duyệt hoán vị

Xem thêm các bài trong Series Backtrack – duyệt – quay lui cho người mới bắt đầu :

5. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Advanced của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn