MÔ HÌNH QUAY LUI
Một phương pháp phổ biến để tìm các cấu hình là dùng giải thuật quay lui. Tư tưởng chính của giải thuật này là xây dựng dần các thành phần của cấu hình bằng cách thử lần lượt các khả năng có thể có. Nếu tồn tại một khả năng chấp nhận được thì tiến hành bước tiếp theo; trái lại cần lùi lại bước trước để thử lại các khả năng chưa được thử . Ta sẽ dùng cách diễn đạt qui nạp để mô tả một cách chi tiết giải thuật này. Trước tiên phải hình thức hoá việc biểu diễn một cấu hình. Thông thường ta trình bày một cấu hình cần xây dựng như một bộ có thứ tự (vector) gồm có n thành phần thỏa mãn một số ràng buộc nào đó. Giả sử đã xây dựng xong i-1 thành phần bây giờ là bước xây dựng thành phần xi. Ta lần lượt thử các khả năng có thể có của xi. Xảy ra các trường hợp:
-Tồn tại một khả năng j chấp nhận được. Khi đó xi sẽ được xác định theo khả năng này. Nếu xi là thành phần cuối (i=n) thì được một nghiệm. Trái lại, i<n thì tiến hành bước tiếp qui nạp.
-Tất cả các khả năng đề cử cho xi đều không chấp nhận được. Khi đó cần lùi lại bước xác định xi-1
Để đảm bảo việc vét cạn, các giá trị đề cử phải không được bỏ sót. Mặt khác để đảm bảo không trùng lặp khi quay lui để xác định xi-1 cần không được thử lại những giá trị thử rồi. Trong phần lớn các bài toán điều kiện chấp nhận j không những phụ thuộc j mà còn phụ thuộc vào việc đã xác định i-1 thành phần trước, do đó cần tổ chức một số biến trạng thái để cất giữ trạng thái của bài toán sau khi xây dựng xong một thành phần để chuẩn bị cho bước xây dựng tiếp. Trường hợp này cần hoàn nguyên lại trạng thái cũ khi quay lui để thử tiếp các khả năng trong lúc trước
Code:
MÔ HÌNH
Procedure Try(i:integer);
(* Xác định thành phần bằng đệ qui *)
Var j:integer;
Begin
For (j thuộc tập các khả năng để thử) do
If then
Begin
;
;
If i=n then
else Try(i+1);
end
end;