THUẬT TOÁN QUAY LUI

 Thuật toán quay lui 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 cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng. Giả sử cấu hình cần liệt kê có dạng x[1..n], khi đó thuật toán quay lui thực hiện qua các bước:

1)             Xét tất cả các giá trị x[1] có thể nhận, thử cho x[1] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x[1] ta sẽ:

2)             Xét tất cả các giá trị x[2] có thể nhận, lại thử cho x[2] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x[2] lại xét tiếp các khả năng chọn x[3] … cứ tiếp tục như vậy đến bước:
¼

n) Xét tất cả các giá trị x[n] có thể nhận, thử cho x[n] nhận lần lượt các giá trị đó, thông báo cấu hình tìm được áx[1], x[2], …, x[n]ñ.

Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các cấu hình n phần tử dạng x[1..n] bằng cách thử cho x[1] nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x[1] bài toán trở thành liệt kê tiếp cấu hình n - 1 phần tử x[2..n].

Mô hình của thuật toán quay lui có thể mô tả như sau:

{Thủ tục này thử cho x[i] nhận lần lượt các giá trị mà nó có thể nhận}
procedure Attempt(i); begin
for ámọi giá trị V có thể gán cho x[i]ñ do begin
áThử cho x[i] := Vñ;
if áx[i] là phần tử cuối cùng trong cấu hìnhñ  then
áThông báo cấu hình tìm đượcñ
else
begin
áGhi nhận việc cho x[i] nhận giá trị V (nếu cần)ñ; Attempt(i + 1); {Gọi đệ quy để chọn tiếp x[i+1]}
áNếu cần, bỏ ghi nhận việc thử x[i] := V để thử giá trị khácñ; end;
end;
end; 

Thuật toán quay lui sẽ bắt đầu bằng lời gọi Attempt(1)