//
you're reading...
01 - Chủ đề thuật toán, Chủ đề quy hoạch động, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi, Giáo trình chuyên Tin học 10

Bài giảng quy hoạch động

 Bài giảng quy hoạch động


I. Quy hoạch động


1. Phương pháp quy hoạch động

Phương pháp quy hoạch động cùng nguyên lý tối ưu được nhà toán học Mỹ R.Bellman đề xuất vào những năm 50 của thế kỷ 20. Phương pháp này đã được áp dụng để giải hàng loạt bài toán thực tế trong các quá trình kỹ thuật công nghệ, tổ chức sản xuất, kế hoạch hoá kinh tế… Tuy nhiên cần lưu ý rằng có một số bài toán mà cách giải bằng quy hoạch động tỏ ra không thích hợp.
Trong thực tế, ta thường gặp một số bài toán tối ưu loại sau: Có một đại lượng f hình thành trong một quá trình gồm nhiều giai đoạn và ta chỉ quan tâm đến kết quả cuối cùng là trị của f phải lớn nhất hoặc nhỏ nhất, ta gọi chung là giá trị tối ưu của f. Giá trị của f phụ thuộc vào những đại lượng xuất hiện trong bài toán mà mỗi bộ giá trị của chúng được gọi là một trạng thái của hệ thống và cũng phụ thuộc vào cách thức đạt được giá trị f trong từng giai đoạn mà mỗi cách thức được gọi là một điều khiển. Đại lượng f thường được gọi là hàm mục tiêu và quá trình đạt được giá trị tối ưu của f được gọi là quá trình điều khiển tối ưu.
Bellman phát biểu nguyên lý tối ưu (cũng còn gọi là nguyên lý Bellman) như sau: ” Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu A0, nếu giữa chừng ta đi đến một trạng thái A nào đó thì phần quá trình đó kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu.”
Chú ý rằng nguyên lý này được thừa nhận và không chứng minh.
Phương pháp tìm điều khiển tối ưu theo nguyên lý Bellman thường được gọi là quy hoạch động. Thuật ngữ này nói lên được thực chất của quá trình điều khiển là động: có thể trong một số bước đầu tiên lựa chọn điều khiển tối ưu dường như không tốt nhưng tựu chung cả quá trình lại là tốt nhất.
Ta có thể giải thích ý này qua bài toán sau:
Cho một dãy N số nguyên A1, A2, …, AN. Hãy tìm cách xoá đi một số ít nhất số hạng để dãy còn lại là đơn điệu hay tương đương 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 trình tự xuất hiện trong dãy A 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ố lượng số hạng 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ử dãy đã cho là 1 8 10 2 4 6 7. Nếu ta chọn lần lượt 1, 8, 10 thì chỉ chọn được 3 số hạng nhưng nếu bỏ qua 8 và 10 thì ta chọn được 5 số hạng 1, 2, 4, 6, 7 .
Khi giải một số 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. Các 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 tính nhiều lần.
Vậy ý tưởng cơ bản của quy hoạch động thật đơn giản: tránh tính toán lại mọi thứ hai lần, mà lưu giữ kết qủa đã tìm kiếm được vào một bảng làm giả thiết cho việc tìm kiếm những kết quả của 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. Kết quả cuối cùng chính là kết quả của bài toán 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 mức cực độ.
Quy hoạch động là kỹ thuật thiết kế bottom-up (từ dưới lên). Nó được bắt đầu với những trường hợp con nhỏ nhất (thường là đơn giản nhất và giải được ngay). Bằng cách tổ hợp các kết quả đã có (không phải tính lại) của các trường hợp con, sẽ đạt tới kết quả của trường hợp có kích thước lớn dần lên và tổng quát hơn, cho đến khi cuối cùng đạt tới lời giải của trường hợp tổng quát nhất.
Trong một số trường hợp, khi giải một bài toán A, trước hết ta tìm họ bài toán A(p) phụ thuộc tham số p (có thể p là một véc tơ) mà A(p0)=A với p0 là trạng thái ban đầu của bài toán A. Sau đó tìm cách giải họ bài toán A(p) với tham số p bằng cách áp dụng nguyên lý tối ưu của Bellman. Cuối cùng cho p=p0 sẽ nhận được kết quả của bài toán A ban đầu.

2. Các bước thực hiện

Bước 1: Lập hệ thức

ã Dựa vào nguyên lý tối ưu tìm cách chia quá trình giải bài toán thành từng giai đoạn sau đó tìm 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 đó. Hoặc tìm cách phân rã bài toán thành các “bài toán con” tương tự có kích thước nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài toán kích thước đã cho với các kết quả của các “bài toán con” cùng kiểu có kích thước nhỏ hơn của nó nhằm xây dựng phương trình truy toán (dạng hàm hoặc thủ tục đệ quy)
ã .Về 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 của nó là 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 i+1 (i=1,2,..,n-1). Theo nguyên lý tối ưu của Bellman thì việc tối ưu giai đoạn cuối cùng không làm ảnh hưởng đến kết quả toàn bài toá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 ban đầu của 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ể tiến hành tối ưu giai đoạn N-2 … cho đến khi các giai đoạn từ N giảm đế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 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)

