Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng

 Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng
 A. MỞ ĐẦU
I. Lý do chọn đề tài
 Tự học tập, nghiên cứu là một nhiệm vụ quan trọng của mỗi giáo viên để nâng 
cao trình độ chuyên môn, đặc biệt tự học, tự nghiên cứu có vai trò quan trọng trong 
vấn đề bồi dưỡng học sinh giỏi.
 Vì vậy, trong năm học này tôi đã nghiên cứu chuyên đề: Các thuật toán tìm 
kiếm trên đồ thị và một số bài tập ứng dụng.
II. Mục tiêu nghiên cứu của đề tài
 • Tìm hiểu tư tưởng, thuật toán tìm kiếm trên đồ thị: DFS – BFS.
 • Một số bài tập ứng dụng:
 + Đề bài
 + Ý tưởng thuật toán
 + Chương trình
 + Xây dựng bộ test
III. Phương pháp nghiên cứu
 - Nghiên cứu cơ sở lý thuyết
 - Thu thập thông tin, tài liệu
 - Tìm hiểu một số bài toán ứng dụng
IV. Giới hạn, phạm vi nghiên cứu của đề tài
 Chuyên đề bồi dưỡng học sinh giỏi, có một số bài khó chỉ áp dụng cho đối 
tượng học sinh chọn đội tuyển và bồi dưỡng quốc gia.
 1 Trương Nữ Thùy Duyên Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng
2. Thuật toán tìm kiếm theo chiều rộng
 Thuật toán này thực ra là sự cải biến về thứ tự duyệt đỉnh trên đồ thị của tìm 
kiếm theo chiều sâu bằng cách thay vì dùng một STACK thì ta lại dùng một hàng đợi 
QUEUE để kết nạp đỉnh được thăm. Như vậy, đỉnh được thăm càng sớm sẽ càng sớm 
trở thành duyệt xong (cơ chế First In First Out - Vào trước ra trước). Thủ tục được 
mô tả dưới đây:
Procedure BFS(u);
Begin
 Queue:=Empty
 Kết nạp u vào Queue;
 Daxet[u]:=True;
 While QueueEmpty do
 Begin
 Lấy v từ Queue;
 Visit(v);
 For w thuộc Kề(v) do 
 If not Daxet[w] then 
 Begin
 Kết nạp w vào Queue;
 Daxet[w]:=True;
 End; 
 End;
End;
Ta có thủ tục tìm kiếm theo chiều rộng là:
Procedure Find;
Begin
 Fillchar(Daxet,SizeOf(Daxet),False);
 For u thuộc V do
 If not Daxet[u] then BFS(u);
End;
 Tương tự như thuật toán tìm kiếm theo chiều sâu, ở thuật toán này mỗi lần gọi 
thủ tục BFS(u) thì mọi đỉnh cùng thành phần liên thông với u sẽ được thăm. Thủ tục 
Visit(u) như đã nói ở trên.
 Từ hai thuật toán trên, rất nhiều bài toán cơ bản trên đồ thị được giải quyết rất dễ 
dàng. 
 * Bài toán tìm thành phần liên thông của đồ thị
 Cho một đồ thị G =(V,E). Hãy cho biết số thành phần liên thông của đồ thị và 
mỗi thành phần liên thông gồm những đỉnh nào.
 3 Trương Nữ Thùy Duyên Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng
 Còn với thủ tục BFS ta cũng sửa lại trong lệnh If như sau:
If not Daxet[w] then
 Begin
 Kết nạp w vào Queue;
 Daxet[w]:= True;
 Truoc[w]:= v;
 End;
 Việc viết đường đi lên màn hình (hoặc ra file) có thể có 3 cách:
 - Viết trực tiếp dựa trên mảng Truoc: Hiển nhiên đường đi hiển thị sẽ ngược từ 
đỉnh t trở về s như sau:
 p1:=Truoc[t] p2:=Truoc[p1] .... s
 - Dùng thêm một mảng phụ P: cách này dùng để đảo đường đi từ mảng Truoc để 
có đường đi thuận từ đỉnh s đến đỉnh t.
 - Cách thứ 3: là dùng chương trình đệ quy để viết đường đi.
Procedure Print_Way(i:Byte);
 If is then
 Begin 
 Print_Way(Truoc[i]);
 Write('->', i);
 End;
 Lời gọi thủ tục đệ quy như sau:
Write(s);
Print_Way(s);
 Các bạn có thể tuỳ chọn cách mà mình thích nhưng thiết nghĩ đó chưa phải là 
vấn đề quan trọng nhất. Nếu tinh ý dựa vào thứ tự thăm đỉnh của thuật toán tìm kiếm 
theo chiều rộng BFS ta sẽ có một nhận xét rất quan trọng, đó là:
 Nếu có đường đi từ s đến t, thì đường đi tìm được do thuật toán tìm kiếm theo 
chiều rộng cho chúng ta một hành trình cực tiểu về số cạnh.
 Nhận xét quan trọng trên là cơ sở cho các thuật toán tìm kiếm lời giải tối ưu dựa 
trên lý thuyết đồ thị. Thực ra, nó là trường hợp riêng của một bài toán lớn trong đồ thị 
- Bài toán tìm đường đi ngắn nhất.
 Trên đây là những thuật toán tìm kiếm cơ bản nhưng rất quan trọng trên đồ thị. 
Những thuật toán này sẽ là nền móng quan trọng để có thể xây dựng và thiết kế 
những thuật giải khác trong lý thuyết đồ thị. 
 5 Trương Nữ Thùy Duyên Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng
Ý tưởng: Số lượng các khóm cỏ có thể xem là số vùng liên thông trên đồ thị. Trong 
đó, khi a[i,j] là cỏ và 4 đỉnh lân cận của nó, nếu cũng là cỏ thì tồn tại đường đi từ 
a[i,j] đến đỉnh đó.
Uses math; Procedure Dfs(x,y: longint);
Const const
fi ='VBGRASS.INP'; tx : array [1..4] of longint = (1,-1,0,0);
fo ='VBGRASS.OUT'; ty : array [1..4] of longint = (0,0,1,-1);
 var 
MAXN = 200; i,u,v: longint;
 begin
Var f[x,y]:=false;
f : array [0..MAXN+1,0..MAXN+1] of boolean; for i:=1 to 4 do
m,n : longint; begin
Res : longint; u:=tx[i] + x;
 v:=ty[i] + y;
Procedure Init(); if f[u,v] then
begin dfs(u,v);
 Fillchar(f,sizeof(f),false); end;
 Res := 0; end;
end; Procedure Solve();
 var i,j : longint;
Procedure ReadData(); begin
var i,j : longint; for i:=1 to m do
c : char; for j:=1 to n do
begin if f[i,j] then
 Readln(m,n); begin
 for i:=1 to m do dfs(i,j);
 begin inc(Res);
 for j:=1 to n do end;
 begin end;
 read(c);
 f[i,j] := c = '#'; BEGIN
 end; assign(input,fi); reset(input);
 readln; assign(output,fo); rewrite(output);
 end; Init();
end; ReadData();
 Solve();
 Writeln(Res);
 close(input); close(output);
 END.
 7 Trương Nữ Thùy Duyên Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng
Ví dụ
 VMUNCH.INP VMUNCH.OUT
 5 6 9
 B...*.
 ..*...
 .**.*.
 ..***.
 *..*.C
Ý tưởng : Bfs bắt đầu từ đỉnh B, với bảng f[i,j] là độ dài đường đi ngắn nhất từ đỉnh 
(i,j) đến đỉnh B, kết quả là f[cx,cy];
Const
fi ='VMUNCH.inp'; Procedure xuly;
fo ='VMUNCH.out '; var bot,top,x,y,i : longint;
MAXN =1500; u : pos;
tx : array [1..4] of longint = (1,0,-1,0); begin
ty : array [1..4] of longint = (0,1,0,-1); bot:=1;top:=1;
 repeat
Type u:=q[top];inc(top);
pos=record a[u.x,u.y]:=false;
 x,y : longint; for i:=1 to 4 do
 end; begin
 x:=u.x+tx[i];y:=u.y+ty[i];
Var if a[x,y] then
a : array [0..MAXN,0..MAXN] of boolean; begin
d : array [1..MAXN,1..MAXN] of longint; a[x,y]:=false;
q : array [1..MAXN*MAXN] of pos; inc(bot);
r,c,cx,cy : longint; q[bot].x:=x;
 q[bot].y:=y;
Procedure nhap; d[x,y]:=d[u.x,u.y]+1;
var i,j : longint; end;
t : char; end;
begin until top>bot;
 assign(input,fi);reset(input); end;
 fillchar(a,sizeof(a),false);
 readln(r,c); Procedure xuat;
 for i:=1 to r do begin
 begin assign(output,fo);rewrite(output);
 9 Trương Nữ Thùy Duyên Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng
