Sơ đồ chung của thuật toán quay lui

Nét đặc trưng của phương pháp quay lui là các bước hướng tới lời giải cuối cùng của bài toán hoàn toàn được làm thử

Tại mỗi bước, nếu có một lựa chọn thì ghi nhận lại lựa chọn này và tiến hành các bước thử tiếp theo. Còn ngược lại không có lựa chọn nào thích hợp thì quay lại bước thử trước, xóa bỏ sự ghi nhận và quay lại chu trình thử với các lựa chọn còn lại

Hành động này được gọi là quay lui, thuật toán thể hiện phương pháp này gọi là thuật toán quay lui

Điểm quan trọng của thuật toán là phải ghi nhớ tại mỗi bước đi qua để tránh trùng lặp khi quay lui. Dễ thấy là các thông tin này cần được lưu trữ vào một ngăn xếp, nên thuật toán thể hiện ý thiết kế một cách đệ quy.

Lời giải của bài toán thường biểu diễn bằng một vec tơ gồm n thành phần x = (x₁,...,x_n) phải thỏa mãn các điều kiện nào đó. Để chỉ ra lời giải x, ta phải xây dựng dần các lời giải x_i

- Tại mỗi bước i:

+ Đã xây dựng xong các thành phần x1,.., xi-1

+ Xây dựng thành phần x_i bằng cách lần lượt thử tất cả các khả năng mà x_i

có thể chọn :

Nếu một khả năng j nào đó phù hợp cho xi thì xác định xi theo khả năng j. Thường phải có thêm thao tác ghi nhận trạng thái mới của bài toán để hổ trợ cho bước quay lui. Nếu i = n thì ta có được một lời giải, nguợc lại thì tiến hành bước i+1 để xác định x_i+1 .

Nếu không có một khả năng nào chấp nhận được cho xi thì ta lùi lại bước trước (bước 1-1) để xác định lại thành phần xi-1.

Để đơn giản, ta giả định các khả năng chọn lựa cho các xi tại mỗi bước là như nhau, do đó ta phải có thêm một thao tác kiểm tra khả năng j nào là chấp nhận được cho x_i.

Mô hình của phương pháp quay lui có thể viết bằng thủ tục sau, với n là số bước cần phải thực hiện, k là số khả năng mà xi có thể chọn lựa.

Try(i)

for ( j = 1 → k)

If ( x_i chấp nhận được khả năng j)

{

Xác định x_i theo khả năng j;

Ghi nhận trạng thái mới;

if( i < n)

Try(i+1);

else

Ghi nhận nghiệm;

Trả lại trạng thái cũ của bài toán;

}

Ghi chú:

Tìm nghiệm bằng phương pháp quay lui có thể chuyển về việc tìm kiếm trên cây không gian các trạng thái, với cây được xây dựng từng mức như sau :

• Các con của gốc (thuộc mức 1) là khả năng có thể chọn cho x₁
• Giả sử x_i-1 là một nút ở mức thứ i-1, khi đó các nút con của x_i-1 là các khả năng mà xi có thể chọn, một khi đã tìm được các thành phần x₁,.., x_i-1.

Như vậy, mỗi nút xi của cây biểu diễn một lời giải bộ phận, đó là các nút nằm trên đường đi từ gốc đến nút đó

Ta có thể nói việc tìm kiếm nghiệm bằng phương pháp quay lui chính là tìm kiếm theo chiều sâu trên cây không gian các trạng thái.

Chúng ta sẽ nghiên cứu một số các ví dụ minh họa cho thuật toán quay lui