THUẬT TOÁN LOANG

Chia sẻ: Dang Quan | Ngày: | Loại File: DOC | Số trang:34

Thêm vào BST

Báo xấu

742
lượt xem 57
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật toán Loang thực chất là thuật toán tìm kiếm theo chiều rộng trên đồ thị (Breadth First Search). Để hiểu rõ bản chất của thuật toán này, ta xét bài toán ‘Thăm các đỉnh của một đồ thị’ như sau: Cho một đồ thị vô hướng G = (V,E), N đỉnh và M cạnh (số hiệu của các đỉnh là 1,2,…,N). Bây giờ ta đưa ra thứ tự duyệt các đỉnh của đồ thị đã cho theo thuật toán tìm kiếm theo chiều rộng....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: THUẬT TOÁN LOANG

THUẬT TOÁN LOANG ----------------- I) ĐẶT VẤN ĐỀ: Thuật toán Loang thực chất là thuật toán tìm kiếm theo chiều rộng trên đồ thị (Breadth First Search). Để hiểu rõ bản chất của thuật toán này, ta xét bài toán ‘Thăm các đ ỉnh c ủa một đồ thị’ như sau: Cho một đồ thị vô hướng G = (V,E), N đ ỉnh và M c ạnh (s ố hi ệu c ủa các đỉnh là 1,2,…,N). Bây giờ ta đưa ra thứ tự duyệt các đỉnh c ủa đ ồ th ị đã cho theo thu ật toán tìm kiếm theo chiều rộng; thứ tự duyệt có thể bắt đầu từ một đỉnh v nào đó. Tư tưởng của thuật toán là sử dụng cấu trúc dữ liệu kiểu hàng đợi (QUEUE - vào tr ước ra tr ước). Phần tử được nạp vào đầu tiên của QUEUE là đỉnh v. Sau đó c ứ mỗi đ ỉnh p l ấy ra kh ỏi QUEUE là ta thăm đỉnh đó đồng thời nạp vào QUEUE những đ ỉnh chung c ạnh v ới p (ch ỉ nạp vào những đỉnh chưa xét đến). Quá trình trên được lặp đi lặp l ại cho đ ến khi nào QUEUE rỗng thì dừng.  Chương trình mô phỏng: Ban đầu tất cả các đỉnh i (i = 1..n) đều đặt cờ chuaxet[i] = True. Nếu đỉnh nào xét r ồi ta đ ặt cờ của đỉnh đó sang trạng thái False. Procedure BFS(v); Tìm kiếm theo chiều rộng bắt đầu từ đỉnh v Begin ; {Khởi tạo QUEUE ban đầu là rỗng} QUEUE = QUEUE cờ của v là False} While QUEUE ≠ do Begin P
Cuoi:=Cuoi+1; {Hoặc dùng lệnh Inc(Cuoi)} Q[Cuoi]:=u; Để lấy một đỉnh p nào đó ra khỏi Q ta thực hiện: P:=Q[Dau]; Inc(Dau); Lưu ý: Ta nói lấy đỉnh p ra khỏi hàng đợi Q là lấy ra theo cơ ch ế điều khi ển ( vì bi ến Dau đã tăng lên một đơn vị qua lệnh Inc(Dau)); về mặt vật lý thì p vẫn đang nằm trong mảng Q. Như vậy ta phải hiểu rằng các phần tử trong cấu trúc hàng đợi Q là các ph ần t ử Q[Dau],..,Q[Cuoi].  Chương trình đầy đủ: Program Thamdinhdothi; Uses Crt; Const Nmax=253; fi='TKR_DT.INP'; Var f:Text; s:Char; A:Array[1..Nmax,1..Nmax] of 0..1;{Nếu có cạnh giữa đỉnh i và đỉnh j thì A[i,j]=1, ngược lại A[i,j]=0 } Chuaxet:Array[1..Nmax] of Boolean;{Cờ của các đỉnh, có trạng thái True nếu chưa xét, ngược lại False} Q:Array[1..Nmax] of Byte;{Biểu diễn hàng đợi QUEUE} N,i,dem,dau,cuoi:Byte; Procedure Doctep; Begin Assign(f,fi); Reset(f); Readln(f,N); {N:Số đỉnh của đồ thị} For i:=1 to N-1 do Begin dem:=0; While not eoln(f) do Begin Read(f,s); dem:=dem+1; If s='1' then Begin A[i,dem+i]:=1; A[dem+i,i]:=1; End; If s='0' then Begin A[i,dem+i]:=0; A[dem+i,i]:=0; End; End; Readln(f); End; Close(f); 2
End; Procedure BFS(v:Integer);{Tìm kiếm theo chiều rộng bắt đầu từ đỉnh v} Var p,u:Byte; Begin FillChar(Q,Sizeof(Q),0); {Khởi tạo tất cả các phần tử của mảng Q đều bằng 0} dau:=1; cuoi:=1; Q[cuoi]:=v; {Nạp v vao Q} Chuaxet[v]:=False; While dau cuối là Q rỗng } Begin p:=Q[dau]; dau:=dau+1; {Lấy đỉnh p ra khỏi Q } If (dau-1) mod 14 = 0 then Writeln(p:4) {In ra số hiệu đỉnh p - thao tác thăm đỉnh p} Else Write(p:4); {trên màn hình xuất hiện mỗi dòng không quá 14 số} For u:=1 to N do If (A[p,u]=1) and (Chuaxet[u]) then Begin cuoi:=cuoi+1; Q[cuoi]:=u; Chuaxet[u]:=False; End; End; End; BEGIN Clrscr; FillChar(A,Sizeof(A),0); {Khởi tạo tất cả các phần tử của mảng A đều bằng 0} Doctep; FillChar(Chuaxet,Sizeof(Chuaxet),True); {Khởi tạo cờ của tất cả các đỉnh đều ở trạng thái True - Trạng thái chưa xét} Writeln('Thu tu tham cac dinh cua do thi khi tim kiem theo chieu rong la:'); For i:=1 to N do If Chuaxet[i] then BFS(i); Writeln; Readln; END. Chương trình trên thực hiện với dữ liệu vào là tệp TKR_DT.INP có cấu trúc: - Dòng đầu tiên, được gọi là dòng 0: ghi các số nguyên dương N, x cách nhau ít nhất là một ký tự trống (N: Số đỉnh của đồ thị; x: Đỉnh xuất phát); - Trong các dòng tiếp theo: Dòng thứ i (i = 1..N-1) ghi N-i s ố 0 và 1 liên ti ếp nhau cho biết giữa đỉnh i và đỉnh j có cạnh nối với nhau hay không (j = i + 1..N). Nếu số ghi ở vị trí j- i tính từ trái sang phải trên dòng thứ i có giá trị 1 thì có c ạnh n ối gi ữa đỉnh i và đ ỉnh j, n ếu là giá trị 0 thì không có cạnh nối. Ví dụ với tệp TKR_DT.INP sau đây: 13 1 101000000010 01000000000 0001000000 011000000 10110000 3
1000001 000000 10000 0000 110 10 0 Với tệp dữ liệu vào như trên ta phải hiểu như sau: + Ở dòng 0: N=13, x=1; + Ở dòng 1: 101000000010 - giữa đỉnh 1 với đỉnh 2 có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 3 không có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 4 có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 5 không có cạnh nối với nhau .... - giữa đỉnh 1 với đỉnh 11 không có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 12 có cạnh nối với nhau - giữa đỉnh 1 với đỉnh 13 không có cạnh nối với nhau + Ở dòng 2: 01000000000 - giữa đỉnh 2 với đỉnh 3 không có cạnh nối với nhau - giữa đỉnh 2 với đỉnh 4 có cạnh nối với nhau .... + Ở dòng 11: 10 - giữa đỉnh 11 với đỉnh 12 có cạnh nối với nhau - giữa đỉnh 11 với đỉnh 13 không có cạnh nối với nhau + Ở dòng 12: 0 - giữa đỉnh 12 với đỉnh 13 không có cạnh nối với nhau Quan hệ giữa các đỉnh được mô tả qua đồ thị sau: 2 3 5 7 8 4 1 6 9 12 13 10 11 Thứ tự các đỉnh được nạp vào hàng đợi Q và lấy ra tuần tự như sau: Các phần tử Các phần tử Các phần tử Phần tử nạp vào Q có trạng thái lấy ra khỏi trong Q cờ là False Q 1 1 1 2,4,12 (Khi lấy 1 ra) 2,4,12 2,4,12 1 Không nạp phần tử nào 4,12 2 khi lấy 2 ra khỏi Q 6,7 6,7 12,6,7 4 10,11 10,11 6,7,10,11 12 5,13 5,13 7,10,11,5,13 6 3 3 10,11,5,13,3 7 4
Không nạp phần tử nào 11,5,13,3 10 khi lấy 10 ra khỏi Q Không nạp phần tử nào 5,13,3 11 khi lấy 11 ra khỏi Q 8,9 8,9 13,3,8,9 5 Không nạp phần tử nào 3,8,9 13 khi lấy 13 ra khỏi Q Không nạp phần tử nào 8,9 3 khi lấy 3 ra khỏi Q Không nạp phần tử nào 9 8 khi lấy 8 ra khỏi Q Không nạp phần tử nào Rỗng 9 khi lấy 9 ra khỏi Q Các phần tử tuần tự được lấy ra khỏi hàng đợi Q chính là các đỉnh được duyệt: 1, 2, 4, 12, 6, 7, 10, 11, 5, 13, 3, 8, 9 Qua đó cho thấy từ một đỉnh ta thăm đến các đỉnh khác liên quan đến nó theo chiều rộng. Chính vì vậy thuật toán tìm kiếm theo chiều rộng được gọi là thuật toán Loang. Lưu ý: + Với những bộ test dữ liệu bé thì ta có thể tạo một cách thủ công. Nhưng với những bộ test dữ liệu lớn thì ta phải tạo bằng chương trình. Sau đây xin giới thiệu chương trình tạo bộ test với số lượng các đỉnh của đồ thị là 253: Program Taotes_baithamdinh; Uses Crt; Const MN=253; fi='TKR_DT.INP'; Var f:Text; Procedure Gen; Var i,j:Integer; Begin Assign(f,fi); Rewrite(f); Writeln(f,MN); Randomize; For i:=1 to MN-1 do Begin For j:=1 to MN-i do Write(f,Random(2)); {Random(2) cho các giá trị ngẫu nhiên tù 0 đến 1} Writeln(f); End; Close(f); End; BEGIN Gen; END. 5
+ Đối với dữ liệu vào mà quan hệ giữa các đỉnh có dạng là m ột ma tr ận đầy đ ủ (ma tr ận đối xứng) và các số ghi trên mỗi dòng cách nhau ít nhất là m ột ký t ự tr ống thì ta thay th ủ tục đọc tệp bởi thủ tục sau đây: Procedure Doctep; Var i,j: Byte; Begin Assign(f,fi); Reset(f); Readln(f,N); For i:=1 to N do Begin For j:=1 to N do Read(f,A[i,j]); Readln(f); End; End; Bạn đọc tự viết thủ tục đọc tệp trong trường hợp dữ li ệu vào mà quan h ệ gi ữa các đ ỉnh có dạng là nữa trên hoặc nữa dưới của một ma trận đầy đủ và các số ghi trên m ỗi dòng cách nhau ít nhất là một ký tự trống hoặc liền nhau. II) CÁC BÀI TOÁN ÁP DỤNG: Bài 1: Tìm đường đi qua ít đỉnh nhất Cho đồ thị vô hướng G = (V,E) có N đỉnh và M cạnh (các đỉnh có số hi ệu là 1,2,...,N). M ối quan hệ giữa các đỉnh được cho bởi ma trận kề A[i,j]: nếu đỉnh i và đỉnh j có chung cạnh thì A[i,j] = 1, ngược lại A[i,j] = 0. Yêu cầu: 1) Tìm đường đi qua ít đỉnh nhất giữa 2 đỉnh bất kỳ nào đó của đồ thị. 2) Tìm số lượng các thành phần liên thông của đ ồ th ị (các đ ỉnh thu ộc m ột vùng liên thông nếu luôn tồn tại đường đi giữa 2 đỉnh bất kỳ trong các đỉnh đó) 6
Bàn về dung lượng bộ nhớ: Chương trình trên thực hiện với giá trị tối đa là 253 đ ỉnh c ủa đồ thị. Vậy với đồ thị có số đỉnh lớn hơn 253 thì ta giải quyết thế nào? Bài toán sau đây đưa ra một giải pháp để xử lý: Bài 2: Đường đi trong đồ thị có nhiều đỉnh Cho một đồ thị vô hướng có N đỉnh (N
Nhìn dạng bài toán, chúng ta nhận thấy ngay thuật toán tối ưu để xử lý là thuật toán Loang. Nhưng vì số đỉnh của đồ thị nằm trong phạm vi quá lớn (N
Inc(dau); Để nạp đỉnh v vào hàng đợi ta thực hiện: Inc(cuoi); Str(cuoi,s); Assign(f,s+que); Rewrite(f); Writeln(f,v); Close(f); Toàn văn chương trình: {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+} {$M 16384,0,655360} Program Timduongdivoisodinhlon; Uses Crt; Const fi='dothi.inp'; fo='dothi.out'; ke='.ke'; que='.que'; dd='.dd'; tr='.tr'; kq='.kq'; Var n,x,y:Longint; time:longint; {Để phục vụ tính thời gian chạy chương trình} f,f1,f2,f3:Text; Procedure Doctep; Var i,u,v:Longint; s:string; Begin Assign(f,fi); Reset(f); Readln(f,n,x,y); For i:=1 to N do Begin Str(i,s); {Thủ tục đổi số u thành dạng ký tự s của nó} Assign(f1,s+ke); Rewrite(f1); Close(f1); Assign(f1,s+tr); Rewrite(f1); Write(f1,0); Close(f1); End; While not seekeof(f) do {Nếu con trỏ tệp chưa di chuyển đến cuối tệp} Begin Readln(f,u,v); Str(u,s); Assign(f1,s+ke); Append(f1); 9
Writeln(f1,v); Close(f1); Assign(f1,s+dd); Rewrite(f1); Writeln(f1,0); Close(f1); Str(v,s); Assign(f1,s+dd); Rewrite(f1); Write(f1,0); Close(f1); End; Close(f); End; Procedure Loang; Var u,v,dau,cuoi:Longint; s1,s2,s3:String; ok:Byte; Begin dau:=1; cuoi:=1; Str(x,s1); Assign(f,s1+dd); Rewrite(f); Write(f,1); {Đánh đấu đỉnh x} Close(f); Assign(f,s1+tr); Rewrite(f); Writeln(f,0); Close(f); Assign(f,'1'+que); Rewrite(f); Writeln(f,x); Close(f); While dau
Reset(f1); Readln(f1,ok); {Kiểm tra xem v đã bị đánh dấu hay chưa} Close(f1); If ok=0 then Begin Assign(f1,s2+dd); Rewrite(f1); Writeln(f1,1); {Đánh dấu v} Close(f1); Inc(cuoi); Str(cuoi,s3); Assign(f2,s3+que); Rewrite(f2); Writeln(f2,v); {Nạp v vào hàng đợi} Close(f2); Assign(f2,s2+tr); Rewrite(f2); Writeln(f2,u); {Lưu lại đỉnh trước của v} Close(f2); End; End; Close(f); End; End; Procedure Ketqua; Var i,t,dem:Longint; s,s1:String; Begin Assign(f,fo); Rewrite(f); Str(y,s); Assign(f1,s+tr); Reset(f1); Read(f1,t); Close(f1); Assign(f1,'1'+kq); Rewrite(f1); Write(f1,y); {Ghi số y vào tệp 1.kq} Close(f1); If t=0 then Write(f,'Khong ton tai duong di') Else Begin i:=t; dem:=1; While ix do Begin Inc(dem); Str(dem,s1); Assign(f1,s1+kq); Rewrite(f1); 11
Writeln(f1,i); Close(f1); Str(i,s1); Assign(f1,s1+tr); Reset(f1); Read(f1,i); Close(f1); End; Inc(dem); Str(dem,s1); Assign(f1,s1+kq); Rewrite(f1); Writeln(f1,i); Close(f1); For i:=dem downto 1 do Begin Str(i,s1); Assign(f1,s1+kq); Reset(f1); Read(f1,t); Close(f1); Writeln(f,t); End; End; Close(f); End; BEGIN Clrscr; time:=MemL[0:$46C]; {Mốc thời gian bắt đầu chạy chương trình} Doctep; Loang; Ketqua; Writeln((MemL[0:$46C] - time)/18.21:10:10); {Thời gian chạy chương trình} END. Lưu ý: + Vì khi chương trình trên thực hiện với bộ dữ liệu lớn thì sẽ t ạo ra r ất nhi ều t ệp văn b ản, mà những tệp này đến một lúc nào đó ta phải xoá đi để m ở rộng không gian l ưu tr ữ cho thiết bị nhớ. Bởi vậy khi cài đặt nên tạo ra một thư m ục để chứa các tệp văn bản đó (khi cần xoá, ta xoá cả thư mục hoặc tất cả các tệp trong thư mục đó). Bạn đọc có thể sử d ụng thêm một biến kiểu String chứa đường dẫn để thay đổi một số câu lệnh trong chương trình trên sao cho việc tạo hoặc truy cập các tệp văn bản cho đúng theo thư mục đã tạo. + Ta có thể tham khảo chương trình sau đây để tạo các bộ test dữ liệu lớn: Program Taotes_duongdivoisodinhlon; Uses Crt; Const MN=500000; fi='dothi.inp'; Var f:Text; x,xn,yd:Longint; 12
Procedure Gen; Var i,j:Longint; Begin Assign(f,fi); Rewrite(f); Randomize; xn:=Random(MN+1); If xn=0 then While xn=0 do xn:=Random(MN+1); yd:=Random(MN+1); If (yd=0) or (yd=xn) then While (yd=0) or (yd=xn) do yd:=Random(MN+1); Writeln(f,MN,’ ‘,xn,’ ‘,yd); For i:=1 to MN do Begin x:=Random(MN); If x=i then While x=i do x:=Random(MN); If x0 then Begin For j:=1 to x do Writeln(f,i,’ ‘,x); For j:=1 to x do Writeln(f,x,’ ‘,i); End; End; Close(f); End; BEGIN Repeat Gen; Writeln(‘Hai đinh can tim duong di la:’,xn,’ ‘,yd); Until Readkey = #27; {Khi nào thấy đạt yêu cầu rồi thì ấn phím ESC để dừng} END. + Nếu yêu cầu dữ liệu ra là tệp văn bản như trên nhưng dòng đ ầu tiên ghi s ố l ượng đ ỉnh trong đường đi tìm được thì ta xử lý thế nào? Bạn đọc tự giải quyết, coi nh ư là m ột bài tập. Bài 4: Otomat Có một Otomat được ghép từ các chi tiết có một trong hai tr ạng thái 0 ho ặc 1 nh ư hình 1. Otomat có cấu trúc như hình 2 gồm 8 chi tiết G1, G2,..., G8 v ới 3 l ối vào A,B,C. M ỗi tr ạng thái của Otomat được được thể hiện bởi xâu nhị phân độ dài 8 là các trạng thái tương ứng của G1, G2,...,G8. Trạng thái 1 Trạng thái 0 13
Hình 1 A B C G1 G2 G3 G4 G5 G6 G7 G8 Hình 2 Otomat hoạt động như sau: Khi thả một quả cầu vào một lối vào nào đó, sau khi quả cầu đi từ một chi tiết nào đó, chi tiết đó thay đổi trạng thái từ 0 thành 1 ho ặc t ừ 1 thành 0. Ho ạt động của Otomat được thể hiện bởi một xâu ký tự S chỉ gồm các chữ cái in hoa A, B, C mà mỗi ký tự trong xâu S thể hiện việc quả cầu vào lối vào với tên ký tự đó. Ví dụ: S=AABC có nghĩa là ta lần lượt thả quả cầu vào các lối A, A, B, C. Bài toán đặt ra như sau: Cho hai trạng thái bất kỳ T1, T2 của Otomat. Hãy tìm m ột ký t ự S ngắn nhất có thể được thể hiện hoạt động của Otomat chuyển từ trạng thái T1 đ ến tr ạng thái T2. Dữ liệu vào là tệp otomat.inp cócấu trúc: - Dòng thứ nhất ghi 8 số 0 và 1 biểu diễn trạng thái T1; - Dòng thứ hai ghi 8 số 0 và 1 biểu diễn trạng thái T2; Các số trên mỗi dòng được ghi liên tiếp nhau. Dữ liệu ra là tệp otomat.out ghi xâu ký tự S tìm được. N ếu không tìm đ ược xâu S thì ghi ký tự ‘#’. Ví dụ: Otomat.inp Otomat.out Otomat.inp Otomat.out 10011010 AAABBC 00010010 # 00101001 00101001 Phân tích: {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+} {$M 16384,0,655360} Program OTOMAT; Uses Crt; Const Nmax=256; fi='otomat.inp'; 14
fo='otomat.out'; Type otomat=String[8]; Var f:Text; S:string; T1,T2,O:otomat; i,dau,cuoi,dem:Integer; Q:Array[1..Nmax] of otomat; truoc:Array[1..Nmax] of Integer; Procedure Doctep; Begin Assign(f,fi); Reset(f); Readln(f,T1); Readln(f,T2); Close(f); End; Function Ktra(T:otomat;N:integer):Boolean; Var j:Integer; Begin Ktra:=True; For j:=1 to N do If T=Q[j] then Begin Ktra:=False; Exit; End; End; Function Tha_A(T:otomat):otomat; Begin If T[1]='0' then Begin T[1]:='1'; If T[6]='0' then T[6]:='1' else T[6]:='0'; End else {T[1]='1'} Begin T[1]:='0'; If T[4]='0' then Begin T[4]:='1'; If T[6]='0' then T[6]:='1' else T[6]:='0'; End else {T[4]='1'} Begin T[4]:='0'; If T[7]='0' then T[7]:='1' 15
else T[7]:='0'; End; End; Tha_A:=T; End; Function Tha_B(T:otomat):otomat; Begin If T[2]='0' then Begin T[2]:='1'; If T[4]='0' then Begin T[4]:='1'; If T[6]='0' then T[6]:='1' Else T[6]:='0'; End Else {T[4]='1'} Begin T[4]:='0'; If T[7]='0' then T[7]:='1' Else T[7]:='0'; End; End Else {T[2]='1'} Begin T[2]:='0'; If T[5]='0' then Begin T[5]:='1'; If T[7]='0' then T[7]:='1' else T[7]:='0'; End Else {T[5]='1'} Begin T[5]:='0'; If T[8]='0' then T[8]:='1' else T[8]:='0'; End; End; Tha_B:=T; End; Function Tha_C(T:otomat):otomat; Begin If T[3]='0' then Begin T[3]:='1'; If T[5]='0' then Begin T[5]:='1'; If T[7]='0' then T[7]:='1' else T[7]:='0' 16
End Else {T[5]='1'} Begin T[5]:='0'; If T[8]='0' then T[8]:='1' else T[8]:='0'; End; End Else {T[3]='1'} Begin T[3]:='0'; If T[8]='0' then T[8]:='1' else T[8]:='0'; End; Tha_C:=T; End; Procedure Loang(T:otomat); Var p:otomat; Begin dau:=1; cuoi:=1; Q[cuoi]:=T; While dau0 then Begin 17
l:=truoc[v]; Ketqua(l); Write(f,s[v]) End; End; BEGIN FillChar(truoc,Sizeof(truoc),0); Doctep; Loang(T1); Assign(f,fo); Rewrite(f); If OT2 then Writeln(f,'#') Else Ketqua(cuoi); Close(f); END. Bài 5: Máy đổi thẻ tự động Có một máy giải trí tự động có M cửa dùng để đổi thẻ. Có các th ẻ mã s ố t ừ 1,..,N. N ếu ta bỏ thẻ có mã số i vào một cửa nào đó thì máy sẽ thu th ẻ đó và cho ra m ột th ẻ có mã s ố nào đó trong khoảng 1..N. Máy đổi thẻ hoạt động theo thông tin ghi trong tệp văn bản the.inp : - Dòng đầu tiên ghi các số N, M; - N dòng tiếp theo, mỗi dòng chứa M số tạo thành một bảng có kích th ước N x M. Phần tử nằm trên dòng i, cột j của bảng này cho biết nếu ta bỏ thẻ có số hiệu i vào c ửa j thì s ẽ thu được thẻ có số hiệu chính là giá trị của phần tử đó. Các số trên mỗi dòng của tệp ghi cách nhau ít nhất là một ký tự trống. Yêu cầu: Với mỗi cặp thẻ có số hiệu x và y cho trước (xy), hãy cho bi ết có cách nào nhanh nhất để dùng thẻ có số hiệu x thu được thẻ có số hiệu y hay không? Dữ liệu ra là tệp văn bản the.out trình bày theo dạng: Bỏ thẻ x vào cửa ... thu được thẻ ... ......... Bỏ thẻ ... vào cửa ... thu được thẻ y Nếu không tìm được cách để từ thẻ có số hiệu x thu được thẻ có số hi ệu y thì ghi vào tệp thông báo ‘Tu the x khong thu duoc the y’. Ví dụ: Tệp Tệp Tệp Tệp Doithe.inp Doithe.out Doithe.inp Doithe.out 5421 Bo the 2 vao cua 1 thu duoc the 3 5 4 4 5 Tu the 4 khong thu duoc the 5 Bo the 3 vao cua 1 thu duoc the 1 2 2 2 4 2351 3443 1444 1524 1524 5321 1122 3424 3424 Phân tích: Bài toán trên thuộc lớp các bài toán biến đổi trạng thái. Hơn nữa yêu cầu tìm kết quả qua ít bước thao tác nhất nên ta sử dụng thuật toán Loang là thích hợp nhất. Cụ thể như sau: Ta sử dụng ma trận A[i,j] (i = 1..N, j = 1...M) để lưu giữ thông tin quan hệ giữa thẻ - cửa đã cho trong tệp dữ liệu vào. Ta phải hiểu: Bỏ thẻ i vào cửa j thu được thẻ A[i,j]. Cấu trúc dữ liệu hàng đợi được biểu diễn bởi mảng một chiều Q. 18
Ta phải tìm các thao tác sao cho từ thẻ x thu được thẻ y một cách nhanh nhất. Đầu tiên ta cho thẻ x vào Q. Cứ mỗi lần lấy một thẻ p ra từ Q ta lại n ạp vào Q nh ững th ẻ có th ể thu đ ược t ừ th ẻ p (ch ỉ nạp những thẻ chưa có trong Q, hàm vitri(v) cho biết thẻ v có ở trong Q hay không: Giá tr ị của hàm bằng 0 thì thẻ v chưa có trong Q, ngược lại thì đã có). Khi nạp một thẻ vào Q ta phải lưu giữ thông tin thẻ đó có được từ thẻ nào và b ỏ vào c ửa nào để sau này truy xuất kết quả (mảng một chiều TRUOC có nhiệm vụ đó). Quá trình trên lặp đi lặp lại cho đến khi hàng đợi Q rỗng (dau > cuoi) Kết thúc quá trình ‘Loang’, dựa vào mảng TRUOC ta truy xuất kết quả bằng th ủ tục đ ệ quy Ketqua(y). Khi truy xuất kết quả ta phải hiểu rằng nếy TRUOC[y].the = 0 thì có nghiã là th ẻ y không thu được từ một thẻ nào cả. Lưu ý: một thẻ i bỏ vào một của j nào đó thì vẫn có thể thu được thẻ i. Sau đây là toàn văn chương trình: {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+} {$M 16384,0,655360} Program Doithe;{ Thuat toan Loang} Uses Crt; Const Mmax=200; Nmax=200; fi='the.inp'; fo='the.out'; Type rc=record the,cua:byte; End; Var A:Array[1..Nmax,1..Mmax] of Byte; {Quan hệ Thẻ - Cửa} Q:Array[1..Nmax] of Byte; {Hàng đợi - chứa các thẻ thu được từ thẻ x} truoc:Array[1..Nmax] of rc; N,M,x,y,i,j,dau,cuoi:Byte; f:Text; Procedure Doctep; Begin Assign(f,fi); Reset(f); Readln(f,N,M,x,y); For i:=1 to N do Begin For j:=1 to M do Read(f,A[i,j]); Readln(f); End; End; Function Vitri(v:Byte):Integer; Var l:Byte; Begin vitri:=0; 19
For l:=cuoi downto 1 do If v=Q[l] then Begin vitri:=l; exit; End; End; Procedure Loang; Var p:Byte; Begin dau:=1; cuoi:=1; Q[cuoi]:=x; {Nap x vao Q} While dau