Dữ liệu: Vào từ file văn bản CIRCUIT.INP:
• Dòng đầu tiên chứa hai số nguyên N và M. N (1 N 100 là số dòng và M 
 (1 M 100) là số cột của lưới. Mỗi nút trên của lưới được xác định bởi hai toạ độ: 
 Nút ở góc trái trên có toạ độ (1,1), nút ở góc phải dưới có toạ độ (N,M)
• Mỗi một trong số N dòng tiếp theo chứa M sốnguyên. Số nguyên ở tên dòng i và 
 cột j của dòng này mô tả đoạn dây nối giữa cặp nối (i,j) và (i+1,j) cũng như giữa 
 cặp nút (i,j) và (i,j+1) theo qui tắc sau:
  0 có nghĩa là không có đoạn dây nối giữa (i,j) và (i+1,j) cũng như giữa cặp nút 
 (i,j) và (i,j+1)
  1 có nghĩa là có đoạn dây nối giữa cặp nút (i,j) và (i+1,j);
  2 có nghĩa là có đoạn dây nối giữa cặp nút (i,j) và (i,j+1);
  3 có nghĩa là cả cặp nút (i,j) và (i+1,j) và (i,j) và (i,j+1) đều được nối với nhau
Kết quả: ghi ra file văn bản CIRCUIT.OUT:
• Dòng đầu tiên chứa hai số nguyên K và V, trong đó K là số đoạn nối cần bổ sung 
 trong cách bổ sung với chi phí nhỏ nhất tìm được còn V là chi phí tương ứng.
• Mỗi một trong số K dòng tiếp theo chứa ba số nguyên i,j và d, trong đó (i,j) là toạ 
 độ của nút còn d chỉ nhận một trong hai giá trị 1 và 2. d=1 cho biết phải nối nút 
 (i,j) với (i+1,j) và d=2 cho biết phải nối nút (i,j) với (i,j+1)
Ví dụ: Xem minh hoạ trong hình 1 và 2
 CIRCUIT.INP CIRCUIT.OUT
 4 5 5 6
 2 1 1 2 1 1 1 1
 0 3 0 1 0 3 2 1
 3 0 0 3 1 3 3 1
 0 2 0 2 0 3 3 2
 2 5 1
 Ý tưởng: Tại mỗi nút (i,j) ta xét 4 nút xung quanh của nó: Q1(i,j-1), Q2(i+1,j), 
Q3(i,j+1), Q4(i-1,j). 
 Q4 (i-1,j)
 Q1 (i,j-1) .(i,j) Q3 (i,j+1)
 Q2 (i+1,j)
 - Nếu các nút này kề với nó và chưa được thăm thì thăm nút đó và tiếp tục duyệt 
nút đó. Sau khi xét hết 4 nút xung quanh của nút (i,j), nếu nút nào vẫn chưa được 
 11 Trương Nữ Thùy Duyên Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng
Procedure ReadIn;
Var
 InFile: Text;
 x,y,z: Byte;
Begin
 Assign(InFile, fin); Reset(InFile);
 ReadLn(InFile, N,M);
 For x:=1 To N Do
 Begin
 For y:=1 To M Do
 Begin
 Read(InFile, z);
 G[x,y]:=z;
 End;
 ReadLn(InFile);
 End;
 Close(InFile);
 For x:=0 To N+1 Do
 Begin
 G[x,0]:=Visited;
 G[x,M+1]:=Visited;
 End;
 For y:=0 To M+1 Do
 Begin
 G[0,y]:=Visited;
 G[N+1,y]:=Visited;
 End;
End;
Procedure WriteOut;
Var i:Integer;
 OutF:Text;
Begin
 Assign(OutF, fou); Rewrite(OutF);
 WriteLn(OutF, OC,' ',Cost);
 For i:=1 To OC Do
 WriteLn(OutF, OList[i].x,' ',OList[i].y,' ',OList[i].c);
 Close(OutF);
End;
Function NotEmptyVert:Boolean;
Begin
 NotEmptyVert:=Disp.VEnd>0
End;
Function NotEmptyHoriz:Boolean;
Begin
 13 Trương Nữ Thùy Duyên Các thuật toán tìm kiếm trên đồ thị và một số bài tập ứng dụng
 Q2.x:=Q2.x+N;
 PutVert(Q2);
 End;
 If G[Q3.x,Q3.y]<Visited Then
 Begin
 Q3.y:=Q3.y+M;
 PutHoriz(Q3);
 End;
 If G[Q4.x,Q4.y]<Visited Then
 PutVert(Q4);
End;
Procedure PutOut(P:Node; c:Byte);
Begin
 Inc(Cost,c);
 Inc(OC);
 OList[OC].x:=P.x; OList[OC].y:=P.y; OList[OC].c:=c;
End;
Procedure Compute;
Var
 P,Q:Node;
Begin
 MN:=M*N;
 Disp.VEnd:=0; Disp.HEnd:=MN+1;
 Cost:=0; OC:=0;
 P.x:=1; P.y:=1;
 DFS(P);
 While True Do
 Begin
 If NotEmptyVert Then
 Begin
 TakeVert(P);
 If P.x>N Then
 Begin
 P.x:=P.x-N;
 Q.x:=P.x-1;
 End Else
 Q.x:=P.x;
 If G[P.x,P.y]>=Visited Then Continue;
 Q.y:=P.y;
 PutOut(Q,1);
 DFS(P);
 End
 Else
 If NotEmptyHoriz Then
 Begin
 TakeHoriz(P);
 15 Trương Nữ Thùy Duyên