Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Tin học Skkn phương pháp giải bài toán tin bằng quy hoạch động ...

Tài liệu Skkn phương pháp giải bài toán tin bằng quy hoạch động

.PDF
28
1685
84

Mô tả:

SỞ GIÁO DỤC VÀ ĐÀO TẠO GIA LAI TRƯỜNG THPT CHUYÊN HÙNG VƯƠNG TỔ TOÁN TIN ĐỀ TÀI: “PHƯƠNG PHÁP GIẢI BÀI TOÁN TIN BẰNG QUY HOẠCH ĐỘNG” Người thực hiện: LÊ VĂN TRƯỜNG Giáo viên: Tin học Pleiku, 2/2014 Phương pháp giải các bài toán - tin bằng quy hoạch động PHƯƠNG PHÁP GIẢI BÀI TOÁN TIN BẰNG QUY HOẠCH ĐỘNG A. PHẦN MỞ ĐẦU I. Lí do chọn đề tài Hiện nay tài liệu dạng chuyên đề nâng cao phục vụ cho việc bồi dưỡng học sinh giỏi môn Tin học là chưa thật sự đầy đủ và tổng quát, đặc biệt là những chuyên đề khá mới và rất khó của thế giới, giờ đã được đưa vào các đề thi học sinh giỏi Quốc gia như: Quy hoạch động, Luồng cực đại trên mạng,… Từ thực tiễn giảng dạy tin tại trường THPT Chuyên Hùng Vương tôi thấy rằng để đạt hiệu quả cao trong bồi dưỡng học sinh giỏi, cần có cách thiết kế bài giảng cho phù hợp với nội dung kiến thức dựa trên tài liệu chuyên đề đầy đủ rõ ràng từ lý thuyết đến bài tập và theo đúng xu thế chung của các kì thi học sinh giỏi các cấp hiện nay và trong tương lai, điều kiện tiến quyết để mang lại thành tích cao cho đội tuyển học sinh giỏi trong các kì thi. Xuất phát từ cơ sở trên, tôi đã chọn đề tài “Phương pháp giải bài toán tin bằng quy hoạch động”, sáng kiến này sẽ giúp học sinh của trường THPT Chuyên Hùng Vương vận dụng các kiến thức vào làm tốt các dạng đề thi Quốc gia có liên quan về luồng cực đại, phục vụ cho việc bồi dưỡng học sinh giỏi của trường. II. Mục đích của đề tài - Giới thiệu phương pháp giải các bài toán - tin bằng quy hoạch động (QHĐ) - Các bước giải bài toán - tin bằng phương pháp QHĐ - Giải một số bài toán bằng phương pháp quy hoạch động điển hình - Một số bài tập áp dụng có hướng dẫn giải thuật cho học sinh tự làm. - Từ đó giúp học sinh của trường THPT Chuyên Hùng Vương vận dụng các kiến thức vào làm tốt các dạng đề thi Quốc gia có dạng quy hoạch động. Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 1 Phương pháp giải các bài toán - tin bằng quy hoạch động III. Nhiệm vụ của nghiên cứu - Giới thiệu phương pháp giải các bài toán - tin bằng quy hoạch động (QHĐ) - Các bước giải bài toán - tin bằng phương pháp QHĐ - Hướng dẫn giải một số bài toán bằng phương pháp quy hoạch động điển hình - Một số bài tập áp dụng có hướng dẫn giải thuật cho học sinh tự làm. - Đưa ra một số bài tượng tự để các em học sinh giỏi vận dụng thực hành trên máy. IV. Đối tượng nghiên cứu - Học sinh giỏi tin học 11, 12 của trường THPT Chuyên Hùng Vương. V. Phương pháp nghiên cứu - Kết hợp thực tiễn giáo dục ở trường THPT Chuyên Hùng Vương và xu thế ra đề thi học sinh giỏi Quốc gia của Bộ giáo dục và đào tạo. - Có tham khảo các tài liệu bồi dưỡng học sinh giỏi trong và ngoài nước. - Tham khảo một số dạng đề thi học sinh giỏi Quốc gia của Bộ giáo dục và đào tạo dạng quy hoạch một số năm gần đây. B. NỘI DUNG I. Cơ sở lí luận - Các cách tiếp cận về tri thức mới, hiện đại của học sinh trong trường THPT Chuyên Hùng Vương là rất khó khăn vì thiếu tài liệu chuyên sâu về bồi dưỡng học sinh giỏi tin học tiếng Việt, nếu có thì cũng chưa thật đầy đủ, tổng quát, còn tài liệu tiếng Anh thì nhiều mà khả năng đọc hiểu của các em thì chưa thật sự tốt. Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 2 Phương pháp giải các bài toán - tin bằng quy hoạch động - Vì vậy tôi đã tham khảo tài liệu trong và ngoài nước để viết lên sáng đề tài về phương pháp quy hoạch động từ lý thuyết đến thuật toán và có một số bài toán cho các em vận dụng để thực hành trên máy tính. Từ đó các em có thể làm tốt các đề bài có dạng tương tự trong các kì thi chọn học sinh giỏi tin học. II. Nội dung và giải pháp thực hiện II.1 Nội Dung I. MỞ ĐẦU Tư tưởng quy hạch động được Bellman đề cập từ 1960 nhằm tìm nghiệm của bài toán tối ưu. Thời kỳ 1960-1970 là thời kỳ phát triển rực rỡ nhất của phương pháp này, nhờ nó nhiều bài toán với kích thước dữ liệu lớn hơn đã được giải với tốc độ chạy chương trình nhanh hơn so với những cách giải trước đây. Song đến năm 1970 đã xuất hiện một số bài toán mới mà cách giải bằng quy hoạch động tỏ ra hạn chế, chỉ tương đối có hiệu quả, thậm chí có bài hầu như không có hiệu qủa. Tuy nhiên với hàng loạt bài toán thông dụng phương pháp này vẫn là một trong các phương pháp tốt. 1. Phương pháp giải các bài toán - tin bằng quy hoạch động (QHĐ) Trong nhiều trường hợp, để giải một bài toán đã cho ta đưa về giải một số bài toán con rồi kết hợp nghiệm của các bài toán con để nhận được nghiệm của bài toán cần giải. Để giải được các bài toán con này ta lại đưa về giải các bài toán con nhỏ hơn. Quá trình trên sẽ tiếp tục cho tới khi nhận được các bài toán con có thể giải được dễ dàng, đó là kỹ thuật chia - để - trị, nó giải các bài toán con nhận được trong quá trình chia nhỏ một cách độc lập. Phương pháp quy hoạch động cũng có những điểm giống kỹ thuật chia để trị nhưng trong quá trình phân chia bài toán thành các bài toán con, các kết quả của mỗi bài toán con được lưu lại để xây dựng kết quả bài toán ban đầu và tránh giải nhiều lần cùng một bài toán con. Do đó phương pháp quy hoạch động thường giải bằng kỹ thuật dưới lên (bottom-up). Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 3 Phương pháp giải các bài toán - tin bằng quy hoạch động Ví dụ 1. Tính Cnk (với 0 <=k<=n). Dễ dàng tính Cnk dựa vào công thức truy hồi Cnk = Cn-1k + Cn-1k-1, với Cji = 1 nếu i=0 hoặc i=j. Hàm tính số tổ hợp chập k của n phần tử được viết theo kỹ thuật chia để trị như sau : Function ToHop(k, n : Integer) : Integer; Begin If (k=0) or (k=n) then ToHop:=1 Else ToHop:=ToHop(k,n-1)+ToHop(k-1,n-1); End; Với cách viết như trên thì có nhiều giá trị của tổ hợp được tính lại nhiều lần, chẳng hạn để tính ToHop(3,5) ta phải tính 2 lần ToHop(2,3); 3 lần ToHop(1,2),... Do đó thời gian tính toán sẽ rất lớn khi các giá trị đầu vào lớn. Để khắc phục hạn chế trên, ta dùng một mảng C[0..k,0..n] để lưu các kết quả đã tính, với mỗi i,j ta chỉ cần tính một lần Cji và lưu vào C[i,j]. Mảng C được xây dựng theo nguyên tắc từ dưới lên với những nhận xét sau: C[0,j]=1 với mọi 0<=j<=n C[i,i]=1 với mọi 0<=i<=k C[i,j]=C[i,j-1]+C[i-1,j-1] Dựa vào những nhận xét trên ta dễ dàng tính mảng C bằng đoạn chương trình sau: For j:=0 to n do C[0,j]:=1; For i:=1 to k do Begin C[i,i]:=1; For j:=i+1 to n do C[i,j]:=C[i,j-1]+C[i-1,j-1] End; 2. Các bước giải bài toán - tin bằng phương pháp QHĐ Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 4 Phương pháp giải các bài toán - tin bằng quy hoạch động Quy hoạch động là một phương pháp dựa vào kỹ thuật từ dưới lên. Để giải bài toán, chúng ta thường xuất phát từ những trường hợp riêng đơn giản nhất của bài toán (thường là thấy ngay nghiệm của chúng). Nghiệm của bài toán trong những trường hợp cụ thể được lưu lại rồi kết hợp theo từng bước để nhận được nghiệm của bài toán có cỡ “lớn hơn” và cuối cùng là nhận được nghiệm của bài toán đã cho. Do đó khi giải một bài toán con ta chỉ cần tìm những nghiệm của các bài toán con có cỡ nhỏ hơn mà kết quả đã được giải và lưu trong bảng kết quả mà không cần giải lại. Chính điều này làm cho các thuật toán quy hoạch động có hiệu quả cao. Để giải một bài toán bằng phương pháp QHĐ chúng ta phải tiến hành các bước cơ bản sau:  Tìm nghiệm các bài toán con (các trường hợp riêng) của bài toán.  Tìm công thức (hoặc quy tắc) xây dựng nghiệm của các bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ hơn (gọi là công thức truy hồi).  Tổ chức cấu trúc dữ liệu hợp lý (thường là dạng bảng) để lưu giữ nghiệm của các bài toán con. Sau đó tính nghiệm của các bài toán con theo công thức đã xây dựng ở bước trước và tiếp tục lưu vào bảng.  Từ bảng các nghiệm của các bà toán con đã được làm đầy, tìm cách xây dựng lời giải cho bài toán. Các bước trên được liệt kê theo thứ tự nhưng để hình thành các bước này cho một bài toán cụ thể ta phải tổng hợp tất cả các bước, trong đó nhiệm vụ xây dựng công thức truy hồi xác định nghiệm (hoặc một thành phần của nghiệm) mới hình thành được cách giải chính xác. Để minh họa, ta xét một số ví dụ sau : Ví dụ 2. Dãy con tăng dài nhất Cho N là một số nguyên dương (0= 2 thì F[i] được tính bằng công thức truy hồi sau: F[i]=Max{F[j]+1} với j=i-1,... 1 mà aj < ai. Ví dụ : i 1 2 3 4 5 6 7 8 9 10 11 12 A[i] 6 12 8 11 3 4 1 7 5 9 10 2 1 1 3 0 5 0 6 6 8 10 7 2 2 3 1 2 1 3 3 4 5 2 Truoc[i 0 ] F[i] 1 Để lấy tìm được dãy con không giảm cực đại (yêu cầu của bài toán) ta dùng một mảng Truoc[1..N] 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 F[i] đạt max. Ta lưu vị trí đó vào biến Luu. Như vậy: F[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: Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 6 Phương pháp giải các bài toán - tin bằng quy hoạch động dem:=0; i:=Luu; While i<>0 do Begin Inc(dem);P[dem]:=i; i:=Truoc[i]; End; Chỉ số theo thứ tự tăng dần của dãy con cực đại được in ra bằng dòng lệnh: For i:=dem downto 1 do Write(P[i],' '); Tuy nhiên làm như trên có vẻ dài dòng trong khi chúng ta đã nhận ra tính đệ quy trong việc lấy ngược lại. Và thủ tục in ra dãy con đã rất ngắn gọn và sáng sủa: Procedure Print(i:Integer); Begin If 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); Daycon.inp Daycon.out 15 7 1-->5-->5-->6-->7-->10-->11 2 1 5 5 6 7 13 10 11 4 6 9 8 10 7 Ta có toàn văn chương trình: uses crt; type mang=array[1..100]of integer; var f :text; a,b,c,truoc : mang; n,cs: integer; Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 7 Phương pháp giải các bài toán - tin bằng quy hoạch động procedure nhap; var i:byte; begin assign(f,'daycon.inp'); reset(f); readln(f, n); for i:=1 to n do read(f,a[i]); close(f); end; procedure taobang; var i,j,bMax,chiso : byte; begin b[1]:=1; truoc[1]:=0; for i:= 2 to n do begin bmax:= 0; chiso:=0; for j:= i-1 downto 1 do if (a[j] <= a[i]) and (b[j] > bmax) then begin bmax:= b[j]; chiso:= j; end; b[i] := bmax +1; truoc[i] := chiso; end; Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 8 Phương pháp giải các bài toán - tin bằng quy hoạch động end; (* In ket qua bang de quy *) procedure xuat(i:integer); begin if truoc[i]=0 then write(f,a[i]) else begin xuat(truoc[i]); write(f,'-->',a[i]); end; end; procedure truyvet; var max,i : byte; begin max:= b[1];cs:=1; for i:= 2 to n do if max < b[i] then begin max:= b[i]; cs:=i; end; assign(f,'daycon.out'); rewrite(f); writeln(f,max); Xuat(cs); Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 9 Phương pháp giải các bài toán - tin bằng quy hoạch động (*while truoc[cs]<>0 do begin write(a[cs]:3); write(F,a[cs]:3); cs:=truoc[cs]; end; write(a[cs]:3); write(F,a[cs]:3); *) close(f); end; begin nhap; taobang; truyvet; end. 3) Sơ đồ giải bài toán QHĐ: B1. Lập hệ thức: Lập hệ thức biểu diễn tương quan quyết định của bước đang xử lý với các bước đã xử lý trước đó. Hệ thức này thường là các biểu thức đệ quy do đó dễ gây ra hiện tượng tràn miền nhớ khi ta tổ chức chương trình trực tiếp bằng đệ quy. B2. Tổ chức dữ liệu và chương trình: Tổ chức dữ liệu tính toán dần theo từng bước. Nên tìm cách khử đệ quy. Thông thường, trong các bài toán chúng ta hay gặp đòi hỏi một vài mảng hai chiều. B3. Truy vết: tìm kết quả của bài toán tử bảng một chiều hoặc hai chiều đã xây dựng. Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 10 Phương pháp giải các bài toán - tin bằng quy hoạch động Dưới đây là các ví dụ minh họa. Ví dụ 3: Bài toán Ba lô 1 Cho ba lô 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 ba lô sao cho đạt giá trị lớn nhất. balo1.inp 4 13 2 4 5 7 3 5 4 6 balo1.out 25 1 1 3 0 B1. Lập hệ thức: Gọi f(k,v) là giá trị lớn nhất của ba lô đự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 k vat *) if (F[i,j]< F[i-1,j-a[i]*k]+C[i]*k) then (* Neu chon vat i vat so luong k ma gia tri lon hon chap nhan gia tri moi *) Begin F[i,j]:=F[i-1,j-a[i]*k]+C[i]*k; (* ghi nhan gia trij F[i,j] *) luu[i,j]:=k; (* Ghi nhan vat i da chon voi so luong la k *) End; end; end; (***************************) { procedure In_ra; Var i:integer; begin Assign(f1,'balo_1.out'); rewrite(f1); Writeln(f1,F[n,w]); i:=n; (* viet ra so luong cac vat theo thu tu nguoc Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 13 Phương pháp giải các bài toán - tin bằng quy hoạch động n <- n-1 <- .. <- 1 khong dep lam *) While (i>0) do begin if i>1 then write(f1,luu[i,w],'<--') else write(f1,luu[i,w]); w:=w-a[i]*luu[i,w]; i:=i-1; end; close(f1); } procedure Find_path(i,j:integer); (* In bang de quy dung thu tu *) begin if (i>0) then begin find_path(i-1,j-a[i]*luu[i,j]); if i<>n then write(f1,luu[i,j],'-->') else write(f1,luu[i,j]); end; end; procedure In_ra; begin Assign(f1,'balo_1.out'); rewrite(f1); Writeln(f1,F[n,w]); Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 14 Phương pháp giải các bài toán - tin bằng quy hoạch động find_path(n,w); close(f1); end; begin input; Qh_dong; In_ra; end. Ví dụ 4: Bài toán ba lô 2: Cho ba lô 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 ba lô sao cho đạt giá trị lớn nhất. (số lượng 1 vật có thể chọn 1 hoặc không chọn) balo2.inp nw a[1] c[1] a[2] c[2] ... a[n] c[n] balo2.out S: Giá trị lớn nhất của các vật đó chọn num[1] num[2] ... num[n] : số lượng các vật được chọn Ví dụ: balo2.inp 4 11 34 56 65 13 Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 15 Phương pháp giải các bài toán - tin bằng quy hoạch động balo2.out 13 1101 B1. Lập hệ thức: Gọi F(i,j) là giá trị lớn nhất của ba lô đựng trọng lượng j và chỉ chứa các đồ vật từ 1 đến i. Đặt: F[i,j]=max(F[i-1,j], F[i-1,j-a[i]]+C[i]) (*) ,với i=1,2,...,n, j=1=1,2..,w B2. Tổ chức dữ liệu và chương trình: 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 luu[i,j] chứa giá trị F(i,j) và giá trị x thoả mãn công thức (*). B3. Truy vết: Để 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 luu[n-1,w-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: Toàn bộ chương trình: program Ba_lo_2; const MaxN=50; MaxW=255; var F,luu:array[0..MaxN,0..MaxW] of Word; A,C:array[1..MaxN] of 0..255; n,W:integer;f1:text; procedure input; var i,j:integer; begin assign(f1,'Balo_2.inp'); Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 16 Phương pháp giải các bài toán - tin bằng quy hoạch động reset(f1); readln(f1,n,W); For i:=1 to n do readln(f1,a[i],c[i]); close(f1); end; procedure QH_dong; Var i,j:integer; begin For j:=1 to W do Begin F[0,j]:=0; Luu[0,j]:=0; end; For i:=1 to n do (* duyet het cac vat tu 1 den n *) For j:=1 to W do (* duyet het kich co tui tu 1 den w *) Begin if j>=a[i] then (* neu co tui lon hon vat i *) if (F[i-1,j]< F[i-1,j-a[i]]+C[i]) then (* neu chon vat i co gia tri lon hon khong chon no thi chap nhan *) Begin F[i,j]:=F[i-1,j-a[i]]+C[i]; (*ghi nhan gia tri F[i,j] *) luu[i,j]:=1; (* ghi nhan vat i co chon *) End else begin F[i,j]:=f[i-1,j];luu[i,j]:=0; (* ghi nhan vat i khong chon *) Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 17 Phương pháp giải các bài toán - tin bằng quy hoạch động end; end; end; (***************************) { procedure In_ra; (* nguoc thu tu n0) do begin write(f1,luu[i,w],' '); w:=w-a[i]*luu[i,w]; i:=i-1; end; close(f1); end; } procedure Find_path(i,j:integer); (* In bang de quy dung thu tu *) begin if (i>0) then begin find_path(i-1,j-a[i]*luu[i,j]); if i<>n then Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 18 Phương pháp giải các bài toán - tin bằng quy hoạch động write(f1,luu[i,j],'-->') else write(f1,luu[i,j]); end; end; procedure In_ra; begin Assign(f1,'balo_2.out'); rewrite(f1); Writeln(f1,F[n,w]); find_path(n,w); close(f1); end; begin input; Qh_dong; In_ra; end. 3) BÀI TẬP ÁP DỤNG Bài 1. Đổi tiền Có n loại tiền có trị giá A1, A2, ..., An. Hãy dùng các loại tiền này đổi số tiền L sao cho tổng số tờ tiền là ít nhất. Hướng dẫn : Công thức truy toán: Gọi F(L) là số tờ tiền ít nhất cần dùng để đổi được số tiền L. Ta có nhận xét : Lê Văn Trường-Gv Trường THPT Chuyên Hùng Vương Gia Lai 19
- Xem thêm -

Tài liệu liên quan