Phương pháp quy hoạch động trong việc giải một lớp “Các bài toán tối ưu ”

PHƯƠNG PHÁP QUY HOẠCH ĐỘNG TRONG VIỆC GIẢI MỘT LỚP “CÁC BÀI TOÁN TỐI ƯU ” L NG C HƯNG(*) TÓM TẮT Phương pháp quy hoạch động là một kĩ thuật được áp dụng để giải các bài toán tìm phương án tối ưu . Vậy ý tưởng của phương pháp quy hoạch động thật đơn giản : Để tránh việc tính lại mọi thứ hai lần , ta lưu giữ kết quả đã tìm được vào một mảng làm giả thiết cho việc tìm kiếm những kết quả cho trường hợp sau . Chúng ta sẽ làm đầy dần giá trị của bảng này . Bởi các kết quả của những trường hợp trước đã được giải quyết . Kết quả cuối cùng cũng chính là kết quả cần giải . Quy hoạch động là dùng kĩ thuật đi từ dưới lên . Xuất phát từ trường hợp đơn giản nhất , có thể tìm ngay ra nghiệm bằng cách kết hợp nghiệm của chúng , ta nhận được nghiệm của bài toán cỡ lớn hơn . Cứ như thế ta nhận được đủ nghiệm của bài toán cần tìm .Trong quá trình đi “ Từ dưới lên “ chúng ta sẽ sử dụng một bảng lưu giữ lời giải của các bài toán con đã được giải. Khi giải một bài toán cần đến nghiệm của những bài toán nhỏ hơn ta chỉ việc tìm kiếm trong bảng . Chính vì vậy mà thuật toán “ Quy hoạch động “ là rất có hiệu quả . ABSTRACT Dynamic programming is the method of solving complex problems for optimal solutions. The ideas behind Dynamic programming are very simple: In order to avoid recalculating everything, we store the solutions to the subproblems in a table which is used as a fundamental theory to solve new problems. We will build up the values of the table by adding the solved results of the previous problems. Therefore, the solution to a given optimal problem can be obtained by the combination of optimal solutions to its subproblems. In another word, Dynamic programming holds the strengths of the “divide and rule” principle to high esteem. Dynamic programming applies the Bottom-up approach. On solving the simpler problems, we can use the solutions to build on and arrive at solutions to bigger problems. Hence, we can formulate a complex calculation as a recursive series of simpler calculations. In this approach, we can refer to a tabular form of the results of the solved subproblems. When we have to find out the solutions to the simpler subproblems ,we just look them up in the table. That is why Dynamic programming algorithm is very efficient. 1. ĐẶT VẤN ĐỀ Phương pháp quy hoạch động (dynamic programming) là một kĩ thuật được áp dụng để giải lớp các bài toán , đặc biệt là các bài toán tìm phương án tối ưu như là: “các bài toán tìm giá trị nhỏ nhất hoặc giá trị lớn nhất”. Ta có thể giải thích ý này qua bài toán sau: (*) Th.S, Khoa Công nghệ thông tin, Trường Đại học Sài Gòn Cho một dãy N số nguyên A1, A2,,An . Hãy tìm cách xóa đi một một số ít số hạng để dãy còn lại là đơn điệu hay nói cách khác: Hãy chọn một số nhiều nhất các số hạng sao cho dãy B gồm các số hạng đó theo thứ tự xuất hiện trong dãy A [1..n] là đơn điệu. Quá trình chọn dãy B được điều khiển qua n giai đoạn để đạt được mục tiêu là số hạng số của dãy B là nhiều nhất. Điều khiển ở giai đoạn i thể hiện việc chọn hay không chọn Ai vào dãy B. Giả sử ta có dãy: 1 8 10 2 4 6 7. Nếu ta chọn 1 8 10 thì ta chỉ có chọn được 3 số hạng nhưng nếu bỏ qua 8 10 thì ta chọn được 5 số hạng: 1 2 4 6 7. Khi giải các bài toán bằng cách “Chia để trị”, chuyển việc giải bài toán kích thước lớn về việc giải nhiều bài toán cùng kiểu có kích thước nhỏ hơn thì thuật toán này thường được thể hiện bằng các chương trình con đệ quy, khi đó trên thực tế, nhiều kết quả trung gian phải được tính lại nhiều lần. Vậy ý tưởng của phương pháp quy hoạch động thật đơn giản: để tránh việc tính lại mọi thứ hai lần, ta lưu giữ kết quả đã tìm được vào một mảng làm giả thiết cho việc tìm kiếm những kết quả cho trường hợp sau. Chúng ta sẽ làm đầy dần giá trị của bảng này. Bởi các kết quả của những trường hợp trước đã được giải quyết. Kết quả cuối cùng cũng chính là kết quả cần giải. Nói cách khác “Phương pháp quy hoạch động” thể hiện sức mạnh của nguyên lý “Chia để trị đến cao độ”. 2. PHƯƠNG PHÁP Phương pháp quy hoạch động là dùng kĩ thuật đi từ dưới lên (bottom up). Xuất phát từ trường hợp đơn giản nhất, có thể tìm ngay ra nghiệm bằng cách kết hợp nghiệm của chúng, ta nhận được nghiệm của bài toán c lớn hơn. Cứ như thế ta nhận được đủ nghiệm của bài toán cần tìm.Trong quá trình đi “từ dưới lên”, chúng ta sẽ sử dụng một bảng lưu giữ lời giải của các bài toán con đã được giải mà không cần quan tâm nó được sử dụng ở đâu sau này. Khi giải một bài toán ta cần đến nghiệm của những bài toán nhỏ hơn ta chỉ việc tìm kiếm trong bảng không cần phải giải lại. Chính vì vậy mà thuật toán “Quy hoạch động” là rất có hiệu quả. 2.1. Ưu điểm của phương pháp quy hoạch động - Chương trình chạy nhanh hơn. 2.2. Phạm vi hoạt động của phương pháp quy hoạch động - Tìm nghiệm các bài toán tối ưu. - Các bài toán có công thức truy hồi. 2.3. Hạn chế của phương pháp quy hoạch động Phương pháp quy hoạch động không đem lại hiệu quả trong các trường hợp sau: - Không tìm được công thức truy hồi. - Việc tìm công thức, phương trình truy toán hoặc tìm cách phân rã bài toán nhiều khi đòi hỏi sự phân tích tổng hợp rất công phu, dễ sai sót, khó nhận ra thế nào là thích hợp, đòi hỏi thời gian suy nghĩ. Đồng thời không phải lúc nào cũng kết hợp việc giải của các bài toán con cũng cho kết quả của bài toán lớn hơn. - Khi bảng lưu trữ đòi hỏi mảng hai chiều , ba chiều thì có thể xử lí dữ liệu với kích c mỗi chiều lớn đến hàng trăm. - Có những bài toán không thể giải được bằng quy hoạch động. Như vậy, ta có thể tóm lược nguyên lí quy hoạch động do Bellman phát biểu như sau: “Quy hoạch động là lớp các bài toán mà quyết định ở bước thứ i phụ thuộc vào các bước (i-1) trước đó” và “Một cấu hình tối ưu thì mọi cấu hình con của nó cũng tối ưu”. 3. CẤU TRÚC CHUNG CỦA CHƯƠNG TRÌNH CHÍNH BEGIN {Chương trình chính} Chuẩn bị đọc dữ liệu và khởi gán một số giá trị. Tạo bảng. Tra bảng và ghi kết quả END. 4. SƠ ĐỒ THUẬT TOÁN CỦA QUY HOẠCH ĐỘNG 4.1.Tính nghiệm tối ưu của bài toán trong trường hợp đơn giản nhất 4.2. Lập hệ thức Lập hệ thức biểu thị sự 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 là hàm đệ quy do đó sẽ gây ra tràn miền nhớ khi tổ chức thực hiện trực tiếp bằng đệ quy. Ta còn gọi hệ thức này là phương trình đệ quy (hay phương trình truy toán). Một cách xây dựng phương trình truy toán: Ta chia việc giải bài toán thành n giai đoạn. Mỗi giai đoạn i có trạng thái ban đầu t(i) và chịu tác động điều khiển d(i) sẽ biến thành trạng thái tiếp theo t(i+1) của giai đoạn thứ (i+1) ( i= 1,2,3,,n). Theo nguyên lý Bellman thì việc tối ưu giai đoạn cuối cùng không làm ảnh hưởng kết quả của bài toán .bằng cách đi từ dưới lên, với trạng thái ban đầu là t(n) sau khi làm giai đoạn n tốt nhất, ta có trạng thái tiếp theo cho giai đoạn (n-1) là t(n-1) và tác động điều khiển của giai đoạn (n-1) là d(n-1), có thể tiếp tục xét đến giai đoạn (n-1). Sau khi tối ưu giai đoạn (n-1) ta lại có t(n-2) và d(n-2) và lại có thể tối ưu giai đoạn (n-2) , Cho đến khi các giai đoạn từ n đến 1 được tối ưu thì coi như hoàn thành bài toán. Gọi giá trị tối ưu của bài toán tính đến giai đoạn thứ k là Fk, giá trị tối ưu của bài toán tính riêng ở giai đoạn k là Gk. Thì: Fk=Fk-1 + Gk Hay là : Fk(t(k))=Max{ Gk(t(k),d(k))+Fk-1(t(k-1))} (*)  d(k) 4.3. 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 mảng một chiều, hai chiều, ba chiều. - Tạo ra một bảng để lưu giữ các nghiệm của bài toán con. Sau đó tính nghiệm của bài toán lớn hơn theo công thức (Hàm đệ quy) và lưu trữ vào bảng cho đến khi tìm được nghiệm của bài toán. - Các giá trị Fk thường lưu trữ trong bảng một chiều, hai chiều, ba chiều. - Cần lưu ý các giá trị khởi tạo ban đầu của bảng cho thích hợp, đó là kết quả của bài toán con nhỏ nhất đang giải (trường hợp đơn giản nhất). F1(t(1)) = Max{ G1(t(1),d(1))+F0(t(0))}  d(1) - Dựa vào phương trình truy toán (*) và các giá trị trong bảng để tìm dần các giá trị còn lại của bảng. - Ngoài ra còn cần mảng lưu trữ nghiệm tương ứng với giá trị tối ưu trong từng giai đoạn. - Dựa vào bảng lưu trữ nghiệm và bảng giá trị tối ưu trong từng giai đã xây dựng, tìm kết quả bài toán theo yêu cầu. 4.4. Làm tốt Làm tốt thuật toán bằng cách thu gọn hệ thức quy hoạch động và giảm thiểu kích thước bộ nhớ. Thường tìm cách dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng ( hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước. 5. MỘT VÀI BÀI TOÁN ÁP DỤNG B C M HO Cần cắm K bó hoa khác nhau vào N lọ xếp thẳng hàng sao cho hoa có số hiệu nhỏ được đặt trước hoa có số hiệu lớn. Với mỗi loại hoa i biết giá trị thẩm mĩ khi cắm hoa đó vào lọ j là V[i][j]. Các số liệu đều là số tự nhiên và được ghi cách nhau bởi dấu cách trên mỗi dòng .Tìm phương án cắm hoa sao cho giá trị thẩm mĩ là cao nhất. Dữ l ệu v : Cho trong tập tin văn bản có tên HOA.INP có cấu trúc : - Dòng đầu tiên là hai giá trị K và N - Từ dòng thứ hai trở đi là các giá trị V[i][j] vớii :1..K,j :1..N ; 1KN100. Dữ l ệu ra : Ghi vào File văn bản có tên HOA.OUT gồm hai dòng: - Dòng đầu tiên là tổng giá trị thẩm mĩ của phương án cắm hoa tối ưu. - Từ dòng thứ hai là hai dãy K số hiệu lọ được chọn cho mỗi bó hoa Thí dụ: HOA.INP HOA.OUT 4 6 1 1 6 4 3 10 9 1 4 7 2 7 7 2 6 10 2 3 6 10 7 1 3 9 24 1 3 4 6 Hướng giải: Ta dùng phương pháp quy hoạch động để giải bài toán này: Ta tiến hành như sau: 5.1. Lập hệ thức: Gọi b[i][j] là giá trị thẫm mĩ khi cắm i bó hoa vào j lọ, ta thấy: 5.1.1. Nếu số bó hoa nhiểu hơn số lọ (i>j) thì không có cách cắm nào . 5.1.2. Nếu số bó hoa bằng số lọ thì chỉ có một cách duy nhất là bó nào vào lọ đó. 5.1.3. Ta xét trường hợp số bó hoa ít hơn số lọ (i<j). Có hai tình huống xẩy ra: + Lọ cuối cùng, tức lọ thứ j được chọn cho phương án tối ưu. + Lọ thứ j không được chọn làm phương án tối ưu . Nếu lọ thư j được chọn tức là trong lọ thứ j ta sẽ cắm bó hoa cuối cùng ,bó thư i .Số (i-1) bó hoa đầu tiên sẽ được phân phối (j-1) lọ đầu tiên, giá trị thẩm mĩ khi đó sẽ là : b[i-1][j-1]+ V[i][j]. Nếu lọ thư j không được chọn cho phương án tối ưu thì i bó hoa phải được cắm vào (j-1) lọ đầu tiên và do đó Giá trị thẩm mỹ khi đó sẽ là : b[i][j-1] Tổ g hợp lạ a có g rị ố ưu kh cắm bó h a v j lọ sẽ l b[i][j] =Maxb[i -1][j -1]+V[i][j],b[i][j -1]. 5.2. Tổ chức dữ liệu và chương trình: Nếu dùng mảng hai chiều b thì ta có thể tính như trong bảng dưới đây : Coät j -1 Coät j Doøng i-1 [i -1][j -1] Doøng i [i][j -1] [i][j] Ngoài ra ta còn cần đặt trong mỗi Ô của bảng trên một mảng dữ liệu bao gồm n phần tử để đánh dấu lọ hoa nào được chọn cho mỗi tình huống. Gọi mảng dữ liệu đó là: L[i][j] . Ta thấy nên điền bảng lần lượt theo từng cột, tại mỗi cột ta điền bảng từ trên xuống hoặc từ dưới lên theo luật sau: + Nếu b[i-1][j-1]+V[i][j]>b[i][j-1] thì ta phải thực hiện hai thao tác sau : + Đặt trị : b[i][j]=b[i-1][j-1]+V[i][j] và ghi nhận việc chọn lọ hoa j trong phương án mới , cụ thể lấy phương án cắm hoa [i-1][j-1] rồi bổ sung thêm việc chọn lọ hoa j như sau : - Đặt L[i][j]=L[i-1][j-1] và đánh dấu phần tử thứ j trong mảng L[i][j] + Nếu b[i-1][j-1]+V[i][j]<=b[i][j-1] thì ta chỉ cần Copy L[i][j-1]sang L[i][j] vì ta bảo lưu phương án [i][j-1] 5.3. Làm tốt: Phương án dùng mảng hai chiều tốn kém bộ nhớ . Ta có thể dùng mảng một chiều T[100] xem như một cột của bảng T nói trên . Ta duyệt j bước , tại bước j , giá trị b[i] sẽ là giá trị tối ưu khi cắm i bó hoa vào j lọ .Như vậy tại bước thứ j ta có : + Nếu b[ -1] cũ +V[i][j]>b[i] cũ thì phải thực hiện hai thao tác : - Đặt L[i]=L[i-1] cũ và đánh dấu phần tử thứ j trong mảng L[i]. + Nếu b[ -1] cũ +V[i][j]  b[i] cũ thì ta không phải làm gì vì sẽ bảo lưu phương án cũ .Biểu thức so sánh cho biết khi cập nhật mảng T từ bước thứ j-1 qua bước thứ j ta phải tính từ dưới lên ,nghĩa là tính dần theo chiều giảm của i=j..1. Để đánh dấu các lọ hoa ta dùng mảng L[MN] mỗi phần tử là một dãy 15 bit thì ta có thể đánh dấu cho 15*8=120 lọ hoa. Khi cần đánh dấu lọ hoa thư j trong dãy L[i] ta bật bit thư j. Khi cần xem lọ thư j có được chọn hay không ta gọi hàm Getbit. Mô ả bằ g gô gữ C hư sau #include #include #define max 100 #define fi "CAMHOA.INP" #define fo "CAMHOA.OUT" int k,n,v[max][max],b[max][max],kq,vt[max]; //------------------------------------------------------------------------------------------------ // b[i][j] là giá trị thẩm mỹ khi cắm i bó hoa vào j lọ //-------------------------------------------------------------------------------------------------- void doc(){ FILE *f =fopen(fi,"rt"); fscanf(f,"%d%d",&k,&n); inti=0,j=0; for(i=1;i<=k;i++) for(j=1;j<=n;j++) fscanf(f,"%d",&v[i][j]); fclose(f); } int getmax(int i,int j) { if(i>j) return i; return j; } /------------------------------------------ void taobang(){ for(int i=1;i<=k;i++) for(int j=i;j<=n-(k-i);j++) b[i][j] = getmax( b[i][j-1] , (b[i1][j1] ) //----------------------------------------- void trabang(){ int i=k;j=n; kq=b[i][j]; do { while(b[i][j]==b[i][j-1]) j--; vt[i]=j; i--;j--;} while (i>-1); } //--------------------------------- void xuat(){ FILE *f=fopen(fo,"wt"); if(kq==-1) fprintf(f,"1"); else { trabang(); fprintf(f,"%d\n",kq); for(inti=1;i<=k;i++) fprintf(f,"%5d",vt[i]); } fclose(f); } //--------------------------------- void main(){ doc(); if(n>=k) taobang() ; else kq=-1; xuat();} Bài toán ba lô 2: Đề b : Cho N món hàng (N50). Món thứ i có khối lượng A[i] và có giá trị là B[i] (số nguyên). cần chọn những món hàng nào để bỏ vào ba lô sao cho tổng giá trị của các món hàng đã chọn là lớn nhất nhưng tổng khối lượng không vượt quá khối lượng W của ba lô cho trước (W 100). Mỗi món chỉ chọn được một hoặc không chọn. Dữ l ệu v : Cho trong File BALO2.INP có cấu trúc như sau: - Dòng đầu ghi hai số nguyên N và W - N dòng tiếp theo, dòng thứ i ghi hai số A[i] và B[i] chỉ rõ khối lượng và giá trị của món hàng thứ I, các số trên một dòng cách nhau ít nhất một dấu cách. Dữ l ệu ra Ghi vào File BALO2.OUT có cấu trúc như sau: - Dòng đầu ghi giá trị lớn nhất của bao lô cần đạt. - Dòng thứ hai số hiệu cùng với khối lượng và giá trị của các món hàng được chọn, các số cách nhau ít nhất một dấu cách. Hướng giải: Gọi Fx[k,v] là giá trị lớn nhất của ba lô khi k món hàng đầu tiên được chọn và khối lượng của ba lô là v. Ta có chương trình cho hàm đệ quy như sau: If v>=A[k] then Fx[k][v]= Max(Fx[k-1][v-A[k]]+B[k],Fx[k-1][v]) Else Fx[k][v]= Fx[k-1][v]. Dưới đây là bảng tính hàm đệ quy Fx[k,v] của ví dụ trên. v k 1 2 3 4 5 6 7 8 9 10 11 12 13 1 0 0 4 4 4 4 4 4 4 4 4 4 4 2 0 0 4 5 5 5 9 9 9 9 9 9 9 3 0 0 4 5 6 6 9 10 11 11 11 15 15 4 0 3 4 5 7 8 9 10 12 13 14 15 15 5 1 3 4 5 7 8 9 10 12 13 14 15 16 Ta có chương trình sau: #include #include #define max 100 #define fi "BALO2.INP" #define fo "BALO2.OUT" int k,n,a[max],gt[max],b[max][max],vt[max],w,kq; void doc() { Ví dụ BALO2.INP BALO2.OUT 4 13 3 4 4 5 5 6 2 3 1 1 16 1(3,4) 2(4,5) 3(5,6) 5(1,1) FILE *f=fopen(fi,"rt"); fscanf(f,"%d%d",&n,&w); for(int i=1;i<=n;i++) fscanf(f,"%d%d",&a[i],>[i]);fclose(f); } int getmax(int i,int j){ if(i>j)return i; return j; } void taobang(){ int i,j; for(j=1;jj) b[1][j]=0; else b[1][j]=gt[1]; for(i=2;i<=n;i++) for(j=1;j=a[i]) b[i][j] =getmax(b[i-1][j],(b[i-1][j-a[i]]+gt[i]) ); else b[i][j]=b[i-1][j]; } void trabang(){ int d=n,c=w,tam; kq=tam=b[d][c]; do{ while(b[d][c]==b[d-1][c]) d--; while(b[d][c]==b[d][c-1]) c--; vt[d]=1;c-=a[d]; }while(c>0); } void xuat(){ FILE *f=fopen(fo,"wt"); trabang(); fprintf(f,"%d",kq); for(int i=1;i<=n;i++) if(vt[i]) fprintf(f,"\n %3d (%d,%d)",i,a[i],gt[i]); fclose(f); } void main(){ doc(); taobang(); xuat(); Bài báo nêu lên phương pháp quy hoạch động chung và một vài áp dụng để giải các bài toán tối ưu, một phương pháp được sử dụng nhiều trong dạy chuyên tin học. Trong khuôn khổ của tạp chí người viết chỉ mới giới thiệu một phần nhỏ của việc áp dụng này. TÀI LIỆU THAM KHẢO 1. Niclaus Wirth (1981), Bản dịch Algorithms+Data structure, NXB Thống Kê. 2. Đỗ Xuân Lôi (1996), Cấu Trúc dữ liệu và giải thuật, NXB Khoa học Kỹ Thuật. 3. Hoàng Kiếm (Chủ biên)( 1996), Giáo trình cấu trúc dữ liệu, ĐH Khoa Học Tự Nhiên. 4. Nguyễn Quốc Cường và Hoàng Đức Hải(1995), Cấu trúc dữ liệu + Giải Thuật = Chương Trình, NXB Giáo Dục. 5. Tin học và nhà trường 6 năm (1999-2005)