Giả sử ta phải tìm trong một tập dữ liệu D cho trước một dãy dữ liệu:
v = (v[1], v[2],..., v[n])
thoả mãn
đồng thời hai tính chất P và Q. Trước hết ta chọn một trong hai tính chất đã
cho để làm nền, giả sử ta chọn tính chất P.
Sau đó ta thực hiện các bước sau đây:
Bước 1. (Khởi trị) Xuất phát từ một dãy ban đầu v = (v[1],...,
v[i])
nào đó của các phần tử trong D sao cho v
thoả P.
Bước 2. Nếu v
thoả Q ta dừng thuật toán và thông báo kết quả là dãy v, ngược lại ta thực hiện Bước 3.
Bước 3. Tìm tiếp một phần tử v[i + 1] để bổ sung cho v sao cho
v = (v[1],...,
v[i],
v[i
+ 1]) thoả P.
Có thể xảy
ra các trường hợp sau đây:
3.1. Tìm
được phần tử v[i + 1]: quay lại bước 2.
3.2. Không
tìm được v[i + 1] như vậy, tức là với mọi v[i + 1] có thể lấy trong D, dãy v = (v[1],..., v[i], v[i
+ 1]) không thoả P. Điều này có nghĩa là đi theo đường
v
= (v[1],..., v[i])
sẽ không
dẫn tới kết quả. Ta phải đổi hướng tại một vị trí nào đó. Để thoát khỏi ngõ cụt
này, ta tìm cách thay v[i] bằng một giá trị khác trong D. Nói
cách khác, ta loại v[i] khỏi dãy v, giảm i đi một đơn vị
rồi quay lại Bước 3.
Cách làm như trên được gọi là quay lui: lùi lại một bước.
Dĩ nhiên ta phải đánh dấu v[i] là phần tử đã loại tại vị trí i để sau đó không đặt lại phần tử đó vào
vị trí i trong dãy v.
Khi nào thì có thể trả lời là không tồn tại dãy v thoả đồng thời hai tính chất P và
Q? Nói cách khác, khi nào thì ta có thể
trả lời là bài toán vô nghiệm?
Dễ thấy, bài toán vô nghiệm khi ta đã duyệt hết mọi khả năng. Ta nói là
đã vét cạn mọi khả năng. Chú ý rằng có thể đến một lúc nào đó ta phải lùi liên
tiếp nhiều lần. Từ đó suy ra rằng, thông thường bài toán vô nghiệm khi ta không
còn có thể lùi được nữa. Có nhiều sơ đồ giải các bài toán quay lui, dưới đây là
hai sơ đồ khá đơn giản, không đệ quy.
Sơ đồ 1: Giải bài toán quay lui
(tìm 1 nghiệm) |
Sơ đồ 2: Giải bài toán quay lui
(tìm 1 nghiệm) |
Khởi trị v: v thoả P;
repeat
if (v thoả Q) then
begin
Ghi nhận nghiệm;
exit;
end;
if (Tìm được
1 nước đi) then Tiến
else
if (có thể lùi được)
then Lùi
else
begin
Ghi nhận: vô nghiệm;
exit;
end;
until false;
|
Khởi trị v:
v thoả P;
repeat
if (v thoả Q) then
begin
Ghi nhận nghiệm;
exit;
end;
if (Hết khả
năng duyệt) then
begin
Ghi nhận vô nghiệm;
exit;
end;
if (Tìm được
1 nước đi)
then Tiến
else
Lùi;
until false;
|
Thông thường ta khởi trị cho v là dãy rỗng (không chứa phần tử nào) hoặc dãy có một phần tử. Ta
chỉ yêu cầu dãy v được khởi trị sao
cho v thoả P. Lưu ý là cả dãy v thoả
P chứ không phải từng phần tử trong v thoả P.
Có bài toán yêu cầu tìm toàn bộ (mọi nghiệm) các
dãy v thoả đồng thời hai tính chất P
và Q. Nếu biết cách tìm một nghiệm ta dễ dàng suy ra cách tìm mọi nghiệm như
sau: mỗi khi tìm được một nghiệm, ta thông báo nghiệm đó trên màn hình hoặc ghi
vào một tệp rồi thực hiện thao tác Lùi, tức là giả vờ như không công nhận
nghiệm đó, do đó phải loại v[i] cuối cùng trong dãy v để tiếp tục tìm
hướng khác. Phương pháp này có tên là phương pháp giả sai. Hai sơ đồ trên sẽ
được sửa một chút như sau để tìm mọi nghiệm.
Sơ đồ 3: Giải bài toán quay lui
(tìm mọi nghiệm) |
Sơ đồ 4: Giải bài toán quay lui
(tìm mọi nghiệm) |
Khởi trị: v thoả P;
d := 0;
{đếm số nghiệm}
repeat
if (v thoả Q) then
begin
d
:= d+1;
Ghi nhận nghiệm thứ d;
Lùi; { giả sai }
end;
if
(Tìm được 1 nước đi)
then Tiến
else if (có thể lùi được)
then Lùi
else { hết khả năng }
begin
if d = 0 then
Ghi nhận: vô nghiệm;
else
Ghi nhận: d nghiệm;
exit;
end;
until false;
|
Khởi trị: v thoả P;
d := 0;
{đếm số nghiệm}
repeat
if (v thoả Q) then
begin
d := d+ 1;
Ghi nhận nghiệm thứ d;
Lùi; { giả
sai }
end;
if (Hết khả năng duyệt)
then
begin
if d = 0 then
Ghi nhận: vô nghiệm;
else
Ghi nhận: d nghiệm;
exit;
end;
if (Tìm được 1 nước đi)
then Tiến
else Lùi;
until false;
|
Không có nhận xét nào:
Đăng nhận xét