GA BDHSG Chuyên đề: ĐỆ QUI

CHUYÊN ĐỀ: THUẬT TOÁN ĐỆ QUI

I/ NỘI DUNG
1/ MÔ HÌNH CỦA 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ả thiết cấu hình cần liệt kê có dạng (x1,x2,……,xn). khi đó thuật toán quay lui thực hiện qua các bước sau:
Xét tất cả các giá trị x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán chon x1 ta sẽ:
Xét tất cả các giá trị x2 có thể nhận, lại thử cho x2 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x2 lại xét tiếp các khả năng chọn x3.......cứ tiếp tục như vậy đến bước.
n) Xét tất cả các giá trị xn có thể nhận, thử cho xn nhận lần lượt các giá trị đó, thông báo cấu hình tìm được (x1,x2,……,xn).
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 (x1,x2,……,xn) bằng cách thử cho x1 nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x1 lại liệt kê tiếp cấu hình n-1 phần tử (x2,x3,……,xn).

Mô hình của thuật toán quay lui có thể mô tả như sau:
(Thủ tục này thử cho xi nhận lần lượt các giá trị mà nó có thể nhận)
Procedure Try(i:Integer);
Begin
For (mọi giá trị V có thể gán cho xi) do
Begin

if (xi là phần tử cuối cùng trong cấu hình) then
Else Begin
;
Try(i+1);(Gọi đệ qui để chọn tiếp xi+1)
;
End;
End;
End;
Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1)
Ta có thể trình bày quá trình tìm kiếm lời giải của thuật toán quay lui bằng thuật toán quay lui bằng cây sau:












2/ MỘT SỐ VÍ DỤ
Ví dụ 1: Liệt kê các dãy nhị phân độ dài n
Biểu diễn dãy nhị phân độ dài N dưới dạng (x1,x2,……,xn). Ta sẽ liệt kê các dãy này bằng cách thử dùng các giá trị (0,1) gán cho xi . Với mỗi giá trị thử gán cho xi lại thử các giá trị có thể gán cho xi+1. Chương trình liệt kê bằng thuật toán quay lui.
Giải:
Program BinaryStrings;
Uses crt;
Const
Max=30;
input=`BSTR.INP`;
output=`BSTR.OUT`;
Var x: Array[1..max] of integer;
n:Integer; f,g:text;
Procedure PrintResult ;
Var I:Integer;
Begin
For i:=1 to n do write(g,x[i]); writeln(g);
End;
Procedure Try(i:integer);
Var J:integer;
Begin
For j:=0 to 1 do
Begin
x[i]:=j;
if i=n then PrintResult
else Try(i+1);
End;
End;
BEGIN
Clrscr;
Assign(F,Input);
Assign(g,output);Rewrite(g);
Reset(f);
Read(f,n);
Try(1);
Close(f);
Close(g);
Readln;
END.Ví dụ 2: Liệt kê các tập con k phần tử
Để liệt kê các tập con k phần tử của tập S=(1,2,……,n) ta có thể đưa về liệt kê các cấu hình (x1,x2,….,xk) ở đây các xi S và x1xk≤n
xk-1≤xk-1≤n-1
…………
xi≤n-k+i
………...
x1≤n-k+1.

Từ đó suy ra xi-1+1 ≤ xi ≤ n-k+i (1 ≤ i ≤ k) ở đây ta giả thiết có thêm một số x0=0 khi xét i=1. Như vậy ta sẽ xét tất cả các cách chọn x1 từ 1 (=x0+1) đến n-k+1,