Bài 3: Thuật toán quay lui

Dựa theo GIẢI THUẬT VÀ LẬP TRÌNH của thầy Lê Minh Hoàng

Bài 3: Thuật toán quay lui

Thủ tục quay lui dùng để giải các 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 xây dựng bằng cách liệt kê tất cả các khả năng.

( Hay nói một cách khác: Ta liệt kê lần lượt từng phần tử  của cấu hình và xét tất cả các khả năng có thể xảy ra của phần tử đó.)

Ví dụ: Cấu hình có dạng [x1,x2,x3,…,xn]

Ta xét lần lượt từ x1 -> xn;

Trong mỗi lần xét:

Ví dụ : Xét x1, trong mỗi khả năng của x1, gồm n-1 khả năng  xảy ra với x2, trong mỗi khả năng xảy ra với x2, có n-2 khả năng xảy ra với x3,…. ( Bỏ qua các khả năng đã xảy xa với những lần xét trước).

Mô hình của thuật toán quay lui:

{Thu tuc nay cho xi lan luot nhan tung gia tri ma no co the nhan duoc}
procedure Attempt(i);
begin
      for( moi gia tri V co the gan cho x[i])do
        begin
             <thu x[i] := V>;
             if(x[i] la phan tu cuoi cung trong cau hinh) then
                 <Thong bao tim duoc>
                 
             else 
                begin
                    <Ghi nhan cho viec x[i] nhan gia tri V (neu can)>;
                    Attempt(i+1); {Goi de qui de chon tiep x[i+1]}
                    <Neu can bo ghi nhan viec  thu x[i] := V de thu gia tri khac>;
                end;
        end;
end;