Tài liệu Thuật toán qui hoạch động

Nội dung text: Tài liệu Thuật toán qui hoạch động

1. TÀI LIỆU THUẬT TOÁN QUI HOẠCH ĐỘNG
2. MỤC LỤC MỤC LỤC 2 Thuật toán qui hoạch động 3 Thuật toán quy hoạch động trên mảng một chiều 8 Giải thuật quy hoạch động 14 Phương pháp quy hoạch động 25 Thuật toán Dijkstra trên cấu trúc Heap 28 Dijtra - thuật toán tốt để giải các bài toán tối ưu 38 Kỹ thuật tìm kiếm nhị phân giải một số bài toán tối ưu 43 Quan hệ sinh dữ liệu và tiếp cận Quy hoạch động 89 Chia sẻ một thuật toán hay 93 Tìm kiếm ưu tiên chiều rộng - Một số bài tập áp dụng 97 Kỹ năng tối ưu hoá thuật toán 104 Ứng dụng phương pháp quy nạp toán học 109 Bàn về một bài toán hay 114 Phương pháp quy hoạch động 116 Thuật toán quy hoạch động 120 Cùng trao đổi về đề thi chọn học sinh giỏi quốc gia - Bảng B năm 2002-2003 122 Kỳ thi chọn học sinh giỏi quốc gia - Tin học Bảng A 126 Hội thi Tin học trẻ không chuyên toàn quốc lần thứ XI 130 Hội thi Tin học trẻ không chuyên toàn quốc 133 Nhận xét - Hướng dẫn - Lời giải 135 Các kỳ thi Tin học trên thế giới 139
3. Thuật toán qui hoạch động Bá Hiệp Trong quá trình học tập, chúng ta gặp rất nhiều các bài tập về Toán-Tin. Các bài tập dạng này rất phong phú và đa dạng. Thực tế chưa có thuật toán hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên người ta đã tìm ra một số thuật toán chung như chia để trị, tham ăn, quay lui, Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Trong bài viết này, tôi muốn đề cập với các bạn một thuật toán khác, đó là thuật toán quy hoạch động. Tư tưởng cơ bản của thuật toán là: Để giải một bài toán ta chia bài toán đó thành các bài toán nhỏ hơn có thể giải một cách dễ dàng. Sau đó kết hợp lời giải các bài toán con, ta có được lời giải bài toán ban đầu. Trong quá trình giải các bài toán con đôi khi ta gặp rất nhiều kết quả trùng lặp của các bài toán con. Để tăng tính hiệu quả, thay vì phải tính lại các kết quả đó, ta lưu chúng vào một bảng. Khi cần lời giải của một bài toán con nào đó ta chỉ cần tim trong bảng, không cần tính lại. Tư tưởng của thuật toán quy hoạch động khá đơn giản. Tuy nhiên khi áp dụng thuật toán vào trường hợp cụ thể lại không dễ dàng (điều này cũng tương tự như nguyên tắc Dirichlet trong toán vậy). Khi giải bài toán bằng phương pháp này, chúng ta phải thực hiện hai yêu cầu quan trọng sau: - Tìm công thức truy hồi xác định nghiệm bài toán qua nghiệm các bài toán con nhỏ hơn. - Với mỗi bài toán cụ thể, ta đề ra phương án lưu trữ nghiệm một cách hợp lý để từ đó có thể truy cập một cách thuận tiện nhất. Để minh hoạ thuật toán, ta xét một vài ví dụ. Ví dụ 1:Cho hai dãy số nguyên (a1,a2, ,am), (b1,b2, ,bn). Tìm dãy con chung có độ dài lớn nhất của hai dãy trên (coi dãy không có số nguyên nào là dãy con của mọi dãy và có độ dài bằng 0). Lời giải Chúng ta có thể thấy ngay rằng độ phức tạp của bài toán trên phụ thuộc vào hai số m, n. Xét hai trường hợp: +Trường hợp1: m=0 hoặc n=0. Đây là trường hợp đặc biệt, có duy nhất một dãy con chung của hai dãy có độ dài? bằng 0. Vì vậy dãy con chung có độ dài lớn nhất của chúng có độ dài bằng 0. +Trường hợp 2: m 0 và n 0.
4. Trong trường hợp này, ta xét các bài toán nhỏ hơn là tìm dãy con chung có độ dài lớn nhất của hai dãy (a1,a2, ,ai), (b1,b2, ,bj) với 0 ≤ i ≤ m, 0 ≤ j ≤ n. Go.i l[i,j] là độ dài của dãy con chung lớn nhất của hai dãy (a1, ,ai), (b1, ,bj). ; Như vậy ta phải tính tất cả các l[i,j] trong đó 0 -Nếu ii bj thì l[i,j]=max{l[i-1,j], l[i,j-1]}. -Nếu ii =Bj thì l[i,j]= 1+l[i-1,j-1]. Với những nhận xét trên, ta hoàn toàn tính được l[m,n] chính là độ dài dãy con chung dài nhất của (a1, am), (b1, bn). Để tìm phần tử của dãy con, ta xuất phát từ ô l[m,n] tới ô l[0,0]. Giả sử ta đang ở ô l[i,j]. Nếu ai =Bj thì ta thêm ai vào dãy con rồi nhảy tới ô l[i-1,j-1]. Nếu aibj thì l[i,j]=l[i-1,j] hoặc l[i,j]=l[i,j-1]. Nếu l[i,j]=l[i-1,j] thì nhảy tới ô l[i-1,j], ngược lại thì nhảy tới ô l[i,j-1]. Sau đây là lời giải của bài toán. Chương trình được viết bằng ngôn ngữ Pascal: uses crt; const fi='b2.inp'; var a:array[1 10] of integer; b:array[1 10] of integer; kq:array[0 10,0 10] of integer; i,j,maxa,maxb:integer; f:text; procedure init; begin assign(f,fi);reset(f);i:=0; while not(eoln(f)) do begin inc(i);read(f,a[i]);end;maxa:=i; readln(f);i:=0; while not(eoln(f)) do begin inc(i);read(f,b[i]);end;maxb:=i;
5. close(f); end; function max(a,b:integer):integer; begin if a>b then max:=a else max:=b; end; begin init; kq[0,0]:=0; for i:=1 to maxa do for j:=1 to maxb do if a[i] 0)or(j>0) do if a[i]=b[j] then begin write(a[i]);dec(i);dec(j);end else if kq[i-1,j]=kq[i,j] then dec(i) else dec(j); end. Với nội dung file?b2.inp? chứa 2 dãy (a1,a2, am) ,(b1,b2, bn) sau: 1 2 3 2 3 4 6 6 9 8 7 Xét bài toán kinh điển về tối ưu tổ hợp: Ví dụ 2:Cho cái túi chứa được trọng lượng tối đa là w. Có n đồ vật, đồ vật thứ i có khối lượng a[i] và giá trị c[i], 1≤ i ≤n. Tìm cách xếp đồ vật vào túi sao cho đạt giá trị lớn nhất.
6. Lời giải Gọi f(k,v) là giá trị lớn nhất của túi đựng trọng lượng v và chỉ chứa các đồ vật từ 1 đến k. Nếu k=1 thì f(k,v)=(v div a[1])*c[1]. Giả sử tính được f(s,t) với 1 Đặt: tg=v div a[k], f(k,v)=max{f(k-1,u)+x*c[k]}? (*) ,với x=0,1,2, ,tg, u=v-x*a[k] Giá trị lớn nhất là f(n,w). Ta dùng mảng bản ghi a[1 n,1 w] chứa kết quả trung gian. Mỗi bản ghi a[k,v] chứa giá trị f(k,v) và giá trị x thoả mãn công thức (*). Để xác định số lượng x[i] đồ vật i thoả mãn điều kiện tối ưu, ta xuất phát từ a[n,w] xác định được x[n]. Nhảy tới a[n-1,w-x[n]*a[n]] xác định được x[n-1]. Cứ như vậy tới x[1]. Sau đây là lời giải, chương trình được viết bằng ngôn ngữ Pascal: uses crt; const n=5;w=17; fi='b3.inp'; type kq=record num,val:integer; end; var a:array[1 10] of integer;{khoi luong} c:array[1 10] of integer;{Gia tri} i,j,tg,k,max,save:integer; f:text; b:array[1 n,1 w] of kq; procedure init; begin assign(f,fi);reset(f);
7. for i:=1 to n do begin read(f,a[i],c[i]);end; close(f); end; begin init; for j:=1 to w do? for i:=1 to n do begin tg:=j div a[i];max:=0; for k:=0 to tg do if (b[i-1,j-k*a[i]].val+k*c[i])>max then begin max:=b[i-1,j-k*a[i]].val+k*c[i];save:=k;end; b[i,j].val:=max; b[i,j].val:=max; b[i,j].num:=save; for i:=1 to n do begin for j:=1 to w do write(b[i,j].val:3); writeln; end; writeln('Max:',b[n,w].val); i:=n;j:=w; while i>=1 do begin if b[i,j].num>0 then writeln('Co ',b[i,j].num,' do vat ',i);
8. j:=j-a[i]*b[i,j].num;dec(i); end; readln; end. Với nội dung file?b3.inp? :hàng i chứa khối lượng a[i], giá trị c[i]: 3 4 4 5 7 10 8 11 9 13 Qua hai ví dụ trên chắc các bạn đã nắm được tư tưởng của thuật toán qui hoạch động cũng ; như cách cài đặt cho nó. ; Như các bạn thấy, cách phát biểu thuật toán rất đơn giản. Nếu biết cách vận dụng thuật toán một cách hợp lý, ta có thể giải được một lớp khá rộng các bài toán trong thực tế. Hi vọng thuật toán sẽ là công cụ tốt của các bạn trong quá trình học tập môn tin học. Chúc các bạn thành công. Bá Hiệp Thuật toán quy hoạch động trên mảng một chiều Trần Minh Quang Bài toán 1: Cho một dãy số nguyên dương a1, a2, aN. Hãy tỉa bớt một số ít nhất các phần tử của dãy số nguyên đó và giữ nguyên thứ tự các phần tử còn lại sao cho dãy số còn lại là một dãy tăng dần. Ta gọi dãy số nguyên tăng dần còn lại sau khi đã tỉa bớt một số phần tử là dãy con của dãy đã cho. Input: Dữ liệu vào được cho bởi tệp văn bản với quy cách: - Dòng đầu ghi số N là số phần tử - Dòng tiếp theo ghi N số là các số nguyên của dãy. Output:
9. -Ghi ra màn hình: Số lượng phần tử của dãy con cực đại và chỉ số các phần tử trong dãy con đó (theo thứ tự tăng dần). Ví dụ: - Với Input trong file DAYSO.INP như sau: 10 10 100 20 1 2 50 70 80 3 60 - thì Output phải là: 1 2 50 70 80 ý tưởng của thuật toán quy hoạch động ở đây là: Để xây dựng dãy con dài nhất của dãy đã cho chúng ta sẽ xây dựng dãy con dài nhất của đoạn phần tử đầu a1, a2, ai. Để làm được điều đó: ta gọi S[i] là số lượng phần tử nhiều nhất của dãy con tăng dần, trong đó ai cũng thuộc dãy con trên (nó là phần tử cuối cùng). Chúng ta sẽ tính S[i] ở từng bước dựa vào các S[i-1], S[1] như sau: Ban đầu S[i] với i = 1, 2, N được gán bằng 1 vì trường hợp xấu nhất thì dãy con chỉ là một phần tử. Với mỗi i >= 2 thì S[i] được tính bằng công thức truy hồi sau: S[i]:=Max(S[j]+1) với j=i-1, 1 mà aj < ai. Để lấy lại dãy con cực đại ta dùng một mảng Truoc với ý nghĩa: Truoc[i] là chỉ số của phần tử trước phần tử i trong dãy con cực đại lấy trong dãy a1,a2, ai. Bây giờ chúng ta phải tìm vị trí i sao cho S[i] đạt max. Ta lưu vị trí đó vào biến Luu. Như vậy: S[Luu] chính là số lượng phần tử của dãy con cực đại của dãy đã cho. Và bằng mảng Truoc ta có thể lấy lại chỉ số các phần tử thuộc dãy con đó. Đến đây ta gặp một vấn đề: Mảng Truoc chỉ cho phép ta lần ngược từ cuối về đầu dó đó để in ra các chỉ số theo thứ tự tăng dần ta phải dùng thêm một mảng phụ P và in ngược lại của mảng P: dem:=0; i:=Luu;
10. While i 0 then Begin Print(Truoc[i]);Write(i,' '); End; End; Công việc in ra chỉ cần một lời gọi: Print(Luu); Ta có 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+,Y+} {$M 65500,0,655360} Uses Crt; Const fi = 'DAYSO.INP'; MaxN=5000; Var A : Array[1 MaxN] of Integer; S : Array[1 MaxN] of Integer;
11. Truoc : Array[1 MaxN] of Integer; i,j,Luu : Word; N : Word; Procedure Init; Begin Fillchar(S,SizeOf(S),1); Fillchar(Truoc,SizeOf(Truoc),0); End; Procedure Readfile; Var f:Text; Begin Assign(f,fi); Reset(f); Readln(f,N); For i:=1 to N do Read(f,A[i]); Close(f); End; Procedure Find; Begin For i:=2 to N do Begin For j:=i-1 downto 1 do If (A[j]< (S[i]
12. Begin S[i]:=S[j]+1; Truoc[i]:=j; End; End; End; Procedure Print(i:Word); Begin If i >0 then Begin Print(Truoc[i]); Write(a[i],' '); End; End; Procedure OutputResult; Begin Luu:=N; For i:=N-1 downto 1 do If S[i]>S[Luu] then Luu:=i; Print(Luu); End; BEGIN Clrscr;
13. Init; Readfile; Find; OutputResult; Readln; END. Qua ví dụ trên chúng ta đã hiểu cách mà thuật toán thể hiện. Bây giờ chúng ta sẽ xét tiếp một bài toán sắp xếp trình tự phục vụ khách hàng mà cách giải đều sử dụng thuật toán Quy hoạch động trên mảng một chiều. Ta xét tiếp một ví dụ sau: Bài toán 2: Tại thời điểm 0, ông chủ một máy tính hiệu năng cao nhận được đơn đặt hàng thuê sử dụng máy của n khách hàng. Các khách hàng được đánh số từ 1 đến n. Khách hàng i cần sử dụng máy từ thời điểm di đến thời điểm ci (di, ci là các số nguyên và 0 < di < ci < 1000000000) và sẽ trả tiền sử dụng máy là pi (pi nguyên, 0 < p i ≤ 10000000). Bạn cần xác định xem ông chủ cần nhận phục vụ những khách hàng nào sao cho khoảng thời gian sử dụng máy của hai khách được nhận phục vụ bất kỳ không được giao nhau đồng thời tổng tiền thu được từ việc phục vụ họ là lớn nhất. Dữ liệu vào: Từ file văn bản THUE.INP Dòng đầu tiên ghi số n (0 < n =< 1000); - Dòng thứ i+1 trong số n dòng tiếp theo ghi 3 số di, ci, pi cách nhau bởi dấu trắng (i = 1, 2, n). Kết quả: Ghi ra file văn bản THUE.OUT -Dòng đầu tiên ghi hai số nguyên dương theo thứ tự là số lượng khách hàng nhận phục vụ và tổng tiền thu được từ việc phục vụ họ. -Dòng tiếp theo ghi chỉ số của các khách hàng được nhận phục vụ. Ví dụ: THUE.INP THUE.OUT THUE.INP THUE.OUT 3 2 180 4 2 1100 2 3 2 4
14. 150 500 150 400 821 800 1 200 100 200 513 500 400 800 80 100 325 200 600 900 600 Bài toán này chúng ta phải chú ý ở chỗ: Để dùng thuật toán Quy hoạch động tối ưu từng bước thì trước hết chúng ta phải sắp xếp các ci theo thứ tự tăng dần: Giả sử c1 ≤ c2 ≤ ≤ cN. Tương tự bài toán trên: Gọi F[k] là số tiền lớn nhất khi phục vụ một số khách hàng từ 1 đến k. Với mỗi F[k] ta có: - Nếu chấp nhận phục vụ khách k thì F[k]:=F[t]+pk (với t là chỉ số max thoả mãn khoảng thời gian [dt, ct [dk,ck] = ). - Nếu không chấp nhận phục vụ k thì F[k]:=F[k-1]. Như vậy hàm quy hoạch động của F[k] sẽ là: F[k]:=Max{F[t]+pk ,F[k-1]} với k = 2, 3, N và t có ý nghĩa như trên. Để lấy lại chỉ số các khách hàng được phục vụ chúng ta lại dùng mảng Truoc như ví dụ trên. Trên đây là những gì tôi muốn trình bày với các bạn. Theo tôi, thuật toán tuy đơn giản nhưng tầm ứng dụng của nó rất phong phú mà nếu nắm vững nó là rất có lợi cho tư tưởng thuật toán của các bạn. Giải thuật quy hoạch động CongHiep_87@yahoọcom Đối với các bạn yêu thích môn lập trình thì có lẽ giải thuật qui hoạch động tương đối quen thuộc trong việc giải quyết các vấn đề tin học. Tuy nhiên, sẽ thật là khó để có thể tìm được cơ cở và công thức cho việc sử dụng qui hoạch động. Chính vì vấn đề này, qui hoach động lại trở thành không phổ biến. Đối với những bài toán như vậy, chúng ta lại cố gắng đi tìm cách giải khác ví dụ như vét cạn hay tham lam điều đó thật là dở! Chính vì vậy, tôi muốn đưa ra một số bài toán áp dụng qui hoạch động
15. để mong rằng sau bài báo này, các bạn sẽ yêu thích giải thuật này hơn. Trước hết các bạn phải luôn nhớ rằng, giải thuật qui hoạch động được xuất phát từ nguyên lí Bellman: nếu 1 cấu hình là tối ưu thì mọi cấu hình con của nó cũng là tối ưu. Chính vì vậy để xây dựng 1 cấu hình tối ưu, ta hãy xây dựng dần các cấu hình con sao cho các cấu hình con này cũng phải tối ưu Đây chính là đường lối chủ đạo cho mọi bài toán qui hoạch động. Sau đây là một số bài toán được giải quyết bằng qui hoạch động. I. Các bài toán Bài 1: Trước tiên chúng ta hãy xét 1 bài toán thật đơn giản và quen thuộc đó là tìm giá trị lớn nhất trong n số là a1, a2, , an. Giải quyết bài toán này, ta sẽ xây dựng các cấu hình con tối ưu bằng cách lần lượt tìm số lớn nhất trong k số đầu tiên với k chạy từ 1 đến n: K=1: max1:=a1; K=2: max2:=max(max1,a2); K=3: max3:=max(max2,a3); K=n: maxn:=max(maxn-1,an); Như vậy khi k đạt tới n thì maxn chính là giá trị lớn nhất trong n số đã chọ Việc cài đặt chương trình hết sức đơn giản như sau: Uses crt; Var a: array[1 100] of integer; n,k,max: integer; Begin Write('Cho so luong phan tu: ');readln(n); For i:=1 to n do begin write('a[',i,']= ');readln(a[i]);end; Max:=a[1]; For k:=2 to n do If a[k]>max then max:=a[k]; Write('Gia tri lon nhat cua day cac so da cho la: ',max); Readln End. Bây giờ chúng ta xét đến bài toán 2 có phần hấp dẫn hơn. Đây chính là một trong những bài toán điển hình cho giải thuật qui hoạch động: Bài 2: Bài toán cái túi: Cho n loại đồ vật (1≤n≤100) với một đồ vật loại thứ i (1≤i≤n) có trọng lượng là a[i] và giá trị sử dụng là c[i]. Một nhà thám hiểm cần mang theo một số đồ vật vào túi của mình sao cho tổng trọng lượng các đồ vật đem theo không vượt quá sức chịu đựng của túi là w (1≤w≤250) và tổng giá trị sử dụng từ các đồ vật đem theo là lớn nhất. Hãy tìm một phương án mang cho nhà thám hiểm với giả sử rằng số lượng đồ vật của mỗi loại là luôn đủ dùng. * Thuật giải bằng qui hoạch động được mô tả như sau: Ta xây dựng một mảng 2 chiều f với f[i,j] là giá trị sử dụng lớn nhất có được bởi j vật từ 1 đến j mà tổng trọng lượng không vượt quá j. Khởi tạo : f[i,1]:=0 với i =a[1]; (i = 1 w); Ta lần lượt cho i đạt tới w và j đạt tới n bằng cách sau: For j:=2 to n do
16. For i:=1 to w do If i >= a[i] then f[i,j]:=Max(f[i-a[j],j]+ c[j],f[i-1,j]) Else f[i,j]:=f[i-1,j]. Như vậy cho đến f[w,n] ta sẽ thu được giá trị lớn nhất có thể đạt được từ n loại đồ vật đã cho sao cho trọng lượng không vượt quá w. Hệ thức toán trên được gọi là hệ thức Dantzig. Có thể rất dễ hiểu được thuật toán như sau: Phần khởi tạo: f[i,1] có nghĩa là giá trị lớn nhất nếu chỉ có 1 loại vật (ở đây là vật 1) mà trọng lượng không quá ị Như vậy nếu i f[i,j] then f[i,j]:=(value[j]+f[i-weight[j],j]); end; end; ( }
17. Procedure Print_rerult; Var i:byte; Begin write('* Gia tri cao nhat dat duoc la: ',f[w,sl]);writeln; End; ( ) Begin Init; Solve; Print_result; Readln; End. Chú ý: chương trình trên được đọc dữ liệu từ file. II. Vấn đề công thức truy hồi Đối với một bài toán qui hoạch động thì công thức truy hồi cũng là một phần rất quan trọng. Nếu chúng ta chỉ xây dựng được giá trị tối ưu thì đôi khi vẫn là chưa đủ. Vấn đề được đặt ra là làm thế nào để xác định được cấu hình tối ưụ Để giải quyết vấn đề này ta lại phải xác định được công thức truy hồị Thực tế là để xác định được công thức truy hồi này thì cũng không phải quá khó bởi từ công thức qui hoạch động chúng ta cũng có thể suy ngay ra được công thức truy hồị Tôi xin trở lại với bài toán cái túi đã nêu ở trên để xây dựng cấu hình tối ưu cho bài toán cái túi có nghĩa là phải mang những loại vật nào và mỗi loại vật là bao nhiêu để có được giá trị sử dụng max: Xây dựng hàm phụ choose[i,k] với ý nghĩa để đạt được giá trị tốt nhất tại f[i,k] thì cần phải sử dụng đến loại đồ vật nào (i=1 w,k=1 n) bằng cac công thức sau: Choose[i,1]:=0 nếu i Ta lần lượt cho k chạy tới n và i chạy tới w để xây dựng mảng choose như sau: Nếu f[i,k]=f[i,k-1] thì choose[i,k]:=choose[i,k-1] (do không mang vật k) Nếu không thì n choose[i,k]:=k (có nghĩa mang theo vật k) Khi xây dựng đến choose[w,n] thì ta chỉ cần chú ý đến cột cuối cùng của mảng choose và bắt đầu truy hồi. Giả sử mảng number[i] (i=1 n) sẽ cho ta số lượng loại vật i được mang theo. Ta sẽ cải thiện chương trình giải bài toán cái túi ở trên như sau: Program Bai_toan_cai_tui; Uses crt; Var value,weight,number:array[1 20]of 0 1000;{value:gia tri} f,choose:array[0 1200,0 12]of 0 10000; w,w1,sl:0 2000; fi:text; Procedure Init; Var i:byte; Begin clrscr; assign(fi,'tui.txt');reset(fi); readln(fi,w,sl);w1:=w; for i:=1 to sl do readln(fi,weight[i],value[i]);
18. End; { } Procedure Solve; Var i,j:word; Begin for j:=1 to sl do begin f[0,j]:=0;choose[0,j]:=0;end; for i:=1 to w do begin f[i,1]:=(i div weight[1])*value[1]; if i>=weight[1] then choose[i,1]:=1 else choose[i,1]:=0; end; for j:= 2 to sl do for i:=1 to w do begin choose[i,j]:=choose[i,j-1]; if i else begin f[i,j]:=f[i,j-1]; if (value[j]+f[i-weight[j],j])>f[i,j] then begin f[i,j]:=(value[j]+f[i-weight[j],j]); choose[i,j]:=j; end; end; end; for i:=1 to sl do number[i]:=0; while choose[w1,sl] 0 then begin write(' - ',number[i],' vat ',i, ' voi trong luong ',number[i]*weight[i],' va gia tri: ',number[i]*value[i]); writeln; end; End;
19. { Main } Begin Init; Solve; Print; Readln; End. III. Bàn luận Về bài toán cái túi còn rất nhiều lời giảị Ta cũng có thể giải quyết bài toán cái túi bằng thuật toán nhánh cận. Ưu điểm lớn nhất của thuật toán nhánh cận là có thể chỉ ra được mọi cấu hình tối ưu của bài tóan, tuy nhiên trong trường hợp xấu nhất, nhánh cận lại chính là vét cạn. Chính vì vậy, thời gian để thực hiện chương trình bằng nhánh cận sẽ rất lâụ Rất tiếc rằng, giải thuật qui hoạch động luôn luôn chỉ nêu ra được một cấu hình tối ưu. Nếu chúng ta giải bằng qui hoạch động như trên, thời gian chạy chương trình rất nhanh chóng. Chương trình trên hoàn toàn có thể cải thiện được bằng cách thay vì dùng mảng 2 chiều f và choose ta có thể chỉ dùng 4 mảng 1 chiều đó là f1, f2, choose1, choose2 bởi thực chất tại cột j của f thì ta chỉ có thể liên quan đến cột j-1 của f. Chính vì vậy, 2 mảng f1,f2 có thể dùng thế lần lượt cho nhau tương đương dùng mảng 2 chiều f. Khi đó chương trình sẽ có thể chạy với bộ dữ liệu cỡ vài nghìn! Thuật toán qui hoạch động còn được ứng dụng trong rất nhiều bài toán, tôi xin được nêu ra thêm một số bài toán khác nữa : Bài 3: Một tam giác được tạo bởi các số x và sắp xếp như hình bên Hãy tìm đường đi từ đỉnh xuống đáy sao cho: tổng các số đi qua là lớn nhất. Cho biết: - x là các số nguyên bất kì từ 0 đến 99. - tam giác có số hàng <=20. - mỗi bước đi: xuống 1 hàng tới số gần nhất bên trái hay phải. * Dữ liệu: đọc từ file 'vaọinp' có dạng: - Dòng đầu: số lượng dòng của tam giác. - Từ dòng 2: các số cụ thể. * Output: in ra màn hình - Hình tam giác cân được tạo từ các số. - Giá trị tổng các số đã gặp trên đường đi. - Các số đã gặp trên đường đi ( Câu 2 trong đề thi chọn đội tuyển Tin học Hà Nội 2001-2002) Bài 4: Chúng ta hãy giải quyết bài toán cái túi nhưng được thay đổi đi một số chi tiết như sau: Một nhà thám hiểm cần đem theo một số đồ vật vào cái túi có trọng tải không quá w của ông. Có tất cả n đồ vật, mỗi đồ vật i có trọng lượng là a[i] và giá trị sử dụng là c[i]. Hãy giúp nhà thám hiểm cách mang các đồ vật sao cho tổng giá trị sử dụng là lớn nhất có thể được (mỗi đồ vật chỉ có thể mang 1 lần hoặc không mang). Một bài báo không thể nói hết được tất cả những ưu việt của cả một thuật toán. Tuy nhiên, sau bài báo này, tôi hy vọng các bạn sẽ hay sử dụng qui hoạch động hơn trong việc giải toán. Nếu bạn nào muốn lời giải cụ thể của tất cả các bài toán trên, hãy liên hệ với tôi theo địa chỉ:
20. Quy hoạch tối ưu một bảng hai chiều - Bài toán tổng quát Đỗ Sơn Huỳnh Có rất nhiều bài toán tối ưu trên một bảng cho trước gồm M dòng, N cột như các dạng bài tìm một hành trình đi từ dòng thứ nhất tới dòng thứ M thoả mãn một điều kiện tối ưu nào đó. Nhưng cũng có những bài toán tối ưu với số liệu ban đầu là các mảng phần tử một chiều đều có thể đưa về bài toán quy hoạch tối ưu trên một bảng hai chiều. Một ví dụ dễ thấy và dễ gặp nhất là bài toán tìm xâu con lớn nhất, tìm đoạn dãy con đơn điệu dài nhất, bài toán cây xăng, và điển hình nhất là bài toán cái túi (với dữ liệu đầu vào là nguyên). Tất cả các bài toán đó chúng ta đều có thể đưa về một dạng tổng quát mà tôi tạm gọi là ″Bài toán tổng quát quy hoạch tối ưu trên một bảng hai chiều ″. Bài viết này là sự tổng hợp của bản thân tôi trong quá trình học môn tin học PASCAL. Xin nêu ra để các bạn có thể tham khảo và cho những ý kiến quý báu. Phát biểu bài toán Cho một bảng gồm M dòng, N cột. Hãy tìm một phương án tối ưu để ″đi ″ từ dòng thứ nhất đến hết dòng thứ M với các nguyên tắc sau: 1. Điều kiện tối ưu: Là điều kiện bài toán đưa ra. Đường đi tối ưu được tính bằng tổng trọng số các ô đi qua. Trọng số của một ô phụ thuộc quy tắc tính trọng số của bài toán. 2. Quy tắc tính trọng số: - Trọng số bằng trị số chính số liệu tại ô. - Trọng số được tính bằng quy tắc do ô đứng trước quy định tuỳ theo từng bài toán. - Trọng số phụ thuộc vào ô đứng trước ô đang xét. 3. Quy tắc ″Đi từ trên xuống dưới ″: Từ dòng thứ i bạn có thể đi ngang sang trái hoặc sang phải trên dòng đó và đi xuống dưới dòng thứ (i+1) theo các hướng chéo hoặc thẳng đứng. Thuật giải chung 1. Bước 0: Mô hình hoá: Nếu bài toán không phải là dạng tối ưu trên một bảng hai chiều, ta phải tìm cách mô hình hoá để đưa nó về dạng này. 2. Bước 1: Xây dựng các quy tắc tính trọng số: Xin lưu ý rằng điều kiện tối ưu ở đây đã có sẵn ngay từ đầu. Tuỳ theo dạng của bài toán ta sẽ có các quy tắc tính trọng số khác nhau. Khi đi xem xét với các bài toán cụ thể ta sẽ rõ hơn điều này. 3. Bước 2: Xây dựng quy tắc ″đi ″: Đôi khi quy tắc đi chưa có sẵn mà phải tự người lập trình đặt ra cho phù hợp với cách mô hình hoá của mình. Vấn đề này thuộc vào tư duy của mỗi người nên rất phong phú và phức tạp. 4. Bước 3: Xây dựng công thức tối ưu: Đây là bước quan trọng nhất của bài toán. Để xây dựng được công thức, ta cần phải dựa vào các quy tắc đi và tính trọng số. 5. Bước 4: Duyệt phương án tối ưu:
21. Đây là bước cuối cùng để ghi dữ liệu tìm được ra FILE kết quả. Bước này tương đối dễ dàng vì trong qúa trình quy hoạch, Chúng ta đã lưu các trạng thái của từng ô đi qua, đa phần là lưu vị trí của ô đứng trước ô này trên đường đi tối ưu. Một số bài toán Trước khi đi xét các bài toán cụ thể, chúng ta quy ước rằng mảng A[1 M,1 N] là mảng lưu dữ liệu ban đầu. Mảng B[1 M,1 N] là mảng dùng để quy hoạch. Với những bài toán với dữ liệu đầu vào là các mảng một chiều thì ta sẽ dùng ngay các dữ liệu đó mà không cần xây dựng mảng A. Các bài toán quen thuộc như bài toán cái túi,bài toán tìm đoạn dãy con đơn điệu dài nhất,bài toán cây xăng,.v v. ta sẽ không xét đến ở đây nữa. 1. Bài toán ″Con kiến ″: Trên một sân hình chữ nhật MxN, được chia thành các ô vuông đơn vị, mỗi ô chứa một lượng thức ăn. Một con kiến xuất phát từ ô (1,1) muốn đi qua sân để đến dòng thứ M. Con kiến chỉ có thể đi theo một dòng chia nhỏ trên sân ứng với một dòng của bảng chữ nhật hoặc đi theo trên một cột của sân. Hãy chỉ ra đường đi giúp con kiến có được nhiều thức ăn nhất. FOOD.INP 3 5 (Trong tất cả các bài toán dưới đây, dòng đầu bao giờ cũng là hai giá trị M và N) FOOD.OUT 45 (lượng thức ăn Max) (1,1) (2,1) (2,2) (2,3) (3,3) Thuật giải - Bước 0: Bỏ qua vì đây là bài toán đúng dạng - Bước 1: Trọng số ở đây là lượng thức ăn trên mỗi ô. - Bước 2: Quy tắc đi: Bước 3: Công thức quy hoạch B[i,j] là lượng thức ăn lớn nhất đi từ ô (1,1) đến ô (i,j) B[1,j] = A[1,j] với j = 1 N
22. B[i,1] = A[i,1]+B[i-1,1] với i = 2 M B[i,j] =Max{B[i-1,j],B[i,j-1]} + A[i,j] với i = 2 M và j = 2 N 2. Bài toán ″Sa mạc ″: Một bãi sa mạc có dạng hình chữ nhật MxN. Mỗi ô vuông đơn vị trên sa mạc có một độ cao nào đó. Một người muốn đi từ bờ đầu này sang bờ cuối cùng bên kia. Người đó chỉ có thể đi từ ô đang đứng tới một ô mới theo hướng thẳng đứng chéo trái hoặc chéo phải. Giả thiết rằng người đó không được vượt ra hai mép trái và phải của sa mạc. Hãy tìm đường đi sao cho người đó phải vượt qua quãng đường ngắn nhất. Mỗi lần đi từ một ô sang ô mới tiếp theo người đó phải đi hết quãng đường bằng độ chênh cao giữa hai ô đó. SAMAC.INP SAMAC.OUT 12 (Quãng đường Min) (1,3) (2,4) (3,3) (4,2) (5,2) Thuật giải -Bước 0: Bỏ qua - Bước 1: Trọng số là độ chênh cao giữa hai ô liên tiếp. - Bước 2: Quy tắc đi. - Bước 3: Công thức tối ưu: B[i,j] là quãng đường nhỏ nhất đi từ bờ đầu tiên đến ô (i,j). B[1,j] = 0 với j = 1 N B[i,1] = Min { B[i-1,1] + abs(A[i,1] - A[i-1,1]); B[i-1,2] + abs(A[i,1] - A[i-1,2])} Với i = 2 M B[i,j] = Min { B[i-1,j -1] + abs(A[i,j] - A[i-1,j -1]); B[i-1,j] + abs(A[i,j] - A[i-1,j]); B[i-1,j+1] + abs(A[i,j] - A[i-1,j+1])} Với i = 2 M, j = 2 N-1 B[i,N] = Min { B[i-1,N] + abs(A[i,N] - A[i-1,N]); B[i-1,N-1] + abs(A[i,N] - A[i-1,N-1])}
23. Với i = 2 M. 3. Bài toán ″Quầy bán hàng ″: Một siêu thị có M gian hàng, mỗi gian hàng gồm N ngăn chứa, mỗi ngăn chứa được bố trí ở mỗi phòng. Giám đốc siêu thị quyết định mở một đợt khuyến mãi cho khách hàng với các quy tắc sau: Mỗi gian hàng được bố trí trên từng tấng tương ứng từ tầng 1 đến M. Mỗi tầng có N thang máy đi lên ứng với mỗi phòng. Một khách hàng có thể mua sản phẩm tại một gian hàng nhưng chỉ có thể đi theo một hướng (không được mua xong rồi quay trở lại nơi đã mua). Khách hàng có thể đi thang máy lên tầng tiếp theo, nhưng phải mua ít nhất tại một ngăn chứa ở tầng đó thì mới được phép đi lên tầng trên nữa. Khách hàng mua hàng tại một ngăn chứa. Mỗi ngăn chứa quy định một số lượng hàng mà người khách buộc phải mua khi đến ngăn chứa đó. Nếu độ chênh số lượng hàng giữa hai ngăn chứa liên tiếp của một khách hàng là một số may mắn đã biết trước. Khách hàng đó sẽ được khuyến mãi thêm một số hàng bằng chính số may mắn đó. Đến tầng thứ M, khách hàng chỉ có thể mua hàng tại duy nhất một ngăn chứa. Hãy giúp khách hàng lựa chọn điểm xuất phát và hướng đi sao cho mua được nhiều hàng nhất (Kể cả số hàng được khuyến mãi). Dữ liệu đầu vào cho trong FILE văn bản SHOP.INP có cấu trúc như sau: Dòng đầu là 3 số M, N, K (1<M, N, K ≤100), K là số các con số may mắn. Dòng thứ hai ghi K con số may mắn. M dòng tiếp theo ghi số lượng hàng quy định tại mỗi ngăn chứa. Mỗi dòng gồm N số cách nhau bởi ít nhất một dấu trắng. Kết quả ghi ra FILE văn bản SHOP.OUT như sau: Dòng một là số lượng hàng nhiều nhất. - Dòng hai điểm xuất phát và quá trình mua hàng. Mỗi ngăn chứa đi qua được biểu diễn theo dạng ″(x,y) ″ trong đó (x,y) là vị trí của ngăn chứa. SHOP.INP SHOP.OUT 80 (Lượng hàng mua được Max) (1,3) (1,2) (2,2) (2,1) (3,1) (3,2) (3,3) (3,4) (4,4) Thuật giải:
24. Bước 0: Bỏ qua Bước 1: Trọng số ở đây là số lượng hàng tại các ngăn chứa. Đồng thời khi thoả mãn điều kiện ″khuyến mãi ″ thì trọng số sẽ được tăng thêm số lượng bằng số các con số may mắn (phụ thuộc vào ô đứng trước). Bước 2: Quy tắc đi Bước 3: Công thức B[i,j] là lượng hàng max khi đi từ tầng 1 cho đến ngăn chứa (i,j) B[0,j]= 0 với j =1 N B[i,0] = 0 với i =1 M B[i,j] = Max{B[i,j-1]+KM1, B[i-1,j] + KM2, B[i-1,k]+ SA[i,u]+KM3}+A[i,j] Với i =1 M , j =1 (N-1) , k =(j+1) M , u = j+1 k KM1 là lượng hàng khuyến mãi nếu Abs(A[i,j]-A[i,j-1]) là con số may mắn. KM2 là lượng hàng khuyến mãi nếu Abs(A[i,j]-A[i-1,j]) là con số may mắn. KM3 là tổng số lượng hàng khuyến mãi nếu Abs(A[i,k]-A[i-1,k]) và Abs(A[i,t]- A[i,t+1]) với t = j (u-1) là các con số may mắn. B[i,N] = Max{B[i,N-1]+KM1,B[i-1,N]+KM2}+A[i,N] Với i =1 M KM1 là lượng hàng khuyến mãi nếu abs(A[i,N]-A[i,N-1]) là con số may mắn. KM2 là lượng hàng khuyến mãi nếu abs(A[i,N]-A[i-1,N]) là con số may mắn. 4.Bài toán ″Tách từ ″: Đây là bài số 2 trong đề thi OLYMPIC Tin học sinh viên lần thứ XII, 2003, khối không chuyên. Mời các bạn xem đề bài trong số báo 5(44) của Tạp chí ISM. Thuật giải: Bước 0: Bài toán này thực chất là bài toán ″xâu con lớn nhất ″. Ta xây dựng bảng B[i,j] là xâu con lớn nhất giữa 2 xâu S1[1 i] và S[1 j].Gọi ll = length(S1), l =length(S). Nhận xét thấy rằng với B[ll,i]=ll với i = ll l thì ta có một phương án để tách từ. Bằng phương pháp duyệt dựa trên bảng lưu trạng thái qua quá trình quy hoạch, ta xét xem những vị trí còn lại trong xâu S (chưa thuộc S1) có tạo ra xâu S2 không. Nếu thoả mãn điều kiện này thì bài toán đã giải quyết xong. Lưu ý rằng bài toán luôn có lời giải. Bước 1: Trọng số là 0 hoặc 1 tuỳ xem S1[i] khác hoặc bằng S[j]. Bước 2: Quy tắc đi: Bước 3: Công thức B[0,j] = 0 với j =1 l B[i,0] = 0 với i =0 ll
25. B[i,j] = min{B[i,j-1],B[i-1,j],B[i-1,j-1]+gt} với i = 1 ll , j =1 l gt là 0 hoặc 1 tuỳ theo S1[i] khác hoặc bằng S[j]. .Bài toán ″Cắt hình chữ nhật ″: Đây là bài 146 trong mục ″Đề ra kì này ″. Xin các bạn xem đề bài trong số 6(45) của Tạp chí ISM. Bước 0: Ta xây dựng bảng B[i,j] là số lần cắt ít nhất để cắt một hình chữ nhật có kích thước [1 i ,1 j]. Bước 1: Trọng số ở đây là 1 thể hiện một nhát cắt. Bước 2: Quy tắc đi: Bài toán này có quy tắc đi tương đối phức tạp. Bước 3: Công thức B[i,1] = i với i = 1 M B[1,j] = j với j = 1 N B[i,j] = min{B[i,q]+B[i,j-q], B[k,j]+B[i-k,j]} với q = 1 (j-1) , k =1 (i-1) Tổng kết Còn rất nhiều bài toán khác có dạng như bài toán tổng quát này nhưng chung quy lại chúng ta đều có thể đưa nó về một dạng chung. Sau đó dựa vào những nguyên tắc giải chung, ta đều có thể giải quyết dễ dàng. Các dạng bài toán tổng quát này khi dữ liệu cho quá giới hạn khai báo bảng hai chiều đều có thể giải quyết bằng cách quy hoạch liên tục trên 2 mảng một chiều. Sau mỗi bước quy hoạch phải thay đổi 2 mảng này sao cho phù hợp với bước quy hoạch tiếp theo. Cái khó của bài toán có dữ liệu lớn này là việc lưu trữ trạng thái để sau khi quy hoạch toàn bộ ta còn có thể in ra file kết quả ″quá trình đi ″ của phương án tối ưu. Rất mong nhận được những ý kiến đóng góp quý báu của các bạn đọc ISM. Mọi thắc mắc xin gửi cho tôi theo địa chỉ: Phương pháp quy hoạch động Phạm Hải Minh Quy hoạch động là một phương pháp rất hay và mạnh của tin học. Nhưng để giải được các bài toán bằng phương pháp quy hoạch động thật chẳng dễ dàng chút nào. Chủ yếu học sinh hiện nay sử dụng quy hoạch động theo kiểu làm từng bài cho nhớ mẫu và áp dụng vào những bài có dạng tương tự. Qua quá trình học tập tôi đã tự rút ra cho mình một số kinh nghiệm về cách giải các bài toán bằng quy hoạch động, xin đưa ra để mọi người cùng tham khảo và góp ý.
26. 1. Lí thuyết: Phương pháp quy hoạch động gồm 6 bước: - Bước 1: Chia nhỏ bài toán Lập vectơ P có các thành phần x1,x2, ,xn. Mỗi vectơ P ứng với một bài toán con của bài toán. Ban đầu ta xây dựng P với 1 thành phần duy nhất. - Bước 2: Lập hệ thức quy hoạch động Xây dựng hàm f(P) là hàm tối ưu của vectơ P (hay hàm tối ưu cho mỗi bài toán con) f(P) = g(f(P1),f(P2), ,f(Pn)) g có thể là hàm Max,Min hoặc tổng tuỳ yêu cầu của bài toán là tìm Max,Min hay tính tổng. P gọi là vectơ cha P1,P2,P3, ,Pn gọi là vectơ con - Bước 3: Kiểm tra Nếu không xây dựng được hàm f thì thêm tiếp hoặc bỏ đi từng thành phần của vectơ P rồi quay lại bước 2. Nếu được thì làm tiếp bước 4. - Bước 4: Tối ưu hoá hệ thức Tối ưu vectơ P bằng cách xét từng thành phần x của vectơ P: Chọn vectơ PBest trong P1,P2,P3, Pn chỉ khác nhau thành phần x sao cho có thể đưa PBest vào thay P1,P2,P3 ,Pn trong hàm g mà không làm thay đổi giá trị của hàm g thì có thể đơn giản thành phần x của vectơ P. - Bước 5: Chọn kiểu quy hoạch động + Kiểu 1: Nếu các thành phần của vectơ con P1 luôn ≤ hay ≥ các thành phần của vectơ cha P thì ta có thể dùng các vòng lặp for lồng nhau để cài đặt. + Kiểu 2: Nếu vectơ P và vectơ P1 luôn có mối quan hệ cha con một chiều thì ta có thể dùng phương pháp đệ quy có nhớ để cài đặt. + Kiểu 3: Nếu vectơ P và vectơ P1 luôn có mối quan hệ cha con hai chiều nhưng không rõ đâu là vectơ cha , đâu là vectơ con vì còn phụ thuộc vào từng bài toán thì ta có thể dùng phương pháp repeat until để cài đặt. - Bước 6: Tối ưu hoá bộ nhớ (chỉ dùng cho cài đặt kiểu 1) Đơn giản vectơ P bằng cách xét từng thành phần x của vectơ P: Nếu f(P( ,x, ))=g(f(P1( ,x1, )),f(P2( ,x2, )), ,f(Pn( ,xn, ))) và x-x1, x-x2, , x-xn≤T nào đó thì ta chỉ cần đưa vòng lặp của x lên đầu tiên và bỏ x ra khỏi vectơ P và lưu T+1 vectơ P. 2. Ví dụ: Ví dụ 1: Bài toán tìm đường đi ngắn nhất: * Bài toán: Cho đồ thị 1 chiều có trọng số được biểu diễn bởi ma trận kề a. Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T.
27. * Cách giải bằng quy hoạch động: - Bước 1: Vectơ P (đỉnh hiện tại) - Bước 2: f(P(u)) = f(P1(v))+a[v,u] (f là đường đi ngắn nhất từ S đến u) - Bước 3: Đúng. - Bước 4: Không cần đơn giản. - Bước 5: Vì P(u) và P1(v) có thể là vectơ cha hay vectơ con tuỳ thuộc bài toán nên ta phải dùng kiểu cài đặt 3. - Bước 6: Không có. Ví dụ 2: Bài toán cái túi: * Bài toán: Cho n đồ vật, đồ vật thứ i có giá trị V[i] và trọng lượng W[i], số lượng không hạn chế. Ta có một túi đựng được trọng lượng không quá T. Cần chọn các đồ vật để bỏ vào túi sao cho tổng giá trị là lớn nhất. * Cách giải bằng quy hoạch động: - Bước 1: Vectơ P (trọng lượng hiện tại) - Bước 2: f(P(m))=Max(f(P1(m-W[i]))+V[i]) (f là tổng giá giá trị lớn nhất khi dùng các vật có tổng trọng lượng m) - Bước 3: Đúng. - Bước 4: Không cần đơn giản. - Bước 5: Vì nếu P1(m1) con của P(m) m1< m nên ta có thể dùng kiểu cài đặt 1. - Bước 6: Không cần đơn giản. Ví dụ 3: Bài toán chia kẹo: * Bài toán: Cho n gói kẹo, gói kẹo thứ i có a[i] cái kẹo. Cần chọn ra một số gói kẹo sao cho số kẹo là lớn nhất và không vượt quá W cái. * Cách giải bằng quy hoạch động: - Bước 1: Vectơ P (tổng số kẹo hiện tại) - Bước 2 (1): Do không biết những gói kẹo nào đã dùng, những gói kẹo nào chưa dùng nên không thể lập được công thức quy hoạch động - Bước 3 (1): Chưa đúng nên thêm thành vectơ P (tổng số kẹo, số gói kẹo đã dùng) - Bước 2 (2): Do vẫn không biết những gói kẹo nào đã dùng, những gói kẹo nào chưa dùng nên không thể lập được công thức quy hoạch động - Bước 3 (2): Thành phần thêm vào không giải quyết được vấn đề nên bỏ đi và thêm thành phần khác vào P (tổng số kẹo, gói keo cuối cùng đã dùng) - Bước 2(3): f(P(u,i))=0 nếu không tồn tại P1(u-a[i],j]) sao cho f(P1)=1 (với j<i) f(P(u,i))=1 nếu tồn tại P1(u-a[i],j) sao cho f(P1)=1 (với j<i) - Bước 3(3): Đúng. - Bước 4: Xét thành phần (gói kẹo cuối cùng đã dùng) của vectơ P. Ta thấy chỉ cần chọn P(u,i) trong P1(u,i1),P2(u,i2), ,Pn(u,in) sao cho i min và f(P)=1. Vì thế ta chỉ cần lưu i min này vào mảng IMin và như vậy hàm f không hề bị thay đổi. Hàm f lúc này thành: f(P(u))=0 nếu không tồn tại P1(u-a[i]) sao cho f(P1)=1 (với IMin[u-a[i]]<i) f(P(u))=1 nếu tồn tại P1(u-a[i]) sao cho f(P1)=1 (với IMin[u-a[i]]<i) - Bước 5: Vì nếu P1(u1) là con của P(u) tương đương u1<u nên ta có thể dùng kiểu cài
28. đặt 1. Ghi chú: Có chương trình mẫu của các ví dụ kèm theo. 3. Bài tập: Bài tập 1: Trên đoạn đường AB dài n km cần đặt k trạm xăng 1 tại A, 1 tại B và sao cho khoảng cách giữa các trạm xăng sau không lớn hơn khoảng cách giữa các trạm xăng trước. Tính số cách đặt các trạm xăng. Input: n k (n≤100,k≤n) Output: P số cách đặt các trạm. Ví dụ: Input: 4 3 Output: 2 Bài tập 2: Cho ma trận n*m chỉ gồm 0 và 1.Hỏi cần ít nhất bao nhiêu nhát cắt thẳng (mỗi nhát cắt thẳng phải chia ma trận ra làm 2 phần) để chia ma trận thành những hình chữ nhật chỉ gồm 0 hoặc 1. Input: n m (n,m≤20) ma trận n*m Output: P số nhát cắt ít nhất. Ví dụ: Input: 3 3 1 1 1 0 0 1 0 0 1 Output: 3 4. Mở rộng: Với phương pháp trên nếu không thể giải được bài toán bằng quy hoạch động do khó khăn trong dữ liệu hay trong việc lập hệ thức, ta có thể nhanh chóng chuyển sang một thuật toán duyệt hoặc tham lam. Nếu hệ thức đúng đắn nhưng không thể lưu trữ ta có thể sử dụng thuật toán duyệt bằng cách đệ qui (bỏ đi phần có nhớ ) sẽ vẫn cho kết quả đúng mặc dù có chậm hơn. Nếu không thể lập được hệ thức đúng ta vẫn có thể cài đặt như một thuật toán tham lam cho kết quả gần đúng. Hi vọng qua bài viết này các bạn có thể tự rút ra những kinh nghiệm riêng cho bản thân. Chúc các bạn thành công với phương pháp quy hoạch động. Thuật toán Dijkstra trên cấu trúc Heap
29. Trần Đỗ Hùng 1. Nhắc lại thuật toán Dijkstra tìm đường đi ngắn nhất Bài toán: Cho đồ thị có hướng với trọng số các cung (i,j) là C[i,j] không âm, tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t. Thuật toán Dijkstra: Bước 1- Khởi trị: - Khởi trị nhãn đường đi ngắn nhất từ đỉnh s tới đỉnh i là d[i]:= C[s,i] (nếu không có đường đi trực tiếp từ s đến i thì C[s,i] bằng vô cùng). Lưu lại đỉnh trước khi tới i trên hành trình ngắn nhất là Tr[i] := s - Khởi trị nhãn đỉnh s là d[s] =0 - Đánh dấu mọi đỉnh i là tự do (nhãn d[i] chưa tối ưu): DX[i]:=false Bước 2 (vòng lặp vô hạn): - Tìm đỉnh i0 tự do có nhãn d[i0] nhỏ nhất. - Nếu không tìm được i0 (i0 =0) hoặc i0 =t thì thoát khỏi vòng lặp còn không thì + Đánh dấu i0 đã được cố định nhãn DX[i0]:=True (gọi i0 là đỉnh được cố định nhãn) + Sửa nhãn cho các đỉnh j tự do kề với i0 theo công thức d[j] = Min{d[j], d[i0]+C[i0,j] và ghi lưu lại đỉnh trước j là i0: Tr[j]:= i0 Bước 3 &minus Tìm và ghi kết quả: Dựa vào giá trị d[t] và mảng Tr để kết luận thích hợp 2. Cấu trúc Heap và một số phép xử lí trên Heap a) Mô tả Heap: Heap được mô tả như một cây nhị phân có cấu trúc sao cho giá trị khoá ở mỗi nút không vượt quá giá trị khoá của hai nút con của nó (suy ra giá trị khoá tại gốc Heap là nhỏ nhất). b) Hai phép xử lí trên Heap - Phép cập nhật Heap Vấn đề: Giả sử nút v có giá trị khoá nhỏ đi, cần chuyển nút v đến vị trí mới trên Heap để bảo toàn cấu trúc Heap Giải quyết: + Nếu nút v chưa có trong Heap thì tạo thêm nút v thành nút cuối cùng của Heap (hình 1) + Chuyển nút v từ vị trí hiện tại đến vị trí thích hợp bằng cách tìm đường đi ngược từ vị trí hiện tại của v về phía gốc qua các nút cha có giá trị khoá lớn hơn giá trị khoá của v. Trên đường đi ấy dồn nút cha xuống nút con, nút cha cuối cùng chính là vị trí mới của nút v (hình 2). Chú ý: trên cây nhị phân, nếu đánh số các nút từ gốc đến lá và từ con trái sang con phải thì dễ thấy: khi biết số hiệu của nút cha là i có thể suy ra số hiệu hai nút con là 2*i và 2*i+1, ngược lại số hiệu nút con là j thì số hiệu nút cha là j div 2.
30. - Phép loại bỏ gốc của Heap Vấn đề: Giả sử cần loại bỏ nút gốc khỏi Heap, hãy sắp xếp lại Heap (gọi là phép vun đống) Giải quyết: + Tìm đường đi từ gốc về phía lá, đi qua các nút con có giá trị khoá nhỏ hơn trong hai nút con cho đến khi gặp lá. + Trên dọc đường đi ấy, kéo nút con lên vị trí nút cha của nó. Ví dụ trong hình vẽ 2 nếu bỏ nút gốc có khoá bằng 1, ta sẽ kéo nút con lên vị trí nút cha trên đường đi qua các nút có giá trị khoá là 1, 2, 6, 8 và Heap mới như hình 3 3. Thuật toán Dijkstra tổ chức trên cấu trúc Heap (tạm kí hiệu là Dijkstra_Heap) Tổ chức Heap: Heap gồm các nút là các đỉnh i tự do (chưa cố định nhãn đường đi ngắn nhất), với khoá là nhãn đường đi ngắn nhất từ s đến i là d[i]. Nút gốc chính là đỉnh tự do có nhãn d[i] nhỏ nhất. Mỗi lần lấy nút gốc ra để cố định nhãn của nó và sửa nhãn cho các đỉnh tự do khác thì phải thức hiện hai loại xử lí Heap đã nêu (phép cập nhật và phép loại bỏ gốc). Vậy thuật toán Dijkstra tổ chức trên Heap như sau: Cập nhật nút 1 của Heap (tương ứng với nút s có giá trị khoá bằng 0)
31. Vòng lặp cho đến khi Heap rỗng (không còn nút nào) Begin + Lấy đỉnh u tại nút gốc của Heap (phép loại bỏ gốc Heap) + Nếu u= t thì thoát khỏi vòng lặp + Đánh dấu u là đỉnh đã được cố định nhãn + Duyệt danh sách cung kề tìm các cung có đỉnh đầu bằng u, đỉnh cuối là v Nếu v là đỉnh tự do và d[v] > d[u] + khoảng cách (u,v) thì Begin Sửa nhãn cho v và ghi nhận đỉnh trước v là u Trên Heap, cập nhật lại nút tương ứng với đỉnh v. End; End; 4. Đánh giá + Thuật toán Dijkstra tổ chức như nêu ở mục 1. Có độ phức tạp thuật toán là O(N2), nên không thể thực hiện trên đồ thị có nhiều đỉnh. + Các phép xử lí Heap đã nêu (cập nhật Heap và loại bỏ gốc Heap) cần thực hiện không quá 2.lgM phép so sánh (nếu Heap có M nút). Số M tối đa là N (số đỉnh của đồ thị) và ngày càng nhỏ dần (tới 0). Ngoài ra, nếu đồ thị thưa (số cung ít) thì thao tác tìm đỉnh v kề với đỉnh u là không đáng kể khi ta tổ chức danh sách các cung kề này theo từng đoạn có đỉnh đầu giống nhau (dạng Forward Star). Do đó trên đồ thị thưa, độ phức tạp của Dijkstra_Heap có thể đạt tới O(N. k.lgN) trong đó k không đáng kể so với N + Kết luận: Trên đồ thị nhiều đỉnh ít cung thì Dijkstra_Heap là thực hiện được trong thời gian có thể chấp nhận. 5. Chương trình uses crt; const maxN = 5001; maxM = 10001; maxC = 1000000000; fi = &rquo;minpath.in&rquo;; fo = &rquo;minpath.out&rquo;; type k1 = array[1 maxM] of integer; k2 = array[1 maxM] of longint; k3 = array[1 maxN] of integer; k4 = array[1 maxN] of longint; k5 = array[1 maxN] of boolean; var ke : ^k1; {danh sách đỉnh kề} c : ^k2; {trọng số cung tương ứng với danh sách kề} p : ^k3; 1 {vị trí đỉnh kề trong danh sách kề} d : k4; {nhãn đường đi ngắn nhất trong thuật toán Dijkstra}
32. tr : k3; {lưu đỉnh trước của các đỉnh trong hành trình ngắn nhất } dx : k5; {đánh dấu nhãn đã cố định, không sửa nũă} h, {heap (Đống)} sh : k3; {số hiệu của nút trong heap} n,m,s,t, {số đỉnh, số cạnh, đính xuất phát và đỉnh đích} shmax : integer; {số nút max trên heap} procedure doc_inp; var i,u,v,x : integer; f : text; begin assign(f,fi); {Đọc file input lần thứ nhất} reset(f); readln(f,n,m,s,t); new(p); new(ke); new(c); fillchar(p^,sizeof(p^),0); for i:=1 to m do begin readln(f,u); inc(p^[u]); {p^[u] số lượng đỉnh kề với đỉnh u} end; for i:=2 to n do p^[i] := p^[i] + p^[i-1]; {p[i]^ dùng để xây dựng chỉ số của mảng kê} close(f); {p[i]^ là vị trí cuối cùng của đỉnh kề với đỉnh i trong mảng kê} {Đọc file input lần thứ hai} reset(f); readln(f); for i:=1 to m do begin readln(f,u,v,x); kê[p^[u]] := v; {xác nhận kề với đỉnh u là đỉnh v} c^[p^[u]] := x; {xác nhận trọng số của cung (u,v) là x} dec(p^[u]); {chuyển về vị trí của đỉnh kề tiếp theo của u} end; p^[n+1] := m; {hàng rào} close(f); end; procedure khoitri; var i : integer;
33. begin for i:=1 to n do d[i] := maxC; {nhãn độ dài đường đi ngắn nhất từ s tới i là vô cùng} d[s] := 0; {nhãn độ dài đường đi ngắn nhất từ s tới s là 0} fillchar(dx,sizeof(dx),False); {khởi trị mảng đánh dấu: mọi đỉnh chưa cố định nhãn } fillchar(sh,sizeof(sh),0); {khởi trị số hiệu các nút của Heap là 0} shmax := 0; {khởi trị số nút của heap là 0} end; procedure capnhat(v : integer); {đỉnh v vừa nhận giá trị mới là d[v], do đó cần xếp lại vị trí của đỉnh v trong heap, bảo đảm tính chất heap} var cha,con : integer; begin con := sh[v]; {con là số hiệu nút hiện tại của v} if con=0 then {v chưa có trong heap, thì bổ sung vào nút cuối cùng của heap} begin inc(shmax); con := shmax; end; cha := con div 2; {cha là số hiệu hiện tại của nút cha của nút v hiện tại} while (cha>0) and (d[h[cha]] > d[v]) do {nếu nhãn của nút cha (có số hiệu là cha) lớn hơn nhãn của nút v thì đưa dần nút v về phía gốc tới vị trí thoả mãn điều kiện của heap bằng cách: kéo nút cha xuống vị trí của nút con của nó } begin h[con] := h[cha]; sh[h[con]] := con; con := cha; cha := con div 2; end; h[con] := v; {nút con cuối cùng trong quá trình "kéo xuống" nêu trên, là vị trí mới của v} sh[v] := con; end; function lay: integer; {lấy khỏi heap đỉnh gốc, vun lại heap để hai cây con hợp thành heap mới} var r,c,v : integer; begin lay := h[1]; {lấy ra nút gốc là nút có nhãn nhỏ nhất trong các nút chưa cố định nhãn} v := h[shmax]; {v: đỉnh cuối cùng của heap} dec(shmax); {sau khi loại đỉnh gốc, số nút của heap giảm đi 1} r := 1; {bắt đầu vun từ nút gốc}
34. while r*2 d[u]+c^[j]) then {điều kiện sửa nhãn v} begin d[v] := d[u] + c^[j]; {sửa lại nhãn của v} tr[v] := u; {ghi nhận lại đỉnh trước của v là u} capnhat(v); {cập nhật lại v trong heap để bảo đảm cấu trúc heap } end; end; until shmax = 0; {dừng khi không còn đỉnh tự do (số nút của heap bằng 0)} end; procedure inkq; var f : text; i,j : integer; kq : k3; begin assign(f,fo); rewrite(f); if d[t]=maxc then writeln(f,-1) {ghi kết quả: vô nghiệm} else begin writeln(f,d[t]); {ghi độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh t vào file output}
35. i := 0; while t<>s do {lần ngược các đỉnh liên tiếp của hành trình ngắn nhất lưu vào mảng kq} begin inc(i); kq[i] := t; t := tr[t]; end; inc(i); kq[i] := s; for j:=i downto 1 do write(f,kq[j],′ ′); {ghi hành trình vào file output} end; close(f); end; BEGIN doc_inp; khoitri; dijkstra; inkq; END. Cách khác để tính giá trị của một biểu thức Quắch Nguyễn Tính giá trị của một biểu thức là một bài toán không khó. Có nhiều cách để giải quyết bài toán này chẳn hạn như: đưa biểu thức số học theo ký pháp hậu tố và tiền tố, hoặc đưa về dạng cây biểu thức Tuy nhiên ở đây tôi muốn đưa ra một phương pháp giải khác với những phương pháp trên nhằm mục đích để cho các bạn đọc gần xa tham khảo thêm và cũng rất mong nhận được ý kiến phản hồi của bạn đọc gần xa. Phương pháp giải 1. Biểu thức chỉ là một số thực thì giá trị của biểu (gtbt) thức bằng chính số đó 2. Biểu thức chỉ chứa phép toán '*' thì gtbt = gtbt(trước phép nhân đầu tiên ) * gtbt(dãy sau phép nhân đầu tiên) 3. Biểu thức có chứa 2 phép toán '+, *' thì gtbt = gtbt(dãy trước dấu cộng đầu tiên)+ gtbt(dãy sau dấu cộng đầu tiên) function gtbt(s:string):real; begin if isnumber(s) then gtbt:=strtonumber(s) else if all_mull_ope(s) then tinh:=gtbt(head(s,’*’))*gtbt(tail(s,’*’))
36. else gtbt:=gtbt(head(s,’+’))+ gtbt(tail(s,’+’)); end; 4. Biểu thức có chứa 3 phép toán '+ , −, *'trong trường họp này ta chèn thêm dấu '+' vào trước những dấu '−' (ngoại trừ dấu ' −' đứng tại ví trí thứ 1 : s1=’ −’ ) sau đó vẫn tính như (3) 5. Biểu thức có chứa 4 phép toán ' +, −, *, /' tương tự như (4) và chèn thêm dấu ' *' trước những dấu ' /' sau đó tính như (3). Các hàm: Function Isnumber(s:string):boolean; {hàm này trả về giá trị đúng nếu s là một số } var r:real; code:word; begin val(s,r,code); Isnumber:=(code=0)or (s[1]=’/’); end; Function Strtonumber(s:string):real; {hàm này trả về một số tương ứng với s hoặc 1/s nếu s[1] =’/’ } var r:real; code:word; begin val(s,r,code); if code 0 then begin val(copy(s,2,length(s)-1),r,code); r:=1/r; end; Strtonumber:=r; end; Function All_mull_ope(s:string):boolean; { hàm trả về giá trị true khi trong s có ' * ' và không có '+' } begin All_mull_ope:= (pos(’*’,s)>0) and (pos(’+’,s)=0); end; Function Head(s:string;c:char):string; { hàm trả về chuỗi đứng trước dấu c đầu tiên } begin Head:=copy(s,1,pos(c,s)-1); end; Function Tail(s:string;c:char):string; { hàm trả về chuỗi đứng sau dấu c đầu tiên } begin Tail:=copy(s,pos(c,s)+1,length(s)-pos(c,s)); end; Function Insert_ope(s:string):string; { hàm xử lí chuỗi trước khi tính } var i:byte; begin while pos(’ ’,s)>0 do begin i:= pos(’ ’,s); delete(s,i,1); s[i]:=’+’; {đổi 2 dấu ’-’ thành
37. dấu’+’} while pos(’ ’,s)>0 do delete(s,pos(’ ’,s),1); i:=1; repeat inc(i); case s[i] of ’-’: begin insert(’+’,s,i); inc(i); end; ’/’: begin insert(’*’,s,i); inc(i); end; end; until i>= length(s); Insert_ope:=s; end; Function Tinh_gia_tri_bieu_thuc_khong_dau_ngoac(s:string) : real; var s:string; begin Tinh_gia_tri_bieu_thuc_khong_dau_ngoac:= gtbt(insert_ope(s)); end; 6. Biểu thức có chứa 4 phép toán trên và dấu ngoặc: Trước tiên ta đi tìm dấu ngoặc đóng đầu tiên tính từ trái sang phải trong b iểu thức. Nếu tồn tại thì ta lui về trái tìm dấu ngoặc mở đầu tiên mà ta gặp (tính từ dấu ngoặc đóng đầu tiên). Sau đó trích biểu thức con trong khoảng trên ra tính giá trị của biểu thức con đó (5) và đưa giá trị ấy về dạng chuỗi ghép vào đúng vị trí của nó ban đầu trong biểu thức mẹ. Lặp lại bước 6. Ngược lại nếu không tồn tại dấu ngoặc đóng thì biểu thức đã cho là biểu thức không có chứa dấu ngoặc (5) Function Numbertostr(r:real):string; var s:string; begin str(r:0:5,s); Numbertotr :=s; end; Function Tinh_gia_tri_bieu_thuc_co_ngoac(s:string):real; begin i:=pos(’)’,s); while i>0 do begin repeat dec(i); until s[i]=’(’; s1:=copy(s,i+1,pos( ’)’,s)-i-1); delete(s,i,pos( ’)’,s) -i+1; insert(numbertostr(Tinh_gia_tri_bieu_thuc_khong_dau_ngoac(s1)),s,i); i:=pos( ’-’,s); end; Tinh_gia_tri_bieu_thuc_khong_co_ngoac:=Tinh_gia_tri_bieu_thuc_khong_dau_ng
38. oac(s); end; 7.Xử lí lỗi của biểu thức: ta chỉ cần sửa lại chút ít các đoạn mã lệnh trên thì ta sẽ phát hiện được tất các các lỗi mà biểu thức đó có chẵn hạn như: sai cú pháp, xuất hiện kí tự lạ, chia cho 0 8. Mở rộng phép toán: với phương pháp nêu trên các bạn dễ dàng bổ sung thêm một số phép toán vào biểu thức như: ^, log, Ln, sin, cos, 9. Tính biểu thức dài: ta có thể dùng mảng để lưu trữ biểu thức thay vì chuỗi. Trong quá trình viết bài có thể có xuất hiện một số sai sót. Mong bạn đọc thông cảm và tự khắc phục (nếu được) hoặc liên hệ với tác giả của bài viết để bổ sung. Dijtra - thuật toán tốt để giải các bài toán tối ưu Đỗ Giang Lâm Bài toán tối ưu là một bài toán muôn thuở trong tin học bởi nó có ứng dụng thực tế cao. Ví dụ như làm thế nào để hoàn thành một công viêc nào đó với chi phí ít nhất, hay đi như thế nào để đến đích sớm nhất, vv Cùng với sự trợ giúp của máy tính và các thuật toán hiệu quả đã giúp chúng ta giải quyết bài toán tối ưu một cách dễ dàng và chính xác. Một trong số các thuật toán hiệu quả đó là thuật toán Dijkstra- thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số không âm. Chắc hẳn các bạn đều không xa lạ gì với thuật toán Dijkstra. Đây là một cải tiến từ thuật toán Ford_Bellman. Trong truờng hợp trọng số trên các cung là không âm, thuật toán do Dijkstra đề nghị để giải bài toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị làm việc hiểu quả hơn nhiều so với thuật toán Ford_Bellman. Thuật toán được xây dựng trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn của một đỉnh cho biết cận trên của độ dài đường đi ngắn nhất từ s đến nó. Các nhãn này sẽ được biến đổi theo một thủ tục lặp, mà ở mỗi một bước lặp có một nhãn tạm thời trở thành nhãn cố định. Nếu nhãn của một đỉnh nào đó trở thành nhãn cố định thì nó sẽ cho ta không phải là cận trên mà là đường đi ngắn nhất từ đỉnh s đến nó. Thuật toán được mô tả cụ thể như sau: Đầu vào: Đồ thị có hướng G = (V,E) với n đỉnh, s thuộc V là đỉnh xuất phát, ma trận trọng số a[u,v], a[u,v] ≥ 0, u,v thuộc V. Đầu ra: Độ dài đường đi ngắn nhất từ s đến tất các đỉnh còn lại: d[v], v thuộc V. truoc[v], v thuộc V, ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v Procedure Dijkstra; Begin for v thuộc V do begin d[v] := a[s,v]; truoc[v] := s; end; (* Khởi tạo *) d[s] := 0; T := V {s} (* T là tập các đỉnh có nhãn tạm thời *) (* Bước lặp *)
39. while T ≠ ∅ do Begin Tìm đỉnh u thuộc T thoả mãn d[u] = Min {d[z] : z thuộc T} T := T{u} (* Cố định nhãn của đỉnh u *) for v thuộc T do (* Cập nhật lại nhãn cho các đỉnh trong T *) if d[v] > d[u] + a[u,v] then begin d[v] := d[u] + a[u,v]; truoc[v] := u; end; end; end; Thuật toán Dijkstra tìm được đường đi ngắn nhất trên đồ thị sau thời gian cỡ O(n2). Nếu chỉ cần tìm đường đi ngắn nhất từ s đến một đỉnh t nào đó thì có thể kết thúc thuật toán khi đỉnh t trở thành đỉnh có nhãn cố định. Việc cài đặt thuật toán chắc không có gì khó khăn. Điều khó nhất là trong các bài toán cụ thể ta phải đưa được nó về mô hình đồ thị như thế nào, đỉnh là gì, 2 đỉnh có cung nối khi nào, trọng số là gì, đỉnh xuất phát là gì, đỉnh kết thúc là gì, vv Từ đó mới áp dụng thuật toán cơ bản để giải. Sau đây là một số bài toán hay ứng dụng thuật toán Dijkstra để giải. Bài 1: Chuyển Hàng Bản đồ một kho hàng hình chữ nhật kích thước mxn được chia thành các ô vuông đơn vị (m hàng, n cột: các hàng đánh số từ trên xuống dưới, các cột được đánh số từ trái qua phải). Trên các ô vuông của bản đồ có một số ký hiệu: - Các ký hiệu # đánh dấu các ô đã có một kiện hàng xếp sẵn. - Một ký hiệu *: Đánh dấu ô đang có một rôbốt. - Một ký hiệu $: Đánh dấu ô chứa kiện hàng cần xếp. - Một ký hiệu @: Đánh dấu vị trí mà cần phải xếp kiện hàng vào $ vào ô đó. - Các ký hiệu dấu chấm ".": Cho biết ô đó trống. Tại môt thời điểm, rô bốt có thể thực hiện một trong số 6 động tác ký hiệu là: - L, R, U, D: Tương ứng với phép di chuyển của rô bốt trên bản đồ: sang trái, sang phải, lên trên, xuống dưới. Thực hiện một phép di chuyển mất 1 công - +, − : Chỉ thực hiện khi rôbốt đứng ở ô bên cạnh kiện hàng $. Khi thực hiện thao tác +, rôbốt đứng yên và đẩy kiện hàng $ làm kiện hàng này trượt theo hướng đẩy, đến khi chạm một kiện hàng khác hoặc tường nhà kho thì dừng lại. Khi thực hiện thao tác − , rô bốt kéo kiện hàng $ về phía mình và lùi lại 1 ô theo hướng kéo. Thực hiện thao tác đẩy hoặc kéo mất C công. Rô bốt chỉ được di chuyển vào ô không chứa kiện hàng của kho. Hãy tìm cách hướng dẫn rôbốt thực hiện các thao tác để đưa kiện hàng $ về vị trí @ sao cho số công phải dùng là ít nhất. Dữ liệu: Vào từ file văn bản CARGO.INP - Dòng 1: Ghi ba số nguyên dương m, n, C ( m, n ≤ 100; C ≤ 100) - m dòng tiếp theo, dòng thứ i ghi đủ n ký kiệu trên hàng i của bản đồ theo đúng thứ tự trái qua phải. Các ký hiệu được ghi liền nhau. Kết quả: Ghi ra file văn bản CARGO.OUT - Dòng 1: Ghi số công cần thực hiện - Dòng 2: Một dãy liên tiếp các ký tự thuộc {L, R, U, D, +, -} thể hiện các động tác cần
40. thực hiện của rô bốt. Rằng buộc: Luôn có phương án thực hiện yêu cầu đề bài. Ví dụ: Phân tích: Thuật toán: Ta sẽ dùng thuật toán Dijkstra để giải bài toán này. * Mô hình đồ thị: Mỗi đỉnh của đồ thị ở đây gồm 3 trường để phân biệt với các đỉnh khác: - i: Tọa độ dòng của kiện hàng (i = 1 m) - j: Tọa độ cột của kiện hàng (j = 1 n) - h: Hướng của rô bốt đứng cạnh kiện hàng so với kiện hàng (h = 1 4: Bắc, Đông, Nam, Tây). Bạn có thể quan niệm mỗi đỉnh là (i,j,u,v): trong đó i,j: tọa độ của kiện hàng; u,v: tọa độ của rôbốt đứng cạnh kiện hàng. Nhưng làm thế sẽ rất lãng phí bộ nhớ và không chạy hết được dữ liệu. Ta chỉ cần biết hướng h của rôbốt so với kiện hàng là có thể tính được tọa độ của rôbốt bằng cách dùng 2 hằng mảng lưu các số ra: dx : array[1 4] of integer = (-1,0,1,0) dy : array[1 4] of integer = (0,1,0,-1) Khi đó, tọa độ(u,v) của rôbốt sẽ là : u := i + dx[h]; v := j + dy[h]; - Hai đỉnh (i1,j1,h1) và (i2,j2,h2) được gọi là kề nhau nếu qua 1 trong 2 thao tác + hoặc - kiện hàng được rôbốt đẩy hoặc kéo từ ô (i1, j1) đến ô (i2, j2) và rôbốt có thể di chuyển được từ ô (u1,v1) đến ô (u2,v2) ( u1 = i1+dx[h1]; v1=j1+dy[h1]; u2=i2+dx[h2]; v2= j2+dy[h2]). Tất nhiên các ô (i2,j2) và (u2,v2) phải đều không chứa kiện hàng. - Trọng số giữa 2 đỉnh là C (số công mà rô bốt đẩy kiện hàng từ ô (i1,j1) đến ô (i2,j2) ) cộng với công để rô bốt di chuyển từ ô (u1,v1) đến ô (u2,v2). Giả sử kiện hàng cần xếp đang ở ô (is,js) và hướng của rôbốt đứng cạnh kiện hàng là hs và ô cần xếp kiện hàng vào là ô (ie, je). Khi đó, ta sẽ dùng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh (is,js,hs) đến đỉnh (ie,je,he) với he thuộc {1 4}. Mảng d sẽ là 1 mảng 3 chiều: d[i,j,h]: Độ dài đường đi ngắn nhất từ đỉnh xuất phát (is,js,hs) đến đỉnh (i,j,h). Kết quả của bài toán sẽ là d[ie,je,he] với he thuộc {1 4}. Để ghi nhận phương án ta sẽ dùng 3 mảng 3 chiều tr1, tr2, tr3. Khi ta di từ đỉnh (i1,j1,h1) đến đỉnh (i2,j2,h2) thì ta sẽ gán: tr1[i2,j2,h2]:= i1; tr2[i2,j2,h2]:= j1; tr3[i2,j2,h2] := h1 để ghi nhận các thông tin: tọa độ dòng, cột, huớng của dỉnh trước đỉnh (i2,j2,h2). Từ 3 mảng
41. này ta có thể dễ dàng lần lại đường đi. Bài 2: Hành trình rẻ nhất: Thành phố Peace vừa đưa vào áp dụng một hệ thống điện tử tự động tính lệ phí sử dụng lệ phí đường giao thông. Một hệ thống được triển khai để phát hiện xe của bạn rẽ trái, rẽ phải, đi thẳng hoặc quay đầu và mỗi thao tác như vậy phải trả một lệ phí tương ứng. Đó là 1 $ cho mỗi lần rẽ trái, 5$ cho mỗi lần rẽ phải, đi thẳng về phía trước là miễn phí, quay đầu xe là bị cấm, ngoại trừ tình huống ở cuối phố khi không còn có thể đi thẳng, rẽ trái, hoặc rẽ phải được nữa. Trong trường hợp ngoại lệ bắt buộc phải quay đầu xe, bạn phải trả lệ phí 10$. Bạn được mời để thiết kế và đưa ra chỉ dẫn cho người đi xe đi sao cho phải trả lệ phí là ít nhất giữa 2 điểm bất kỳ trong thành phố. Rất may hệ thống đường giao thông của Peace có dạng bàn cờ. Ví dụ: ở ví dụ trên ký tự ’#’ để chỉ ra đoạn đường phố, còn ký tự ’.’ chỉ ra đoạn đường không là đường. Các đoạn đường phố đều có thể đi cả 2 chiều. Ký tự ’E’ chỉ ra vị trí xuất phát của xe ô tô có đầu xe hướng về phía Đông, còn ký tự ’F’ chỉ ra vị trí kết thúc. Lộ trình phải trả là 8$, trong đó ta phải thực hiên 3 lần rẽ trái và 1 lần rẽ phải để đến đích. Ta có thể thực hiện cách đi rẽ phải 2 lần đễ đến đích, nhưng cách đó lệ phí phải trả là 10$. Chiều cao và chiều rộng của bản đồ ít nhất là 4 và không quá 30. Bản đồ có đúng 1 điểm xuất phát và 1 điểm kết thúc. Luôn có đường đi từ điểm xuất phát đến điểm kết thúc. Luôn có một khung gồm toàn ký tự ’.’ viền bản đồ để không thể vượt ra ngoài bản đồ. Dữ liệu: Vào từ file văn bản ERP.INP gồm các dòng: - Dòng thứ nhất chứa 2 số nguyên dương h, w theo thứ tự là chiều cao h và chiều rộng của bản đồ. - Mỗi dòng trong h dòng tiếp theo chứa w ký tự. Mỗi ký tự chỉ là một trong số các ký tự sau: - ’.’: vị trí không có đường - ’#’: vị trí có đường của bản đồ. - ’E’: vị trí xuất phát, xe hướng đầu về phía Đông. - ’W’: vị trí xuất phát, xe hướng đầu về phía Tây. - ’N’: vị trí xuất phát, xe hướng đầu về phía Bắc. - ’S’: vị trí xuất phát, xe hướng đầu về phía Nam. - ’F’: vị trí kết thúc. Trong bản đồ có đúng 1 trong 4 ký tự ’E’, ’W’, ’N’, ’S’. Và đúng 1 ký tự F.
42. Kết quả ghi ra file văn bản ERP.OUT duy nhất một số là lệ phí của lộ trình rẻ nhất đi từ vị trí xuất phát đến vị trí kết thúc. Phân tích: Mô hình đồ thị: Mỗi đỉnh của đồ thị ở đây gồm 3 trường để phân biệt với các đỉnh khác: - i: Tọa độ dòng của nút mà ô tô đang đứng( i = 1 h) - j: Tọa độ cột của nút mà ô tô đang đứng (j = 1 w) - h: Hướng của đầu ô tô (h=1 4) Ta sẽ xét xem 1 ô (i,j) có phải là 1 nút không. Để dễ hình dung, ta sẽ quan niệm 1 nút ở đây cũng giống như 1 nút giao thông như trong thực tế. Ta sẽ xây dựng một mảng nut (nut(i,j)=true: ô (i,j) là 1 nút ) như sau: - Điều kiện cần để ô (i,j) là 1 nút là ô (i,j) đó phải là đường. - Các ô xuất phát và kết thúc đều là nút. - Nếu một ô (i,j) có 2 ô kề theo hướng 1 và 3 (hoặc 2 và 4) là đường và 2 ô kề theo hướng 2 và 4 (hoặc 1 và 3) không là đường thì ô (i,j) đó không là 1 nút. Ngược lại ô (i,j) đó là 1 nút. - Khi ta đang đứng ở ô (i1,j1) và ô tô đang quay đầu về hướng h1 ta sẽ tìm đỉnh kề bằng cách đi theo 4 hướng(1 4). Khi đi theo hướng h2 ta gặp một ô (i2,j2) là 1 nút. Khi đó đỉnh (i1,j1,h1) và (i2,j2,h2) được gọi là kề nhau. ở mỗi hướng ta sẽ đi cho đến khi gặp ô không là đường. - Trọng số ở đây sẽ được lưu trữ trong 1 hằng mảng cp(u,v) với ý nghĩa cp(u,v) là chi phí phải trả để ô tô đang quay đầu theo hướng u chuyển sang quay đầu theo hướng v. Khi đó, trọng số giữa 2 đỉnh (i1,j1,h1) và (i2,j2,h2) là cp(h1,h2). Hằng mảng chi phí như sau: cp :array[1 4,1 4] of integer= ( (0,5,10,1), (1,0,5,10), (10,1,0,5), (5,10,1,0) ); - Mảng d(i,j,h) sẽ lưu trữ chi phí ít nhất để đi từ đỉnh xuất phát (is,js,hs) đến đỉnh (i,j,h). Kết quả của bài toán sẽ là d(ie,je,he) với ô (ie,je) là ô kết thúc, he=1 4. Bài tập: Bài 1: Đường đi trong mê cung. Một mê cung gồm MxN ô vuông (M dòng, N cột, M, N ≤ 100). Mỗi ô vuông có thể có từ 0 đến 4 bức tường bao quanh. Cần phải đi từ bên ngoài vào mê cung, bắt đầu từ phía Tây, qua các ô của mê cung và thoắt ra khỏi mê cung về phía Đông. Chỉ được phép di chuyển theo 4 hướng Đông, Tây, Nam, Bắc và đi qua nơi không có tường chắn. 1. Trong trường hợp có đường đi, hãy tìm đường đi qua ít ô nhất. 2. Trong trường hợp trái lại, hãy tìm cách phá bỏ ít nhất một số bức tường để có đường đi. Nếu có nhiều phương án như vậy, hãy chỉ ra một phương án để đường đi qua ít ô nhất. Trạng thái của 1 ô được cho bởi một số nguyên trong khoảng 0 đến 15 theo quy tắc: bắt
43. đầu là 0 (Không có tường), cộng thêm 1(nếu có bức tường phía Tây), cộng thêm 2 (nếu có bức tường phía Bắc), cộng thêm 4 (nếu có bức tường phía Đông), cộng thêm 8 (nếu có bức tường phía Nam). Dữ liệu vào được cho bởi file văn bản MECUNG.INP bao gồm: - Dòng đầu ghi 2 số M, N - Các dòng tiếp theo ghi ma trận trạng thái của các ô gồm M dòng, N cột, trong đó giá trị dòng i cột j mô tả trạng thái của ô [i,j]. Các giá trị ghi trên 1 dòng cách nhau ít nhất 1 dấu cách. Kết quả ghi ra file văn bản MECUNG.OUT: 1. Trường hợp tìm thấy đường đi: - Dòng đàu ghi sô ô mà đường đi đi qua - Dòng tiếp theo ghi thông tin về đường đi gồm tọa độ dòng xuất phát, sau đó cách 1 dấu trắng, là xâu kí tự mô tả đường đi( theo hướng) viết liên tiếp nhau, gồm các ký tự D(đông), B(bắc), N(nam), T(tây). 2. Trường hợp không tìm thấy đường đi: - Dòng đầu ghi số 0 - Dòng thứ 2 ghi số bức tuờng phải phá - Dòng thứ ba ghi số ô mà đường đi đi qua - Dòng cuối ghi thông tin về đường di theo quy cách giống như trường hợp 1. Vidụ 1: Các bạn thấy đấy, một bài toán tưởng chừng như rất khó, nhưng sau khi phân tích và đưa nó về mô hình đồ thị ta có thể giải nó dễ dàng bằng thuật toán Dijkstra. Phần cài đặt các bài toán trên, tôi để các bạn tự làm. Nếu muốn có chương trình hoặc có gì không hiểu, xin liên hệ với toà soạn hoặc tôi và tôi sẽ cho bạn thấy sức mạnh của thuật toán Dijkstra! Chúc các bạn thành công Kỹ thuật tìm kiếm nhị phân giải một số bài toán tối ưu
44. Nguyễn Thanh Tùng Có lẽ ai trong chúng ta cũng biết về thuật toán tìm kiếm nhị phân và sự hiệu quả của nó. Sử dụng kỹ thuật tìm kiếm tương tự trong một số bài toán ta cũng đạt được kết quả rất khả quan. Sau đây là một số bài toán như vậy. I. Bài toán ví dụ. Thông tin về mạng giao thông gồm n thành phố cho bởi mảng A kích thước n?n gồm các phần tử aij là một giá trị nguyên dương chỉ tải trọng của tuyến đường nối 2 thành phố i,j. Nếu aij =0 thì giữa i,j không có đường nối. Tải trọng của một lộ trình từ thành phố s đến thành phố t (có thể đi qua một số thành phố trung gian) là tải trọng của tuyến đường có tải trọng nhỏ nhất thuộc lộ trình. Cho trước 2 thành phố s và t. Giả thiết luôn có lộ trình từ s đến t, hãy tìm một lộ trình từ s đến t có tải trọng lớn nhất. Thuật giải Đặt kmin = min {aij : aij >0}; kmax = max {aij: aij >0} Với k thuộc kmin kmax, ta xây dựng đồ thị G(k) gồm: n đỉnh ứng với n thành phố. 2 đỉnh i,j có cạnh nối nếu aij ≥k Nếu G(k) có một đường đi từ s đến t thì ta nói mạng giao thông có "lộ trình tối thiểu k" (Vì mọi cạnh của G(k) đều có trọng số ≥ k nên nếu G(k) có một đường đi từ s đến t thì đường đi đó có tải trọng ≥k). Bài toán được chuyển thành việc tìm giá trị k lớn nhất thuộc kmin kmax sao cho mạng giao thông có "lộ trình tối thiểu k". Khi đó đường đi từ s đến t tìm được chính là đường đi có tải trọng lớn nhất cần tìm. Ta sử dụng kỹ thuật tìm kiếm nhị phân dựa trên nhận xét: nếu mạng có "lộ trình tối thiểu p" và k là giá trị lớn nhất để có "lộ trình tối thiểu k" thì k thuộc p kmax. Ngược lại (nếu mạng không có "lộ trình tối thiểu p") thì k thuộc kmin p −1. Thủ tục Search thực hiện việc tìm kiếm nhị phân có dạng như sau: procedure search(x); begin l := kmin; r := kmax; repeat k := (l + r) div 2; check(k); if ok then l := k else r := k - 1; until l>=r; end; Trong đó thủ tục Check (k) thực hiện: 1. Xây dựng đồ thị G(k) như đã mô tả ở trên. 2. Dùng thuật toán DFS để kiểm tra xem có đường đi từ s đến t không. Nếu có thì đặt Ok là true, ngược lại thì Ok là false. Chương trình mẫu Để bạn đọc tiện theo dõi, tôi xin cung cấp chương trình mẫu của bài toán này. Để xử lí lỗi, một số đoạn chương trình hơi phức tạp so với mẫu trên. program weight;
45. const inp = ’weight.inp’; out = ’weight.out’; max = 100; type mang1 = array[1 max] of integer; mang2 = array[1 max, 1 max] of LongInt; var n,s,t,z : integer; k,l,r : LongInt; a : mang2; đ,kq : mang1; ok : boolean; ( ) procedure nhap; var i,j : integer; f : text; begin assign(f, inp); reset(f); readln(f, n, s, t); for i := 1 to n do begin for j := 1 to n do read(f,a[i,j]); readln(f); end; close(f); end; ( ) procedure chbi; var i,j : integer; begin l := maxLongInt; r := 0; for i := 1 to n do for j := 1 to n do if a[i,j] > 0 then begin if l > a[i,j] then l := a[i,j]; if r < a[i,j] then r := a[i,j]; end; end; ( ) procedure dfs(i : integer); var j : integer; begin
46. for j := 1 to n do if (đ[j] = 0) and (a[i,j] > = k) then begin đ[j] := i; dfs(j); end; end; ( ) procedure check; begin fillchar(đ,sizeof(đ),0); đ[s] := -1; dfs(s); if đ[t] = 0 then ok := false else ok := true; end; ( ) procedure search; begin repeat k := (l+r) div 2; check; if ok then l := k else r := k-1; until (l=r) or (l = r-1); if l = r-1 then begin k := r; check; if ok then exit; end; k := l; check; end; procedure trace; var i : integer; begin if not ok then exit; z := 0; i := t; repeat inc(z); kq[z] := i; i := đ[i]; until i = -1; end; ( ) procedure xuly; begin
47. search; trace; end; ( ) procedure inkq; var f : text; i : integer; begin assign(f, out); rewrite(f); writeln(f, k); for i := z downto 1 do write(f,’ ’,kq[i]); close(f); end; ( ) begin nhap; chbi; xuly; inkq; end. Nhận xét a. Với kỹ thuật tìm kiếm nhị phân, giải thuật trên chỉ cần thực hiện cỡ log2(kmax −kmin) lần kiểm tra (gọi thủ tục check). Do hạn chế aij là nguyên dương ≤ maxLongInt nên kmax − 32 2 kmin < 2 . Thủ tục check sử dụng thuật toán DFS có độ phức tạp tính toán là O(n ) nên giải thuật có thời gian thực thi cỡ C.O(n2) với C < 32. b. Ta không cần phải xây dựng G(k) một cách tường minh (tính hẳn thành ma trận kề) mà chỉ cần thay biểu thức kiểm tra có cạnh (i,j) không bằng biểu thức aij≥ k (trong thủ tục DFS). c. Giá trị tối ưu là một trong các phần tử của A. Trong bài này do aij là số nguyên nên ta xác định được khoảng tìm kiếm là miền nguyên kmin kmax và thực hiện việc tìm kiếm nhị phân trên miền đó. Nếu aij là số thực không thể kĩ thuật tìm kiếm nhị phân không áp dụng được trên miền thực [kmin, kmax]. Để áp dụng được ta phải sắp xếp tăng dần các phần tử dương của A (tối đa có n2 phần tử) rồi thực hiện tìm kiếm nhị phân trên dãy tăng dần đó. Khi đó thủ tục search cần thay đổi: l khởi tạo bằng 1, r khởi tạo bằng n2 và thủ tục check được gọi với tham số là d[k]: check(d[k]) trong đó d dãy tăng dần chứa n2 phần tử của A. Cũng có thể làm thế khi aij là số nguyên, tuy nhiên sẽ không hiệu quả vì sẽ tốn thời gian sắp xếp dãy và tốn không gian lưu trữ dãy đã sắp. II. Một số bài toán áp dụng 1. Bài toán 1 (đề thi HSGQG năm học 1999-2000) Có n công nhân và n công việc. Nếu xếp công nhân i nếu làm việc j thì phải trả tiền công là aij. Hãy tìm một cách xếp mỗi người một việc sao cho tiền công lớn nhất cần
48. trả trong cách xếp việc đó là nhỏ nhất. Thuật giải Nếu bài toán yêu cầu là tìm cách xếp việc sao cho tổng tiền công phải trả là nhỏ nhất thì đó là bài toán tìm cặp ghép đầy đủ trọng số cực tiểu. Tuy nhiên bài này là tìm cách xếp việc sao cho tiền công lớn nhất là nhỏ nhất. Ta có ý tưởng như sau: tìm số k bé nhất sao cho tồn tại một cách sắp xếp đủ n người, n việc và các yêu cầu về tiền công đều ≤ k. Dễ thấy việc tìm kiếm đó có thể thực hiện bằng kĩ thuật tìm kiếm nhị phân, và việc kiểm tra số k có thoả mãn không chính là việc kiểm tra đồ thị 2 phía G(k) có bộ ghép đầy đủ hay không. Đồ thị đồ thị 2 phía G(k) được xác định như sau: G(k) = (X,Y,E) Trong đó: X là tập n đỉnh ứng với n công nhân, Y là tập n đỉnh ứng với n công việc. Với i thuộc X, j thuộc Y nếu aij ≥ k thì cho (i,j) thuộc E (2 đỉnh i,j chỉ được nối với nhau nếu aij≥k) . Nếu k là số nhỏ nhất mà G(k) có bộ ghép đầy đủ thì bộ ghép đó chính là cách xếp việc cần tìm. Ta cũng có một số bài toán dạng tương tự: Bài toán 2. Thời gian hoàn thành Có n công nhân và n công việc. Nếu xếp công nhân i nếu làm việc j thì thời gian hoàn thành là Tij. Hãy tìm một cách xếp mỗi người một việc sao tất cả các công việc hoàn thành trong thời gian sớm nhất (các công việc được tiến hành song song). Bài toán 3. Năng suất dây truyền Dây truyền sản xuất có n vị trí và n công nhân (đều được đánh số từ 1 n). aij là năng suất (số sản phẩm sản xuất được trong một đơn vị thời gian) của công nhân i khi làm việc tại vị trí j. Với mỗi cách bố trí dây truyền (công nhân nào làm ở vị trí nào) năng suất của một vị trí là năng suất của công nhân làm việc tại vị trí đó. Năng suất chung của dây truyền là năng suất của vị trí kém nhất trên dây truyền. Hãy tìm cách bố trí dây truyền để có năng suất cao nhất. Chú ý: trong bài này ta phải tìm số k lớn nhất để G(k) có bộ ghép đầy đủ và 2 đỉnh i,j chỉ được nối với nhau nếu aij≥k. 2. Bài toán 4 (đề thi HSGQG năm học 1998-1999) Một đoạn đường quốc lộ có n cửa hàng, pi là khoảng cách của nó so với đầu đường. Nếu một cửa hàng có kho thì không cần phải đi lấy hàng, ngược lại thì phải đến lấy hàng ở cửa hàng có kho gần nhất. Hãy chọn k cửa hàng để đặt kho sao cho quãng đường đi lấy hàng dài nhất trong số các các cửa hàng còn lại là ngắn nhất. Thuật giải Bài này có thể làm bằng vét cạn (duyệt các tổ hợp). Ngoài ra còn có phương pháp quy hoạch động. Tuy nhiên chúng hoàn toàn không hiệu quả khi n lớn. Ta có thể áp dụng kỹ thuật tìm kiếm nhị phân kết hợp tham lam như sau. Thủ tục search tìm kiếm nhị phân giá trị d trong miền dmin dmax tương tự bài toán 1. Riêng thủ tục check(d) sẽ thực hiện khác. Thay vì kiểm tra xem có thể bố trí k kho sao cho quãng đường đi lấy hàng của mọi cửa hàng không có kho đều ≤d không, ta sẽ làm ngược lại: lần lượt bố trí các kho sao cho quãng đường đi lấy hàng của mỗi cửa hàng không bao giờ vượt quá d. Cách làm như sau: Gọi dij là khoảng cách giữa 2 cửa hàng i,j: dij = |pi −pj| Dùng 2 cửa hàng giả có chỉ số là 0 và t = n+1 làm biên sao cho di0 = dit = ∞ với mọi i.
49. Đặt 2 kho (giả) tại 2 cửa hàng đó. Với mỗi cửa hàng i từ 1 đến n: nếu i đã có kho thì chuyển sang cửa hàng tiếp theo, ngược lại thì: 1. Tìm cửa hàng x có kho gần i nhất về phía bên trái (x thuộc 0 i). 2. Tìm cửa hàng y có kho gần i nhất về phía bên phải (y thuộc i t). Nếu dix hoặc diy ≤ d thì quãng đường đi lấy hàng của i ≤ d (thoả mãn). Ngược lại tìm cửa hàng j chưa có kho xa i nhất về phía phải (j thuộc i y) mà dij ≤ d. Đặt kho tại j. Sau quá trình trên đếm số kho (tất nhiên không tính 2 kho 0 và t). Nếu số kho ≤ k thì đặt Ok là true. 3. Bài toán 5 (đề thi Olympic Tin học SV 2004) Có N hành khách, M khách sạn và K xe bus. Mỗi hành khách cần về một khách sạn và mỗi xe bus sẽ đi qua một số khách sạn nào đó. Xe bus i có q[i] chỗ ngồi. Hãy sắp xếp hành khách lên xe bus sao cho: 1. Mỗi xe bus không chứa nhiều hành khách hơn số ghế của nó. 2. Tất cả hành khách đều lên xe bus có đi qua khách sạn mình cần đến. 3. Số xe bus cần dùng là ít nhất. Thuật giải Bài này có một thuật giải áp dụng kĩ thuật tìm kiếm nhị phân như sau: ta sẽ tìm số T nhỏ nhất sao cho: chỉ dùng T xe bus là chở được hết khách thoả mãn 3 điều kiện trên. T sẽ được tìm bằng phương pháp nhị phân trong miền từ 1 đến K. Để kiểm tra giá trị T có thoả mãn không, ta sẽ tìm một tổ hợp T xe bus trong số K xe bus sao cho có thể sắp xếp N hành khách lên T xe bus đó thoả mãn 3 điều kiện trên. Ta chọn T xe bus bằng phương pháp duyệt tổ hợp và kiểm tra tổ hợp có được có thoả mãn không bằng thuật toán cặp ghép (hoặc luồng trên đồ thị 2 phía). Thuật toán luồng thực thi nhanh hơn, được mô tả như sau: 1. Xây dựng đồ thị 2 phía G(X,Y,E). Trong đó: X là các khách sạn, Y là các xe bus được chọn (T xe bus). Khả năng thông qua của mỗi đỉnh thuộc X là số hành khách đến khách sạn đó. Khả năng thông qua của mỗi đỉnh thuộc Y là số chỗ ngồi của xe bus đó. Nếu xe bus j đi qua khách sạn i thì đặt khả năng thông qua trên cạnh (i,j) là N, ngược lại thì đặt bằng 0. 2. Tìm luồng cực đại trên đồ thị G. Nếu giá trị luồng qua mỗi đỉnh ở X bằng khả năng thông qua của nó thì việc lựa chọn tổ hợp T xe bus đó là thoả mãn yêu cầu. Từ giá trị luồng ta cũng dễ dàng tìm được cách sắp xếp hành khách. Nếu các bạn không quen với thuật toán luồng thì có thể cài bằng thuật toán cặp ghép: 1. Xây dựng đồ thị 2 phía G(X,Y,E). Trong đó: X là các hành khách, Y là các chỗ ngồi trên các xe bus được chọn (có T xe bus được chọn, xe t có q[t] chỗ thì ta sinh q[t] đỉnh trong Y). Nếu xe bus tương ứng của j đi qua khách sạn của i thì đưa cạnh (i,j) vào E. 2. Tìm bộ ghép đầy đủ trên đồ thị G. Nếu có thì việc lựa chọn tổ hợp T xe bus đó là thoả mãn yêu cầu và bộ ghép đó chính là cách sắp xếp hành khách. Ta rút ra một số nhận xét sau: 1. Việc tìm kiếm nhị phân làm giảm số tổ hợp phải duyệt rất nhiều. Nếu vét cạn thuần tuý thì phải duyệt tối đa 2K tổ hợp. Tuy nhiên dùng phương pháp tìm kiếm nhị phân, nếu đã duyệt xong giá trị T thì ta không cần phải kiểm tra các tổ hợp nhiều hơn T phần tử (nếu T thoả mãn) hoặc ít hơn T phần tử (nếu T không thoả
50. mãn). 2. Ta chỉ cần tìm một tổ hợp thoả mãn, nên số tổ hợp cần duyệt còn ít hơn nữa (tìm thấy một tổ hợp thoả mãn thì không cần tìm các tổ hợp khác cùng số phần tử nữa). Và ta có thể áp dụng một số kĩ thuật tham lam trong khi duyệt như: ưu tiên chọn các xe bus chở được nhiều khách, đi qua nhiều khách sạn, không xét các xe bus không đi qua khách sạn nào trong số các khách sạn có hành khách cần đến 3. Cần giảm miền tìm kiếm kmin kmax xuống càng nhiều càng tốt (kết hợp với phương pháp tham lam chẳng hạn). Mặt khác ghi nhận lại những giá trị T đã xét để tránh phải xét lại một cách vô ích. Ta cũng có một bài toán giải bằng kĩ thuật tương tự: Bài toán 6. Mạng máy tính Mạng gồm N máy tính, một số cặp máy được nối với nhau bằng cáp. Có một chương trình điều khiển, máy nào được cài đặt chương trình đó thì có thể điều khiển tất cả các máy khác có cáp nối trực tiếp với nó (tất nhiên có thể điều khiển chính nó). Cần chọn ra một số ít máy nhất để cài chương trình sao tất cả các máy đều được điều khiển. Thuật giải Bài này chỉ giải được bằng cách duyệt tất cả các tổ hợp. Tuy nhiên áp dụng phương pháp tìm kiếm nhị phân sẽ giúp giảm số tổ hợp cần duyệt rất nhiều (lập luận như bài 5). Bạn đọc có thể cài theo cả 2 phương pháp để so sánh. Trên đây là một số bài toán áp dụng được kỹ thuật tìm kiếm nhị phân. Lời giải không kèm chương trình mẫu mà dành cho bạn đọc tự cài đặt vừa để tránh bài viết dài một cách không cần thiết vừa để bạn đọc rèn luyện kỹ năng lập trình. Bạn đọc nào có nhu cầu về chương trình mẫu để tham khảo, xin liên hệ với tác giả qua email: TungNT31@yahoo.com Độ phực tạp thuật toán và tổ chức dữ liệu Trần Đỗ Hùng Trong Tin học, khi phân tích một bài toán người ta cũng tìm giả thiết và kết luận. Giả thiết là những dữ liệu đưa vào máy tính xử lí kèm theo các điều kiện ràng buộc chúng (gọi là input) và kết luận là những thông tin thu được sau xử lí (gọi là output). Bài toán trong Tin học có thể hiểu là bất cứ công việc gì có thể giao cho máy tính thực hiện: vẽ một chữ, một hình trên màn hình cũng là bài toán! Phương pháp giải bài toán có thể cài đặt thành chương trình máy tính (viết bằng ngôn ngữ lập trình) gọi là thuật toán. Thuật toán được thể hiện là dãy các thao tác có thứ tự và hữu hạn để sau khi thực hiện dãy thao tác này, từ input của bài toán sẽ nhận được output của bài toán. Một bài toán có thể được giải bằng một vài thuật toán khác nhau. Người ta cần lựa chọn thuật toán thích hợp và do đó cần đánh giá thuật toán. Để đánh giá thuật toán người ta dựa vào khái niệm độ phức tạp thuật toán. Độ phức tạp của thuật toán là đại lượng đánh giá lượng thời gian và không gian bộ nhớ dành cho thực hiện thuật toán. Từ ý nghĩa thực tiễn của các bài toán khác nhau, có khi người ta quan tâm tới thuật toán đòi hỏi ít thời gian thực hiện, nhưng cũng có khi lại quan tâm nhiều hơn tới thuật toán
51. cho phép cài đặt dữ liệu chiếm ít không gian bộ nhớ. Độ phức tạp về không gian bộ nhớ của thuật toán phụ thuộc phần lớn vào cấu trúc dữ liệu được sử dụng khi cài đặt thuật toán. Độ phức tạp về thời gian thực hiện (còn gọi là độ phức tạp tính toán) được đánh giá sơ bộ dựa vào số lượng các thao tác cơ bản (gán, so sánh 2 số nguyên, cộng, nhân 2 số nguyên ). Số lượng các thao tác này là một hàm số của kích cỡ dữ liệu input. Nếu kích cỡ dữ liệu input là N thì thời gian thực hiện thuật toán là một hàm số của N. Với một thuật toán trên các bộ dữ liệu input khác nhau (cùng kích cỡ N) có thể các hàm số này là khác nhau; song điều quan tâm hơn cả là mức độ tăng của chúng như thế nào khi N tăng đáng kể. Ví dụ: Xét thuật toán tìm giá trị lớn nhất trong dãy N số sau đây: Input. Số nguyên dương N, dãy N số A1, A2, , AN Output max{A1, A2, , AN} Bước 1. max ← A1 Bước 2. for i ← 2 to N do If max < Ai then max ← Ai Bước 3. Hiện max Trường hợp xấu nhất: dữ liệu vào là dãy sắp tăng, thì số thao tác cơ bản là f(N)=2N+1 Trường hợp tốt nhất: giá trị lớn nhất ở ngay đầu dãy, thì thao tác cơ bản là g(N)= N. Khi N lớn đáng kể thì f(N) và g(N) coi như xấp xỉ nhau và xấp xỉ hàm bậc nhất của N. Vậy trong trường hợp này ta kí hiệu độ phức tạp thời gian của thuật toán trên là O(N). Người ta phân lớp các bài toán theo độ phức tạp thuật toán. Có thể liệt kê một số lớp sau có độ phức tạp tăng dần: - Độ phức tạp hằng O(1) - Độ phức tạp lôgarit O(logN) - Độ phức tạp tuyến tính O(N) - Độ phức tạp NlogN O(NlogN) - Độ phức tạp đa thức O(Nk) k: hằng nguyên - Độ phức tạp luỹ thừa O(aN) a: cơ số nguyên dương khác 1 - Độ phức tạp giai thừa O(N!) Tính hiệu quả (về thời gian) của thuật toán là đánh giá về thực hiện thuật toán trong một khoảng thời gian cho phép. Tính hiệu quả được nhận xét gián tiếp qua độ phức tạp tính toán của thuật toán. Độ phức tạp lớn thì thời gian thực hiện lâu hơn. Chúng ta xét hai bài toán quen thuộc sau đây làm ví dụ về lựa chọn thuật toán và cài đặt dữ liệu: Bài toán 1. Dãy đơn điệu tăng dài nhất Cho mảng ĂN) gồm N phần tử nguyên. Hãy xoá đi một số ít nhất các phần tử của mảng để những phần tử còn lại lập thành dãy tăng dài nhất. Dữ liệu vào từ file văn bản DAYTANG.IN Dòng đầu là số nguyên N (1≤ N ≤ 30000) Tiếp theo là N số nguyên lần lượt từ phần tử đầu đến phần tử cuối của mảng. Kết quả ghi ra file văn bản DAYTANG.OUT Dòng đầu là số K là số lượng các phần tử còn giữ lại Tiếp theo là K dòng, mỗi dòng ghi 2 số: số thứ nhất là giá trị phần tử giữ lại, số thứ hai là chỉ số (trong mảng ban đầu) của phần tử được giữ lại này. DAYTANG.IN
52. 10 1 2 8 10 5 9 4 3 6 7 DAYTANG.OUT 5 1 1 2 2 5 5 6 9 7 10 Bài toán này thường được giải bằng Qui hoạch động. Có thể cài đặt dữ liệu như sau: Xây dựng 2 mảng một chiều T và mảng D với ý nghĩa sau: D[i] là độ dài của dãy kết quả khi bài toán chỉ xét dãy A1 , A 2 , , Ai và nó được tính theo công thức truy hồi: D[i] = Max { D[i], D[j] +1 với mọi j mà j < i và Aj ≤A i } (1) T[i]=j là chỉ số (trong dãy A ban đầu) của phần tử đứng ngay trước A i trong dãy kết quả. Cách tìm T[i]: duyệt mảng A từ vị trí 1 đến vị trí i-1, vị trí j thoả mãn có D[j] lớn nhất và A[j]≤A[i]. Khởi trị: T[1]:= 0 ; D[1]:= 1; Ví dụ: Khi duyệt ngược tìm kết quả ta tiến hành như sau: Tìm phần tử lớn nhất trong D, giả sử đó là D[i], ta đổi dấu của D[i] coi như đánh dấu nó, tìm tiếp phần tử j = T[i], lại đổi dấu D[j], quá trình cứ như thế lùi chỉ số j đến khi j=0 Kết qủa được dãy con dài nhất là : 3 4 7 9 10 Độ phức tạp tính toán của thuật toán trên là O(N2). Với N=30000 thì mặc dù có thể tổ chức các mảng động một chiều để cài đặt dữ liệu thực hiện thuật toán nhưng cũng không thể chấp nhận được vì thời gian thực hiện thuật toán quá lâu! Ta tìm kiếm một thuật toán khác (vẫn bằng qui hoạch động): Về cài đặt dữ liệu: + Mảng một chiều A là dãy số đã cho ban đầu. + Mảng một chiều L dùng để lưu các chỉ số (trong dãy A ban đầu) của một số phần tử của A xếp theo giá trị tăng dần (tạo thành một dãy trung gian là H) để dựa vào H ta có thể tìm ra giá trị mảng Tr. + Mảng Tr có ý nghĩa như sau: Tr^[k] là chỉ số (trong dãy A ban đầu) của phần tử đứng
53. trước phần tử Ak trong dãy kết quả. Dựa vào mảng Tr sẽ tìm ra dãy kết quả. + Dùng biến d để theo dõi độ dài dãy kết quả Thuật toán: - Ban đầu dãy kết quả có độ dài d=1, phần tử đầu của dãy H là A1. Xác nhận chỉ số (trong dãy A ban đầu) của phần tử đầu dãy H là L[1]:=1, chỉ số (trong dãy A ban đầu) của phần tử cuối dãy H là L[d]=1. Chưa có phần tử trước A1 nên tạm coi chỉ số của phần tử trước A1 là 0 (gán Tr^[1] :=0;) - Duyệt tuyến tính các phần tử từ A2 đến AN. Giả sử đã xét đến Ak. + Nếu Ak = AL[d] thì thêm Ak vào cuối dãy H(điều này tương ứng với sự kiện dãy kết quả được kéo dài thêm 1 phần tử nữa vì phần tử Ak có chỉ số k > L[d]. Tuy nhiên, chú ý rằng dãy H không đồng nhất với dãy kết quả). Gán Tr^[k]:= L[d]; Inc(d); L[d]=k; + Trường hợp còn lại: dùng phương pháp tìm kiếm nhị phân để biết vị trí Ak trong dãy H={AL[1], AL[2], , AL[d] ). Giả sử tìm được chỉ số t sao cho A L[t-1] ≤ Ak ≤ AL[t] thì ta gán Tr^[k] :=L[t-1]; L[t] := k; - Dựa vào mảng Tr^ tìm ngược dãy kết quả (dài bằng d). Chú ý rằng phần tử cuối cùng của dãy kết quả là AL[d] Thủ tục chính của chương trình theo thuật toán trên là: procedure lam; var l : mg; i,j,k,t : integer; f : text; begin new(tr); { tr^[i]=j nghĩa là trong dãy tăng kết quả: liền trước A[i] là A[j] } fillchar(l,sizeof(l),0); fillchar(tr^,sizeof(tr^),0); l[1]:=1; {Xác nhận phần tử đầu của dãy H có chỉ số là 1 } d:=1; {d: số lượng phần tử của dãy kết qủa} for k:=2 to n do {duyệt dãy A, từ phần tử thứ 2} begin if â[k] =â[l[d]] then begin tr^[k]:=l[d];{xác nhận l[d] là chỉ số của phần tử có thể đứng trước â[k] trong dãy kết quả } inc(d); l[d]:=k; {thêm phần tử â[k] vào cuối dãy H} end else {bằng tìm kiếm nhị phân vị trí của â[k] trong dãy H}
54. begin i:=1;j:=d; while i begin t:=(i+j)div 2; if â[k]>=â[l[t]] then i:=t+1 else j:=t; end; t:=(i+j) div 2; tr^[k]:=l[t-1]; l[t]:=k; {phần tử thứ t trong H là Â[k]} end; end; k:=l[d]; {tìm vết dãy kết quả, lần từ cuối dãy} fillchar(l,sizeof(l),0); assign(f,fo); rewrite(f); writeln(f,d); while k>0 do {ghi lại vết dãy kết quả} begin l[k]:=1; k:=tr^[k]; end; for k:=1 to n do if l[k]=1 then writeln(f,â[k],#32,k); {ghi kết quả vào file output} close(f); end; Độ phức tạp thời gian của thuật toán này là O(NlogN) nên có thể chấp nhận về thời gian cho phép khi N=30000. Bài toán 2. Palindrome (time limit 2s) Một xâu được gọi là xâu đối gương nếu đọc từ trái qua phải cũng giống như đọc từ phải qua trái. Ví dụ xâu "madam" là một xâu đối gương. Bài toán đặt ra là cho một xâu S gồm các kí tự thuộc tập M=[’a’ ’z’], hãy tìm cách chèn vào xâu S các kí tự thuộc tập M tại các vị trí bất kì với số lượng kí tự chèn vào là ít nhất để xâu S thành xâu đối gương. Ví dụ: xâu: "adbhbca" ta sẽ chèn thêm 2 kí tự ( c và d) để được xâu đối gương "adcbhbcda". Dữ liệu vào trong file PALIN.IN có dạng: Dòng thứ nhất là một số nguyên dương T (T <=10) là số bộ test T dòng sau, mỗi dòng chứa một xâu S, độ dài mỗi xâu không vượt quá 500. Kết quả ghi ra file PALIN.OUT có dạng: Gồm nhiều dòng, mỗi dòng là một xâu đối gương sau khi đã chèn thêm ít kí tự nhất vào xâu S tương ứng ở file input.
55. Thuật toán. Dùng Qui hoạch động: Gọi L[i,j] là số kí tự cần chèn thêm vào đoạn S[i j] để đoạn này thành đối gương (các đoạn S[1 i-1] và S[j+1 n] đã đối xứng nhau rồi) thì: L[i,j] = Min {L[i+1,j-1}, L[i+1,j]+1, L[i,j-1]+1} (2) L[i,j] = L[i+1,j-1] chỉ khi S[i]=S[j] L[i,j] = L[i+1,j]+1khi S[i] S[j] và ta chèn thêm S[j] vào bên trái S[i]. Đánh dấu hiện tượng này bằng bít 0 trên mảng đánh dấu D. Nhãn L[1,N] chính là số kí tự chèn thêm cần tìm. Do kích thước đề bài, không thể tổ chức mảng hai chiều L (kể cả cách tổ chức theo kiểu mảng động cũng không thể được, vì mảng hai chiều kích thước 500?500 phần tử kiểu Integer là quá lớn). Vì vậy điều chủ chốt để thực hiện thuật toán này là vấn đề cài đặt dữ liệu theo cách khác hợp lí hơn. Ta có nhận xét: theo công thức truy hồi (2) thì L[i,j] chỉ liên quan tới L[i+1,j-1] , L[i,j-1] và L[i+1,j]. Gọi độ dài đoạn S[i j] là k=j-i+1. (hay là j=i+k-1) Thay cho L[i, j] ta dùng C3[i] (ứng với khoảng cách từ i tới j là k). Thay cho L[i+1, j] ta dùng C2[i+1] (ứng với khoảng cách từ i+1 tới j là k-1). Thay cho L[i, j-1] ta dùng C2[i] (dùng C2 vì ứng với khoảng cách từ i tới j-1 vẫn là k-1). Thay cho L[i+1, j-1] ta dùng C1[i+1] (ứng với khoảng cách từ i+1 tới j-1 là k-2) Công thức truy hồi (2) có dạng mới là: C3[i] = Min {C2[i] +1, C2[i+1] +1, C1[i+1]} (2.b) C3[i] = C1[i+1] khi S[i]=S[j] C3[i] = C2[i+1] +1 khi S[i] S[j] và chèn thêm S[j] vào bên trái S[i]. Hiện tượng này đã được đáh dấu bằng bít là 0 khi khởi trị D. Vậy ta chỉ cần dùng 3 mảng một chiều là C1(500), C2(500), C3(500) và một mảng hai chiều là D (500, 500 div 8). Sau đây là toàn bộ chương trình giải bài toán 2 const maxn = 501; fi = ’palin.in’; fo = ’palin.out’; type m1 = array[1 maxn]of char;
56. m2 = array[1 2*maxn]of char; m3 = array[0 maxn div 8]of byte; m4 = array[0 maxn]of m3; m5 = array[0 maxn]of integer; var f,g : text; a : m1; d : m4; {đánh dấu } c1,c2,c3 : m5; {3 mảng 1 chiều thay cho mảng hai chiều L} kq : m2; {xâu đối gương cần tìm} dau,cuoi,sol,n,test,sotest :integer; procedure readinp; begin n:=1; while not seekeoln(f) do begin read(f,a[n]); if a[n]=’ ’ then if n>1 then break else continue; inc(n); end; readln(f); dec(n); end; procedure batbit(i,j :integer); var v,k :integer; begin v:=j div 8; k:=j mod 8; d[i,v]:=d[i,v] or (1 shl k); end; procedure init_data; var i,j,k :integer; begin fillchar(d,sizeof(d),0); fillchar(c1,sizeof(c1),0); fillchar(c2,sizeof(c2),0); fillchar(c3,sizeof(c3),0); for i:=1 to n-1 do {xét các xâuchỉ gồm 2 kí tự liên tiếp a[i] và a[i+1]} begin j:=i+1; if a[i]<>a[j] then begin c3[i]:=1; {phải chèn vào 1 kí tự} batbit(i,j); {đánh dấu hiện tượng chèn này: chèn a[i] vào bên trái a[i+1]} end;
57. end; end; procedure process; var k,i,j :integer; begin init_data; for k:=3 to n do begin {c1 lưu trạng thái của c2} move(c2,c1,sizeof(c2)); { c2 lưu trạng thái của c3} move(c3,c2,sizeof(c3)); for i:=1 to n-k+1 do begin j:=i+k-1; if a[i]=a[j] then begin c3[i]:=c1[i+1]; {không cần chèn thêm kí tự nào} end else begin if c2[i] begin c3[i]:=c2[i]+1; {chèn a[i] vào bên trái a[j]} batbit(i,j); {đánh dấu hiện tượng chèn này} end else c3[i]:=c2[i+1]+1; {chèn a[j] vào bên phải a[i] } end; end; end; end; function getbit(i,j :integer):byte; var p,k,v :integer; begin v:=j div 8; k:=j mod 8; p:=d[i,v] and (1 shl k); getbit:=ord( p>0 ); end; procedure print; var i :integer; procedure find(left,right :integer); var k :byte; begin if left>right then exit;
58. if a[left]=a[right] then begin inc(dau); kq[dau]:=a[left]; if left begin dec(cuoi); kq[cuoi]:=a[right]; end; find(left+1,right-1); exit; end; k:=getbit(left,right); if k=1 then begin inc(dau); kq[dau]:=a[right]; dec(cuoi); kq[cuoi]:=a[right]; find(left,right-1); end else begin dec(cuoi); kq[cuoi]:=a[left]; inc(dau); kq[dau]:=a[left]; find(left+1,right); end; end; begin fillchar(kq,sizeof(kq),0); sol:=c3[1]; dau:=0; cuoi:=n+sol+1; find(1,n); {Tìm lại kết quả bằng đệ qui } for i:=1 to n+sol do write(g,kq[i]); writeln(g); end; BEGIN assign(f,fi); reset(f); assign(g,fo); rewrite(g); readln(f,sotest); for test:=1 to sotest do begin readinp; process; print;
59. end; close(f); close(g); END. Qua hai bài toán trên, nhận thấy rằng khi cố gắng tìm tòi, lựa chọn thuật toán và cài đặt dữ liệu có thể giải được những bài toán đã quen thuộc đạt yêu cầu tốt hơn trước: thời gian thực hiện nhanh và thích ứng được với các bộ dữ liệu vào có kích cỡ lớn hơn. Trần Đỗ Hùng giáo viên PTTH Nguyễn Huệ Hà Tây Qui hoạch động với các bài toán có dữ liệu lớn Cao Minh Anh Như chúng ta đã biết khi giải một bài toán thì vấn đễ thời gian và dữ liệu là cốt lõi. Vì thế trong các kì thi chúng ta thường gặp các bài có dữ liệu lớn. Những bài nay thường rất khó bởi vì ta vừa phải giải quyết vấn đề dữ liệu, vừa phải giải quyết vấn đề thời gian. Vì thế khi có được một thuật toán hay tối ưu vẫn chưa chắc giải được những bài này, tối ưu chưa đủ mà cần phải có phương pháp cài đặt tốt để có thể giải quyết về mặt dữ liệu. Quy hoạch động tượng trưng cho sự tối ưu hoá về thời gian vì thế tôi xin trình bày một số bài toán dữ liệu lớn dùng quy hoạch động đễ giải và cách thức xử lý của từng bài toán. Bài 1: Tìm số lớn nhất. Cho n số nguyên (n<=232) trong file max.inp, hãy tìm số lớn nhất trong n số nguyên đã cho. Kết quả được viết vào file max.out gồm 2 số M, P − trong đó M là số lớn nhất và P là vị trí của nó trong n số nguyên. Nếu có nhiều kết quả đưa ra số lớn nhất có vị trí lớn nhất. Ví dụ: Đây là một bài quy hoạch động rất đơn giản, tôi muốn đề cập để các bạn thấy rằng bài toán tìm max là một bài toán rất cơ bản, ai học cũng biết bài toán này nhưng chắc các bạn sẽ không nghĩ rằng đây là một bài toán qui hoạch động đơn giản mà ai cũng có thể làm được. Tôi muốn giới thiệu với các bạn bài toán tìm max với dữ liệu lớn dùng file để chứa
60. các phần tử thay vì dùng mảng, như thế ta vừa tiết kiệm được dữ liệu vừa giải quyết bài toán nhanh nhất. uses crt; const fi=’max.inp’; go=’max.out’; var max,n,k :longint; f,g :text; procedure Openf; begin assign(f,fi); reset(f); assign(g,go); rewrite(g); end; procedure Closef; begin close(f); close(g); end; procedure Main; var i:integer; begin max:=-maxlongint; readln(f,n); for i:=1 to n do begin readln(f,k); if k>max then max:=k; end; end; procedure Print; begin writeln(g,max); end; begin clrscr; Openf; Main;
61. Print; Closef; end. Bài 2: Cho N số tự nhiên nằm trong khoảng [0 9], hãy tìm dãy tăng dài nhất dài nhất. Dữ liệu vào: File daytang.inp gồm dòng đầu tiên là số N.N dòng tiếp theo là N số tự nhiên. Dữ liệu ra: File daytang.out gồm 2 số M là chiều dài của dãy tăng dài nhất. Ví dụ: - Nếu bài trên với dữ liệu N khoảng 10000 thì ta có thể giải quyết theo cách sau: + Nhập N số trên vào mảng a. + Gọi Fx[i] là chiều dài dài nhất của dãy tăng kết thúc là phần tử a[i]. Như vậy ta có chương trình quy hoạch đơn giản như sau: procedure Quyhoach; var i,j:integer; begin for i:=1 to n do fx[i]:=1; for i:=2 to n do for j:=i-1 downto 1 do if a[j]<=a[i] then if fx[i] Muốn xuất kết quả ta chỉ cần writeln(Max(fx[1],fx[2], ,fx[n])); Nhưng nếu bài toán trên với dữ liệu lớn không thể bỏ vào mảng thì ta không thể giải quyết theo phương pháp trên được. Ta chú ý các số chỉ nằm trong khoảng [0 9] vì thế thay vì dùng mảng Fx[i] là chiều dài dãy tăng lớn nhất khi a[i] cuối dãy ta có thể dùng mảng Fx[i] là chiều dài dãy tăng lớn nhất khi i đứng cuối dãy. Như thế chỉ cần khai báo: Var fx : array[0 9] of longint; Như vậy khi nhập một số k. Thì số k có thể đặt sau dãy tăng có tận cùng là 0,1,2 k. Như vậy thì fx[k] sẽ bằng Fx[k]:=max(Fx[0]+1,Fx[1]+1,Fx[2]+1, ,fx[k]+1) Với cách làm như thế thì bài toán trở nên đơn giản hơn rất nhiều vài có thể giải quyết với N rất lớn. Đây là toàn bộ chương trình:
62. uses crt; const fi=’daytang.inp’; go=’daytang.out’; var fx :array[0 9] of longint; n,k,max :longint; f,g :text; procedure Openf; begin assign(f,fi); reset(f); assign(g,go); rewrite(g); end; procedure Closef; begin close(f); close(g); end; procedure Quyhoach; var i,j:integer; begin readln(f,n); for i:=1 to n do begin readln(f,k); for j:=k downto 0 do if fx[k] end; end; procedure Findmax; var i:integer; begin max:=0; for i:=0 to 9 do if fx[i]>max then max:=fx[i]; end; procedure Xuat; var i:integer;
63. begin writeln(g,max); end; begin clrscr; openf; Quyhoach; Findmax; Xuat; Closef; end. Chúng ta có thể dùng với các số tự nhiên lớn hơn không nhất thiết là từ [0 9] chỉ cần khai báo mảng Fx lớn hơn là được.Sau đây chúng ta chuyển qua một bài toán dùng qui hoạch động rất hay đó là bài Cấp số cộng. Bài 3: Cấp số cộng (Đề thi quốc gia bảng Bm). Cho một tệp văn bản gồm N (N rất lớn) số nguyên a1, a2, a3, ,an với Abs(ai)<=30 000. Hãy tìm trong dãy A đó một dãy con dài nhất lập thành một dãy cấp số cộng có công sai là d. Với 0<D<=100. Dữ liều vào: Csc. INP - Dòng đầu ghi số N - N dòng tiếp theo ghi các số ứng với dãy A Dữ liệu ra: Csc.OUT - Dòng đầu ghi số M là số phần tử và công sai của dãy cấp số cộng đó - M dòng tiếp theo ghi số chỉ số của các số thuộc cấp số cộng. Ví dụ: Nếu dữ liệu nhỏ N=10000 thì ta có thể dùng phương pháp duyệt đơn thuần để giải bài toán trên một cách dễ dàng, nhưng với dữ liệu N<=100000 thì quả là lớn,việc lưu các số này vào mảng là một chuyện không thể, huống chi ta phải duyệt với độ phức tạp N*(N+1 )/2. Nếu duyệt thì ta sẽ không giải quyết được dữ liệu cũng như thời gian. Các bạn hãy chú ý rằng nếu biết công sai và số đầu hay số cuối thì ta có thể biết được dãy cấp số cộng nó như thế nào, tại sao ta không tìm dãy cấp số cộng dài nhất ứng với một
64. công sai nào đó. Giả sử cần tìm chiều dài lớn nhất của dãy cấp số cộng có công sai là d + Ta gọi Fx[i] là chiều dài dãy cấp số cộng dài nhất kết thúc bằng i. Suy ra:Fx[i]=Fx[i-d]+1; Vì đã biết công sai là d nên khi nhập được số k nào đó thì muốn tạo thành cấp số cộng tận cùng bằng k thì số trước đó phải là (k-d). Như vậy chiều dài dài nhất của dãy cấp số cộng tận cùng bằng k sẽ bằng chiều dài dài nhất của dãy cấp số cộng tận cùng là k-d cộng 1. Ta có thể khai báo như sau: Type arr=array[0 30000] of word; var a,b :^arr; Nhận xét chiều dài tối đa của dãy cấp số cộng là 60001 nên ta khai báo word là vừa đủ. + Với mảng a dùng cho các số không âm,mảng b dành cho các số âm. A[i] là chiều dài dài nhất của dãy cấp số cộng tận cùng bằng i, B[i] là chiều dài dài nhất của dãy cấp số cộng tận cùng bằng -i, Vậy để giải quyết bài toán Cấp số cộng ta chỉ cần duyệt với từng công sai từ 1౰0 là được. Sau đây là bài giải: uses crt; const fi=’csc.inp’; go=’csc.out’; Type arr=array[0 30000] of word; var a,b :^arr; max,k,s,d,luu,sc,sd,n :longint; f,g :text; procedure Openf; begin assign(f,fi); reset(f); assign(g,go); rewrite(g); end; procedure Closef; begin close(f); close(g); end; procedure Main; var i:integer;
65. begin max:=0; for i:=1 to 100 do begin openf; New(a); New(b); readln(f); fillchar(â,sizeof(â),0); fillchar(b^,sizeof(b^),0); while not eof(f) do begin d:=max; readln(f,k); s:=k-i; if s>=0 then â[k]:=â[s]+1 else begin if k>=0 then â[k]:=b^[abs(s)]+1 else b^[abs(k)]:=b^[abs(s)]+1; end; if max if max if d<>max then begin luu:=i; sc :=k; end; end; dispose(a); dispose(b); closef; end; end; procedure Print; var i:integer; begin Openf; writeln(g,max,luu:4); sd:=sc-(max-1)*luu; readln(f,n); for i:=1 to n do begin readln(f,k); if k=sd then
66. begin writeln(g,i); sd:=sd+luu; end; end; Closef; end; begin clrscr; Main; Print; end. Bài 4: Xâu fibonacci. Định nghĩa: Dãy xâu fibo được xây dựng theo nguyên tắc sau: + F1 =’B’;F2 =’A’; + Fk = Fk-1 + Fk-2. Yêu cầu: Tính số lần xuất hiện của SR trong Fn(tức là số xâu con các kí tự liên tiếp nhau bằng SR). Hai xâu con được gọi là khác nhau nếu khác nhu ít nhất một ký tự.(N<=100). Dữ liệu vào: File FSTR.inp + Dòng đầu tiên là số N. + Dòng tiếp theo là xâu SR.(length(SR)<=15). Dữ liệu ra: File FSTR.out Số lần xuất hiện tìm được. + Phương pháp 1: Thuật toán lùa bò vào chuồng. Với phương pháp này chỉ giải quyết với dữ liệu không lớn lắm (N<=35) nhưng cũng là một cách để cách bạn tham khảo. + Tìm Fn. Ta sẽ tìm Fn và đưa đó vào file để chứa. Chuơng trình tìm và xuất Fn rất đơn giản như sau: Function Fibo(N:integer):integer; Begin If n=1 then write(g,’B’) Else If n=2 then write(g,’A’) Else Fibo:=Fibo(n-2)+Fibo(n-1); End; + Nhập xâu SR. Ta tưởng tượng rằng ’A’ chính là 1,’B’ chính là 0. Lúc này SR là biểu diễn nhị phân của số K. Vấn đề tìm k khá đơn giản. Sau khi tìm được k, ta mở file chứa Fn ra,sao đó lấy từng đoạn liên tiếp có chiều dài length(SR) ra chuyển ra nhị phân (với ’A’ chính là ’1’,’B’ là ’0’), nếu chuyển ra nhị phân bằng đúng k thì tăng đếm lên 1. Sau khi đọc hết file thì biến đếm chính là kết quả cần tìm. Ví dụ: