ĐỆ QUY QUAY LUI (BACK TRACKING)

1/. Giới thiệu về đệ quy quay lui

Một bài toán liệt kê tổ hợp luôn cần phải đảm bảo hai nguyên tắc, đó là: không được bỏ sót một cấu hình và không được trùng lặp một cấu hình. Có thể nói rằng phương pháp liệt kê là cách cuối cùng để có thể giải được một số bài toán tổ hợp hiện nay. Một trong những phương pháp liệt kê có tính phổ dụng cao đó là phương pháp quay lui.

Nội dung chính của phương pháp này là việc xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng. Giả thiết cấu hình cần được tìm được mô tả bằng một bộ giá trị $(x_1,x_2,..,x_n)$. Giả sử đã xác định được $i-1$ thành phần $(x_1,x_2,...,x_{i-1}$), bây giờ ta xác định thành phần $x_i$ bằng cách duyệt tất cả các khả năng có thể đề cử cho nó (đánh số từ $1$ đến $n_i$).Với mỗi khả năng $j$, kiểm tra xem $j$ có được chấp nhận hay không. Có thể có hai trường hợp có thể xảy ra:

• Nếu $j$ được chấp nhận thì xác định $x_i$ theo $j$, sau đó nếu $j=n$ thì ta được một cấu hình nghiệm, trái lại ta tiếp tục tiến hành việc xác định $x_{i+1}$.
• Nếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì ta sẽ lùi lại bước trước để xác định $x_{i-1}$.

Thông thường ta phân tích quá trình tìm kiếm thành cây tìm kiếm. Không gian tìm kiếm càng lớn hay càng nhiều khả năng tìm kiếm thì cây tìm kiếm càng lớn, càng nhiều nhánh. Vì vậy hạn chế và bỏ bớt các nhánh vô nghiệm của cây tìm kiếm sẽ tiết kiệm được thời gian và bộ nhớ, tránh bị tràn dữ liệu. Quá trình tìm kiếm lời giải theo thuật toán quay lui có thể được mô tả bởi mô hình cây tìm dưới đây:

Cần phải lưu ý là ta phải ghi nhớ tại mỗi bước đã đi qua, những khả năng nào đã thử để tránh trùng lặp. Những thông tin này được lưu trữ theo kiểu dữ liệu ngăn xếp - Stack (vào sau ra trước) - vì thế nên thuật toán này phù hợp thể hiện bởi thủ tục đệ quy.

Ta có thể mô tả bước xác định $x_i$ bởi thủ tục đệ quy sau:

Procedure BACKTRACK(i); {Chọn thực hiện bước thứ i}
Begin
    for CÁC PHƯƠNG ÁN CHỌN do 
        if CHỌN ĐƯỢC then
        begin
            THỰC HIỆN BƯỚC ĐI THỨ i;
            if THÀNH CÔNG then 
                THÔNG BÁO KẾT QUẢ  
            else  
                BACKTRACK(i+1);
            HỦY BƯỚC ĐI THỨ i; {Quay lui}
        end;
End;

Minh họa cụ thể bằng ngôn ngữ C++ như sau:

void backtrack(int i) 
{ 
    for (int j = 1; j <= n_i ; j++) 
        if (chấp nhận j)
        {
            X[i] = j; // xác định x_i theo j
            DD[j] = true; //ghi nhận việc đã chọn khả năng j (lệnh này có thể không có)
            if (i == n) //xây dựng được nghiệm (đã xác nhận đủ n thành phần)
                Ghi nhận một cấu hình nghiệm
            else 
                backtrack(i+1); //đi tìm phần tử thứ i+1 (chưa đủ các phần tử)
            DD[j] = false; //ghi nhận việc bỏ chọn khả năng j (lệnh này có thể không có)
        }
}

Trong thủ tục mô tả trên, điều quan trọng nhất là đưa ra được một danh sách các khả năng đề cử và xác định được giá trị của biểu thức logic [chấp nhận $j$]. Ngoài việc phụ thuộc $j$, giá trị này còn phụ thuộc vào việc đã chọn các khả năng tại $i-1$ bước trước đó. Trong những trường hợp như vậy, cần ghi nhớ trạng thái mới của quá trình sau khi [xác định $x_i$ theo $j$] và trả lại trạng thái cũ sau lời gọi $backtrack(i+1)$. Các trạng thái này được ghi nhận nhờ một số biến tổng thể (global), gọi là các biến trạng thái.

Dễ thấy rằng bài toán vô nghiệm khi ta đã duyệt hết mọi khả năng mà không có khả năng nào thoả mãn yêu cầu. Ta nói rằng là đã vét cạn mọi trường hợp. Chú ý rằng đến một lúc nào đó ta phải lùi liên tiếp nhiều lần. Từ đó suy ra rằng, thông thường bài toán vô nghiệm khi không thể lùi được nữa. Thuật toán này sẽ không có tính khả thi cao bởi dùng thủ tục đệ quy dễ bị lỗi tràn Stack.

2. Sử dụng đệ quy quay lui trong trường hợp nào:

Thường sử dụng trong các chương trình

• Cần liệt kê kết quả
• Cần duyệt qua các phương án để tìm phương án tối ưu
• Tìm một phương án
• Tìm thấy phương án thì dừng

Ví dụ:

• Liệt kê các hoán vị của số n
• Bài toán tám quân hậu
• Liệt kê dãy nhị phân độ dài n