Đệ quy quay lùi đồ thị
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (114.27 KB, 6 trang )
Đệ quy quay lui với các bài toán về đồ thị
Chu Đức Minh
Có lẽ bạn cũng đã làm quen với khái niệm đệ quyvà giải thuật đệ quy là thế nào rồi. Nếu
bạn chưa thực sự rõ lắm về giải thuậtđệ quy xin mời bạn tham khảo thêm ở Tạp chí Tin
học & Nhà trường số 2 năm2000, bài viết 'Đệ quy và Giải thuật đệ quý đã đề cập rất rõ về
vấnđề này.
Quả hẳn, giải thuật đệ quy làmcho bài toán trở lên đơn giản và dễ hiểu. Có những bài toán
chúng ta không thểkhông dùng giải thuật đệ quy để cài đặt cho bài toán bởi tính chất mạnh
mẽ vàchặt chẽ của nó. Tuy nhiên cũng có những bài toán thì giải thuật đệ quy tỏ rakhông
tác dụng cho lắm, lúc đó giải thuật khử đệ quy là phương án tối ưu nhất.
Trong hầu hết các bài toán vềđồ thị (graph), xét tính liên thông, tìm các thành phần liên
thông của đồ thị,tìm đường đi giữa hai đỉnh của đồ thị, tìm đường đi ngắn nhất? ta đều
dùng mộtgiải thuật có tính chất đệ quy nhưng đặc biệt hơn là nó còn mang tính chất quylui
và lặp lại được gọi là giải thuật đệ quy quay lui (Back Tracking).
Thuật toán đệ quy quay lui (Back Tracking)
Nét đặc trưng của thuật toánnày là ở chỗ các bước đi tới lời giải hoàn toàn được làm thử.
Nếu có một lựachọn được chấp nhận thì ghi nhớ các thông tin cần thiết và tiến hành các
bướcthử tiếp theo. Trái lại, không có lựa chọn nào thích hợp cả thì làm lại bướctrước, đồng
thời xoá bớt các ghi nhớ và quay về chu trình thử với các lựa chọncòn lại. Hành động được
gọi là quay lui và các giải thuật thể hiện phương phápnày gọi là giải thuật đệ quy quay lui.
Có thể nêu giải thuật như sau(mô phỏng theo ngôn ngữ tựa Pascal):
PROCEDUCE TRY(J);
FORmỗi phương án chọn DO
IFchọn được THEN
BEGIN
Thực hiện bước đi;
IF thành công THEN thông báo kết quả
ELSE Try(j+1);
Hủybước đi vừa rồi;
END
RETURN;
Một số bài toán mô phỏng thuật giải trên
Bài toán 1: Xét tính liên thông
Chomột đồ thị gồm N đỉnh được đánh số từ 1 đến N lưu trữ ma trận kề A. A[i,j] cógiá trị là
1 nếu có đường đi giữa i và j, có giá trị là 0 nếu giữa i và j khôngcó đường đi. Cho trước
hai đỉnh P và Q. Hỏi có tồn tại đường đi từ P đến Qkhông (hay P và Q có liên thông
không?).
Giải thuật:
Đỉnhđầu tiên được chọn là P. Do đó ta phải đánh dấu đỉnh đó và lưu vết thứ nhất làP.
Bước1: Xuất phát từ đỉnh P (ta chọn chọn để thực hiện bước thứ j), duyệtqua tất cả các
đỉnh. Với mỗi đỉnh kiểm tra xem đỉnh đó đã được chọn chưa và cóđường đi từ đỉnh đến
đỉnh K không. Nếu thỏa mãn rằng có đường đi từ P đến đỉnhK và K chưa được chọn thì
thực hiện:
+ Đánh dấu đỉnh K
+Lưu vết
Bước2: Sau đó kiểm tra xem đỉnh K đó có trùng với Q chưa. Nếu trùng thìthông báo là liên
thông và kết thúc, còn không thì quay lại bước 1 với đỉnhxuất phát là K.
Bước3: Bỏ đánh dấu đỉnh K.
Tacần tổ chức một mảng Vet: Array [1..N] of Integer; để lưukết quả đường đi, đồng thời
tổ chức một mảng Chon: Array [1..N] of Boolean; đểđánh dấu các đỉnh được nạp. Nếu
Chon[i] có giá trị True nếu đỉnh đó chưa kếtnạp, ngược lại có giá trị False thì đỉnh đó đã
kết nạp.
Thủ tục như sau:
Proceduce Try(M,j: Byte);
Var i: Byte;
Begin
Fori:=1 to N do
If(A[M,i]=1) and B[i] then
Begin
B[i]:=False; {đánh dấu đỉnh được kết nạp}
If i=Q then
Begin write ('Có đường đi từ',P, 'đến',Q,'!'); Halt;
End
Else Try1(i, j +1);
B[i]:=True; {Hủy đánh dấu đỉnh đã kết nạptrước đó}
End;
write('Cóđường đi từ' ,P,'đến',Q,'!');
Halt;
End;
Yêucầu:
+Bạn có thể cải tiến thuật giải của bài toán trên để liệt kê tất cả các đường đitừ P đến Q.
+Giả sử đồ thị có trọng số, hãy cải tiến thuật giải trên để xác định đường đingắn nhất từ P
đến Q. Lưu ý: khi đồ thị có trọng số thì nếu giữa hai đỉnh cóđường đi thì giá trị trọng số
khác 0,ngược lại sẽ bằng 0. Do đó khi kiểm tra có đường đi hay không ta chỉ cần thayđiều
kiện A[M,i] =1 bằng A[M,i] <> 0. Trong quá trình đánh dấu ta phảithực hiện tính tổng các
trị số trên đường đi. Sau đó, khi một phương án thànhcông thì so sánh với kết quả của
phương án trước xem giá trị nào nhỏ hơn vàthực hiện lưu kết quả. Kết quả sau cùng là giá
trị của đường đi ngắn nhất.
Bài toán 2: Diện tích bồn cỏ
Chobảng chữ nhật A gồm M dòng và N cột. Trên mỗi ô ghi các giá trị 0 và 1: giá trị0 được
hiểu là nước, giá trị 1 được hiểu là đất. Hai ô đất có cạnh liền nhauđược xem như nằm
trong cùng một bồn cỏ. Hãy xác định diện tích của bồn cỏ lớnnhất (mỗi ô được xem như 1
đơn vị đo).
Nhận xét:
-Mỗi ô được đánh số 1 được xem như là một đỉnh của đồ thị.
-Hai đỉnh được gọi là liên thông nếu có chung cạnh. Như vậy yêu cầu của bài toánchính là
tìm thành phần liên thông có số đỉnh lớn nhất.
Giải thuật:
-Hoàn toàn tương tự như bài toán trên. Xuất phát từ ô A[i,j] có giá trị là 1 tatìm tất cả các ô
liên thông của nó, đồng thời ghi nhận tổng số đỉnh liên thông.
-Tìm tất cả các thành phần liên thông như thế và so sánh giá trị tổng lớn nhất,đó chính là
kết quả của bài toán.
Chú ý: Với mỗi ô ta có 4 ô có chungcạnh với nó. Chính vì vậy cần tổ chức hai hằng mảng
lưu vị trí của 4 ô ứng vớiô được chọn để quá trình duyệt đệ quy đơn giản hơn như sau:
Const dong:array[1..4] of Integer = (0, -1, 0, 1);
cot: array[1..4] of Integer = (-1, 0, 1, 0);
Thủtục xác định vùng liên thông và lưu lại giá trị số đỉnh của vùng liên thông quatham
biến Tong:
ProceduceXdlthg(i, j: Byte; Var Tong: Integer);
{Xacđinh vung lien thong}
Var k: Byte; x,y: Byte;
Begin
Tong:=Tong+1; A[i, j]:=0;
Fork:=1 to 4 do
Begin
x:=i+dong[k]; y:=j+cot[k];
If ((1<=x) and (x<=M) and (y>=1) and (y<=N)) and (A[x,y]=1) then
Xdlthg(x, y, Tong);
End;
End;
Thủ tục xác định diện tích bồn cỏ (vùng liênthông) lớn nhất:
ProceduceDT_lonnhat;
Var DTLN: Integer; i,j: Byte;
Begin
DTLN:= 0; dem:=0;
For i:=1 to m do
For j:=1 to n do
If A[i, j]=1 then
Begin
Tong:=0;Inc(dem);
Xdlthg(i,j, Tong);
End;
writeln;
writeln('Diện tích lớn nhất là:', DTLN);
End;
Yêucầu: Bạn hãy cải thiện giải thuật trên để giải quyết bài toán trên:ngoài việc trả lời diện
tích lớn nhất còn đưa ra màn hình tọa độ góc trên bêntrái và góc dưới bên phải của hình
chữ nhật chứa vùng liên thông ấy; trả lời sốvùng có trong mảng A.
Bài toán 3: Dãy số lớn nhất
Chobảng hình chữ nhật A có M dòng và N cột. Trong mỗi ô ghi một số nguyên
dương.Người ta tạo các dãy số từ bảng trên a
1
, a
2
,... a
k
theo nguyên tắc sau: a
i
≤ a
i+1
và a
i
,
a
i+1
phải nằm trong ô có chung cạnh. Đồng thời trong dãy số không có hai số trongmột ô
được lặp lại. Hãy lập chương trình để xác định dãy số có số lượng phần tửnhiều nhất.
Thôngbáo ra màn hình dãy số đó kèm theo vị trí của các ô đó dưới dạng sau:
..a (i,j);b(i,j);...
Vídụ: 1(1,3); 1(2,3)...
