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<br /> GIẢI MỘT LỚP “CÁC BÀI TOÁN TỐI ƯU ”<br /> <br /> L NG C HƯNG(*)<br /> <br /> TÓM TẮT<br /> <br /> 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<br /> ư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ứ<br /> 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ả<br /> 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<br /> 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 .<br /> 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ể<br /> 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ỡ<br /> 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<br /> 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<br /> 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<br /> mà thuật toán “ Quy hoạch động “ là rất có hiệu quả .<br /> <br /> ABSTRACT<br /> <br /> Dynamic programming is the method of solving complex problems for optimal solutions.<br /> The ideas behind Dynamic programming are very simple:<br /> In order to avoid recalculating everything, we store the solutions to the subproblems in a table<br /> which is used as a fundamental theory to solve new problems. We will build up the values of the<br /> table by adding the solved results of the previous problems. Therefore, the solution to a given<br /> optimal problem can be obtained by the combination of optimal solutions to its subproblems. In<br /> another word, Dynamic programming holds the strengths of the “divide and rule” principle to high<br /> esteem.<br /> Dynamic programming applies the Bottom-up approach. On solving the simpler problems, we can<br /> use the solutions to build on and arrive at solutions to bigger problems. Hence, we can formulate a<br /> complex calculation as a recursive series of simpler calculations. In this approach, we can refer to a<br /> tabular form of the results of the solved subproblems. When we have to find out the solutions to the<br /> simpler subproblems ,we just look them up in the table. That is why Dynamic programming<br /> algorithm is very efficient.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> <br /> 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<br /> 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<br /> giá trị lớn nhất”.<br /> <br /> Ta có thể giải thích ý này qua bài toán sau:<br /> <br /> <br /> <br /> <br /> (*)<br /> Th.S, Khoa Công nghệ thông tin, Trường Đại học Sài Gòn<br /> 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<br /> 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ố<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> “Phương pháp quy hoạch động” thể hiện sức mạnh của nguyên lý “Chia để trị đến cao độ”.<br /> <br /> 2. PHƯƠNG PHÁP<br /> <br /> 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<br /> đơ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<br /> 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á<br /> 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<br /> 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<br /> 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<br /> vì vậy mà thuật toán “Quy hoạch động” là rất có hiệu quả.<br /> <br /> 2.1. Ưu điểm của phương pháp quy hoạch động<br /> <br /> - Chương trình chạy nhanh hơn.<br /> <br /> 2.2. Phạm vi hoạt động của phương pháp quy hoạch động<br /> <br /> - Tìm nghiệm các bài toán tối ưu.<br /> - Các bài toán có công thức truy hồi.<br /> <br /> 2.3. Hạn chế của phương pháp quy hoạch động<br /> <br /> Phương pháp quy hoạch động không đem lại hiệu quả trong các trường hợp sau:<br /> <br /> - Không tìm được công thức truy hồi.<br /> - 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ự<br /> 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<br /> 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ả<br /> của bài toán lớn hơn.<br /> - 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<br /> lớn đến hàng trăm.<br /> - Có những bài toán không thể giải được bằng quy hoạch động.<br /> 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<br /> độ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<br /> cấu hình tối ưu thì mọi cấu hình con của nó cũng tối ưu”.<br /> <br /> 3. CẤU TRÚC CHUNG CỦA CHƯƠNG TRÌNH CHÍNH<br /> <br /> BEGIN {Chương trình chính}<br /> <br /> Chuẩn bị đọc dữ liệu và khởi gán một số giá trị.<br /> Tạo bảng.<br /> Tra bảng và ghi kết quả<br /> <br /> END.<br /> <br /> 4. SƠ ĐỒ THUẬT TOÁN CỦA QUY HOẠCH ĐỘNG<br /> <br /> 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<br /> <br /> 4.2. Lập hệ thức<br /> <br /> 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 đó.<br /> 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 đệ<br /> 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).<br /> <br /> Một cách xây dựng phương trình truy toán:<br /> <br /> 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<br /> độ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).<br /> 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<br /> 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ó<br /> 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),<br /> 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<br /> 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<br /> 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<br /> toán tính riêng ở giai đoạn k là Gk. Thì:<br /> <br /> Fk=Fk-1 + Gk<br /> Hay là :<br /> Fk(t(k))=Max{ Gk(t(k),d(k))+Fk-1(t(k-1))} (*)<br />  d(k)<br /> <br /> 4.3. Tổ chức dữ liệu và chương trình<br /> <br /> - 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<br /> 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.<br /> - 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<br /> 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.<br /> - Các giá trị Fk thường lưu trữ trong bảng một chiều, hai chiều, ba chiều.<br /> - 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<br /> nhỏ nhất đang giải (trường hợp đơn giản nhất).<br /> F1(t(1)) = Max{ G1(t(1),d(1))+F0(t(0))}<br />  d(1)<br /> - 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<br /> bảng.<br /> - 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.<br /> - 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<br /> toán theo yêu cầu.<br /> <br /> 4.4. Làm tốt<br /> <br /> 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ớ.<br /> 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)<br /> của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước.<br /> <br /> 5. MỘT VÀI BÀI TOÁN ÁP DỤNG<br /> <br /> B C M HO<br /> <br /> 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<br /> 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<br /> 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<br /> hoa sao cho giá trị thẩm mĩ là cao nhất.<br /> <br /> Dữ l ệu v : Cho trong tập tin văn bản có tên HOA.INP có cấu trúc :<br /> <br /> - Dòng đầu tiên là hai giá trị K và N<br /> - 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.<br /> <br /> Dữ l ệu ra : Ghi vào File văn bản có tên HOA.OUT gồm hai dòng:<br /> <br /> - Dòng đầu tiên là tổng giá trị thẩm mĩ của phương án cắm hoa tối ưu.<br /> - Từ dòng thứ hai là hai dãy K số hiệu lọ được chọn cho mỗi bó hoa<br /> <br /> Thí dụ:<br /> <br /> HOA.INP HOA.OUT<br /> 4 6 24<br /> 1 1 6 4 3 10 1 3 4 6<br /> 9 1 4 7 2 7<br /> 7 2 6 10 2 3<br /> 6 10 7 1 3 9<br /> <br /> <br /> Hướng giải:<br /> Ta dùng phương pháp quy hoạch động để giải bài toán này:<br /> <br /> Ta tiến hành như sau:<br /> <br /> 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:<br /> <br /> 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 .<br /> <br /> 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ọ đó.<br /> <br /> 5.1.3. Ta xét trường hợp số bó hoa ít hơn số lọ (ib[i][j-1] thì ta phải thực hiện hai thao tác sau :<br /> <br /> + Đặ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<br /> 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 :<br /> - Đặt L[i][j]=L[i-1][j-1] và đánh dấu phần tử thứ j trong mảng L[i][j]<br /> <br /> + Nếu b[i-1][j-1]+V[i][j]b[i] cũ thì phải thực hiện hai thao tác :<br /> <br /> - Đặt L[i]=L[i-1] cũ và đánh dấu phần tử thứ j trong mảng L[i].<br /> <br /> + 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<br /> 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à<br /> tính dần theo chiều giảm của i=j..1.<br /> <br /> Để đá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<br /> 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ọ<br /> thư j có được chọn hay không ta gọi hàm Getbit.<br /> <br /> Mô ả bằ g gô gữ C hư sau<br /> <br /> #include<br /> #include<br /> #define max 100<br /> #define fi "CAMHOA.INP"<br /> #define fo "CAMHOA.OUT"<br /> int k,n,v[max][max],b[max][max],kq,vt[max];<br /> //------------------------------------------------------------------------------------------------<br /> // b[i][j] là giá trị thẩm mỹ khi cắm i bó hoa vào j lọ<br /> //--------------------------------------------------------------------------------------------------<br /> <br /> void doc(){<br /> FILE *f =fopen(fi,"rt");<br /> fscanf(f,"%d%d",&k,&n);<br /> inti=0,j=0;<br /> for(i=1;i