Bước 2: Tổ chức dữ liệu và chương trình

Tổ chức dữ liệu sao cho đạt các yêu cầu sau:
a- Dữ liệu được tính toán dần theo từng bước
b- Dữ liệu được lưu trữ để giảm lượng tính toán lặp lại.
c- Kích thước miền nhớ dành cho lưu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ liệu được chọn phù hợp, nên chọn đơn giản dễ truy cập.
Cụ thể:
ã Các giá trị của Fk thường được lưu trữ trong một bảng (mảng một chiều hoặc hai, ba v.v.. chiều).
ã Cần lưu ý khởi trị các giá trị ban đầu của bảng cho thích hợp, đó là các kết quả của các bài toán con có kích cỡ nhỏ nhất của bài toán đang giải.

F1(t(1)) = Max { G1(t(1),d(1)) + F0 (t(0))}
D(1)

ã Dựa vào công thức, phương trình truy toán (*) và các giá trị đã có 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 từng giai đoạn đã xây dựng, tìm ra kết quả bài toán.

Bước 3: Làm tốt

Làm tốt thuật toán bằng cách thu gọn hệ thức (*) và giảm kích thước miền nhớ. Thường tìm cách dùng mảng 2 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.
Trong một số trường hợp có thể thay mảng 2 chiều với các giá trị phần tử chỉ nhận giá trị 0, 1 bởi mảng 2 chiều mới bằng cách dùng kỹ thuật quản lý bít.

3. Hạn chế của quy hoạch động

ã 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 như thế nào là thích hợp, đòi hỏi nhiều thời gian suy nghĩ. Đồng thời không phải lúc nào kết hợp lời 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, ba chiều.. thì khó có thể xử lý dữ liệu với kích cỡ mỗi chiều lớn hàng trăm.
ã Có những bài toán không thể giải dược bằng quy hoạch động.

4. Một vài ví dụ

Ví dụ 1: Tính tổ hợp chập k của n.
Chúng ta có ngay công thức truy hồi quen thuộc là:

Nếu chúng ta tính tổ hợp chập k của n trực tiếp bằng hàm:

Function C(n,k)
If (k=0) or (k=n) then C:= 1
Else C:= C(n-1,k-1)+C(n-1,k).

thì nhiều lần sẽ phải tính đi tính lại giá trị C(i,j) (i<n) (j<k). Do đó thời gian thực hiện của thuật toán này lớn theo sự lặp lại. Chúng ta cũng gặp hiện tượng tương tự khi tính dãy số Fibonacci.

Ngược lại nếu sử dụng bảng chứa các kết quả trung gian (bảng có dạng tam giác Pascal) chúng ta sẽ đạt được một thuật toán hiệu suất hơn. Bảng sẽ được làm đầy dần theo từng dòng.

0 1 2 3 .. k-1 k
0 1
1 1 1
2 1 2 1
n-1 .. .. .. .. C(n-1,k-1) C(n-1,k)

+

n C(n,k)

Cũng có thể chỉ cần dùng  một véc tơ dài là k, véc tơ này biểu diễn cho dòng hiện thời (dòng thứ n+1) của tam giác Pascal tính đến cột k+1 và chúng ta sẽ cập nhật các giá trị vào nó từ trái qua phải. Do vậy thuật toán được thực hiện trong thời gian O(n.k) và chiếm không gian O(k) nếu coi phép cộng là phép toán cơ bản:


Hướng dẫn


[Chương trình mẫu]

uses crt;
const max   	= 20;
      fileinp = 'd:\tohop.inp';
      fileout = 'd:\tohop.out';
var   n, i,j,k 	: byte;
      fi, fo    : text;
      C     	: array[0..max] of longint;
      p1,p2 	: longint;

BEGIN
     clrscr;
     assign(fi,fileinp);
     reset(fi);
     readln(fi,n, k);
     close(fi);
     C[0] := 1; {C(0,1)=1}
     C[1] := 1; {C(1,1)=1}
     for i:=2 to n do
     begin
         p1 := 1;
         for j:=1 to i-1 do
         begin
              p2   := C[j];
              C[j] := p1 + p2;
              p1   := p2;
         end;
         C[i] := 1;
     end;
     assign(fo, fileout);
     rewrite(fo);
     write(fo,C[k],' ');
     close(fo);
END.

II. Một số bài toán tiêu biểu


(Phát biểu, phân tích thuật toán và tổ chức dữ liệu, chương trình)


III. Các bài tập luyện tập


  1. Tính số Catalan
  2. Tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị n đỉnh có trọng số, không có chu trình âm (Thuật toán Floyld).

IV. Các đề tự giải


  1. _
  2. _
  3. _

Tài liệu tham khảo


  1. _
  2. _
  3. _

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: