Bài giảng đệ quy quay lui

GIẢI THUẬT
ĐỆ QUI QUAY LUI
Quay lui là ban đầu ta tiến, tiến và tiến cho đến khi không tiến được nữa thì lui và lui cho đến khi có đường đi mới, ta lại tiến và tiến… lại lui, lui cho đến khi hết đường lui. Xong việc!
NỘI DUNG
Ý tưởng
Mô hình
Bài toán ngựa đi tuần
Bài toán 8 quân hậu
Bài tập
Ý TƯỞNG
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ột bước
Nếu có một lựa chọn thì ghi nhận lại lựa chọn và tiến hành các bước thử tiếp theo
Ngược lại thì làm lại bước trước, xóa bỏ sự ghi nhận và quay về thử các lựa chọn còn lại
Lời giải của bài toán thường biểu diễn bằng một vector gồm n thành phần x=(x1,x2,..,xn) phải thỏa mãn điều kiện nào đó
Để chỉ ra lời giải x, ta phải xây dựng dần các thành phần lời giải xi
Tại mỗi bước i:
Đã xây dựng xong các thành phần: x1,x2,..xi-1
Xây dựng các thành phần xi bằng cách lần lượt thử tất cả các khả năng mà xi có thể chọn:
MÔ HÌNH ĐỆ QUI QUAY LUI
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 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, ngược lại thì tiến hành bước i+1 để xác định xi+1
Nếu không có khả năng nào chấp nhận được cho xi thì ta lùi lại bước trước (i-1) để xác định lại thành phần xi-1
MÔ HÌNH ĐỆ QUI QUAY LUI
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 thực hiện, k là số khả năng chọn xi
Try(i)
For (j=1->k)
If (xi chấp nhận được khả năng j)
Xác định xi theo khả năng j
Ghi nhận trạng thái mới
if(iTry(i+1)
else
Ghi nhận nghiệm
Trả lại trạng thái cũ cho bài toán
MÔ HÌNH ĐỆ QUI QUAY LUI
BÀI TOÁN 1. BÀI TOÁN NGỰA ĐI TUẦN
Cho bàn cờ có NxN ô. Một con ngựa được phép đi theo luật cờ vua, đầu tiên được đặt ở ô có tọa độ x0,y0. Hãy chỉ ra hành trình(nếu có) đó là ngựa đi qua tất cả các ô của bàn cờ, mỗi ô đi qua đúng một lần
Kích thước bàn cờ 6*6
Tọa độ xuất phát : (2;3)
Tọa độ bước kế tiếp: (1;1)
Cách giải quyết là xem xét xem có thể thực hiện một nước đi kế tiếp hay không. Sơ đồ:
- Try(i)
for(j=1->k)
if(xi chấp nhận được khả năng j)
Xác định xi theo khả năng j
Ghi nhận trạng thái mới
If (iTry(i+1)
else
Ghi nhận nghiệm
Trả lại trạng thái cũ cho bài toán
BÀI TOÁN 1. BÀI TOÁN NGỰA ĐI TUẦN
Để mô tả chi tiết thuật toán, ta mô tả dữ liệu và các thao tác theo trình tự như sau:
1. Biểu diễn bàn cờ
2. Các khả năng lựa chọn cho xi
3. Cách thức xác định xi theo j
4. Cách thức ghi nhận trạng thái mới, trả về trạng thái cũ
5. Ghi nhận nghiệm
BÀI TOÁN 1. BÀI TOÁN NGỰA ĐI TUẦN
BÀI TOÁN NGỰA ĐI TUẦN
1. Biểu diễn bàn cờ
Ta sẽ biểu diễn bàn cờ bằng một ma trận vuông cấp n:
h[x][y]=0: ngựa chưa đi qua
h[x][y]=i: ngựa đã đi qua ở bước i
BÀI TOÁN NGỰA ĐI TUẦN
2. Các khả năng lựa chọn cho xi
Tọa độ x, y được xác định giá trị đường đi của con mã theo ngược chiều kim đồng hồ lần lượt như sau:
X=(2,1,-1,-2,-2,-1,1,2) Y=(1,2,2,1,-1,-2,-2,-1)
BÀI TOÁN NGỰA ĐI TUẦN
Tọa độ x, y được xác định giá trị đường đi của con mã theo ngược chiều kim đồng hồ lần lượt như sau:
X=(2,1,-1,-2,-2,-1,1,2) Y=(1,2,2,1,-1,-2,-2,1)
BÀI TOÁN NGỰA ĐI TUẦN
Để ghi nhận nước đi hợp lệ ở bước i, ta gán h[u][v]=i và hủy bước đi thì gán h[u][v]=0
Try(i,x,y)
for(k= 0->7)
u=x+a[k]; v=y+b[k]
if(1<=u,v<=n and h[u][v]=0)
h[u][v]=i
if(iTry(i+1,x,y)
else
Xuat_h;
h[u][v]=0
* Tổng quát
- Try(i,x,y)
- for(k= 1->8)
-u=x+a[k];v=y+b[k]
If ((1<=u) and
(u<=n) and (1<=v) and (v<=n)
and h[u][v]=0)
- h[u][v]=i
- if(i - Try(i+1,x,y)
else
Xuat_h;
h[u][v]=0
Nsq=n*n
kích thức bàn cờ)
Trả lại trạng thái cũ cho bài toán
DEMO BÀI TOÁN MÃ ĐI TUẦN
BÀI TOÁN 2. BÀI TOÁN 8 QUÂN HẬU
A solution
Not a solution
BÀI TOÁN 2. BÀI TOÁN 8 QUÂN HẬU
BÀI TOÁN 8 QUÂN HẬU
Yêu cầu: Đặt tám quân hậu lên một bàn cờ vua sao cho không quân nào có thể ăn được nhau
A solution
Not a solution
BÀI TOÁN 8 QUÂN HẬU
Theo luật cờ vua, một quân hậu có thể ăn các quân khác nếu cùng nằm trên một đường:
Hàng,
Cột
Các đường chéo (đi qua vị trí của hậu)
Suy ra mỗi hàng (cột) chỉ chứa một quân hậu- việc chọn quân hậu thứ i có thể giới hạn trên hàng i
BÀI TOÁN 8 QUÂN HẬU
Trong hai đường chéo
Đường chéo thuận: tất cả các ô có hiệu các tọa độ (i-j) là hằng số
Đường chéo ngược: tất cả các ô có tổng các tọa độ (i+j) là hằng số
BÀI TOÁN 8 QUÂN HẬU
+ Đối với bài toán 8 quân hậu:
- Do mỗi cột chỉ có thể có một quân hậu nên lựa chọn đối với quân hậu thứ j, ứng với cột j, là đặt nó vào hàng nào để đảm bảo “an toàn” nghĩa là không cùng hàng, không cùng đường chéo với j-1 quân hậu đã được sắp xếp trước đó.
- Rõ ràng để đi tới các lời giải ta phải thử tất cả các trường hợp sắp xếp quân hậu. Đầu tiên tại cột 1. Với một vị trí thử như vậy ta phải giải quyết bài toán 7 con hậu với phần còn lại của bàn cờ, nghĩa là ta đã “quay lại bài toán cũ”!
BÀI TOÁN 8 QUÂN HẬU
Sử dụng giải thuật đệ quy quay lui cho bài toán 8 con hậu, ta có:
- Try(j):Chọn dòng để đặt quân hậu thứ j (ở cột j).
Các phương án chọn:
Như trên đã nêu, đối với quân hậu thứ j, vị trí của nó chỉ chọn trong cột thứ j.
Vậy tham biến j trở thành chỉ số cột và việc chọn lựa “các phương án chọn” đuợc tiến hành trên 8 giá trị số hàng i (chọn dòng i: 1, 2,3 ,.., 8).
BÀI TOÁN 8 QUÂN HẬU
Chọn được: Để lựa chọn i được chấp nhận, thì hàng i và hai đường chéo qua ô (i,j) phải không có quân hậu nào ở trên đó.
Ta thấy trong đường chéo theo chiều (song song với chéo chính) có các ô (i,j) mà tổng (i+ j) không đổi, còn đường chéo theo chiều (song song với chéo phụ) có các ô (i,j) mà i-j không đổi.
(Phụ)
(Chính)
(Phụ)
(Chính)
BÀI TOÁN 8 QUÂN HẬU(3/3)
Do đó ta sẽ chọn các mảng một chiều Boolean để biểu diễn các tình trạng này:
Như vậy điều kiện để “chọn được” là:
a[i] and b[i+j] and c[i-j] có giá trị true.
BÀI TOÁN 8 QUÂN HẬU
Ta đã biết: 1<=i, j<=8 (1<=i and i<=8, 1<=j and j<=8)
→ Nên suy ra 2<=i +j <=16 và -7<=i -j<=7
Vị trí của mỗi con hậu được ghi vào mảng một chiều X gồm 8 phần tử là 8 vị trí dòng của các con hậu ở 8 cột tương ứng.
BÀI TOÁN 8 QUÂN HẬU(3/3)
- Thực hiện bước đi thứ j:
Thành công:
Khi j=8 tức là đặt xong vị trí của 8 con hậu, khi đó sẽ “thông báo kết quả” vị trí các con hậu đã đặt, ngược lại sẽ tiếp tục thử để đặt các con hậu tiếp theo.
- Hủy bước đi thứ j:
a[i] := true;
b[i+j] := true;
c[i-j] := true;
procedure thu( i: integer);
Var j: integer;
begin
for j:=1 to n do
if a[j] and b[i+j] and c[i-j] then
begin
x[i]:=j;
a[j]:= false;
b[i+j]:= false;
c[i-j]:= false;
if i=n then
inkq
else {i thu(i+1);
a[j]:= true;
b[i+j]:= true;
c[i-j]:= true;
end;
end;
*Chương trình bài toán 8 hậu
program tam_conhau;
uses crt;
Var
n: integer;
x: array[1..8] of integer;
a: array[1..8] of boolean;
b: array[2..16] of boolean;
c: array[-7..7] of boolean;
dem: word;
{-----------------------------------}
procedure khoitao;
var
i: integer;
begin

dem:=0;
for i:=1 to n do a[i]:= true;
for i:=2 to 2*n do b[i]:= true;
for i:=1-n to n-1 do c[i]:= true;
end;
procedure thu( i: integer);
var
j: integer;
begin
for j:=1 to n do
if a[j] and b[i+j] and c[i-j] then
begin
x[i]:=j;
a[j]:= false;
b[i+j]:= false;
c[i-j]:= false;
if i=n then
inkq
else{i thu(i+1);
a[j]:= true;
b[i+j]:= true;
c[i-j]:= true;
end;
end
Chương trình bài toán 8 hậu
procedure inkq;
var
i: integer;
begin
dem:=dem+1;
write(dem:5,`. `);
for i:=1 to n do
write(x[i]:3);
writeln;
end;
BEGIN
clrscr;
write(` Moi ban co cua ban co(n>=4): n= `); readln(n);
if n<4 then
writeln(` Ban da nhap co cua ban co nho hon 4*4. Nen se khong co dap an.`)
else
begin
khoitao;
thu(1);
writeln(` Cac ban da thanh cong`);
end;
readln;
END.
Chương trình bài toán mã đi tuần
program knighs_tour;
const n=8;
nsq=n*n;
xNext:array[1..8] of integer=(2,1,-1,-2,-2,-1,1,2);
yNext:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);
type index=1..n;
trace=0..nsq;
board=array[index,index] of trace;
var i,j:index;
q:boolean;
kq:board;
Chương trình bài toán mã đi tuần
procedure try(i:trace; x,y:index; var q:boolean);
var k,u,v:integer;
q1:boolean;
begin
k:=0;
repeat
k:=k+1;
q1:=false;
u:=x+xNext[k];
v:=y+yNext[k];

if (1<=u) and (u<=n) and (1<=v) and (v<=n) then
if (kq[u,v]=0) then
begin
kq[u,v]:=i;
if (i begin
try(i+1,u,v,q1);
if (not q1) then
kq[u,v]:=0;
end
else
q1:=true;
end;
until q1 or (k=8);
q:=q1;
end;
Chương trình bài toán mã đi tuần
Begin
for i:=1 to n do
for j:=1 to n do
kq[i,j]:=0;

q:=false;
kq[1,1]:=1;
try(2,1,1,q);

if q then
for i:=1 to n do
begin
for j:=1 to n do
write(kq[i,j]:3);
writeln;
end
else
writeln(`: Khong tim duoc loi giai `);

readln;
End.
Nguyên tắc cơ bản của phương pháp tìm kiếm quay lui là như sau:
- Chia tập tìm kiếm thành nhiều tập con,
- Đánh số các tập con theo một tiêu chuẩn nào đó  có các tập P1, P2, . . ., Pk,
- Với mỗi tập con nhận được: xác định một trong số các khả năng:
- Không cần xét tiếp tập này,
- Bài toán trở nên quá đơn giản và tìm được một lời giải,
- Quay lại bước đầu với tập con này.
- Tiêu chuẩn phân chia tập con: thỏa mãn một trong số các tính chất:
Nhận được bài toán giống như ban đầu, nhưng có kích thước bé hơn,
Nhận được bài toán đơn giản hơn,
Nhận được bài toán với một số tính chất mới không có trong bài toán ban đầu.
- Tiêu chuẩn đánh số các tập con:
Theo thứ tự từ điển của một cấu trúc dữ liệu,
Theo khả năng, triển vọng tồn tại nghiệm.
- Tìm kiếm quay lui về bản chất gần giống các giải thuật đệ quy, nhưng có một số khác biệt cơ bản:
Người lập trình điều khiển được quá trình duyệt theo các hướng có triển vọng,
Không cần lưu toàn bộ các nút rẽ nhánh trong tìm kiếm,
Có thể dễ dàng ngắt và quay lui khi cần thiết.
Chính vì những đặc điểm trên nên giải thuật này thường áp dụng để giải các bài toán theo phương pháp nhánh và cận.