//
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 (2)

Đặt vấn đề

Các bài toán quy hoạch động chiếm một vị trí khá quan trọng trong việc tổ chức hoạt động và sản xuất (nhất là việc giải quyết các bài toán tối ưu). Chính vì lẽ đó mà trong các kỳ thi học sinh giỏi Quốc Gia và Quốc Tế chúng ta thường gặp loại toán này. Tư tưởng chủ đạo của phương pháp này dựa trên nguyên lí tối ưu của Bellman phát biểu như sau :

         “Nếu một dãy các lựa chọn là tối ưu thì mọi dãy con của nó cũng tối ưu “

Ngoài ra khi thiết kế các thuật toán quy hoạch động ta thường dùng kỹ thuật “Phân vùng để xử lí “, nghĩa là để giải quyết một bài toán lớn ta chia nó thành nhiều bài toán con có thể giải quyết độc lập. Trong phương pháp quy hoạch động, việc thể hiện nguyên lí này được đẩy đến cực độ. Để giải quyết các bài  toán quy hoạch động ta có thể theo sơ đồ sau :

a.)     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ễ thấy hiện tượng tràn bộ nhớ

b.)     Tổ chức dữ liệu chương trình : Tổ chức giữ 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 tin chúng ta hay gặp đòi hỏi một vài mảng lớn .

c.)      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 kích thước miền nhớ .

Các thao tác tổng quát của quy hoạch động

  1. Xây dựng hàm quy hoạch động.
  2. Lập bảng lưu lại giá trị của hàm.
  3. Tính các giá trị ban đầu của bảng.
  4. Tính các giá trị còn lại theo kích thước tăng dần của bảng cho đến khi đạt được giá trị tối ưu cần tìm.
  5. Dùng bảng lưu để truy xuất lời giải tối ưu.

Trong các lời hướng dẫn các bài toán, chúng tôi sẽ đưa các bạn đi theo từng phần như sơ đồ giải quyết trên . Chúng ta có thể phân loại các bài toán quy hoạch động theo nhiều cách. Để các bạn tiện theo dõi , tôi xin phân loại theo cách lưu  (tức là tổ chức chương trình) là các mảng một chiều hay nhiều chiều.

Các bài toán cụ thể

I. Dạng một:

Đa phần dạng bài toán thường gặp trong loại này đó là loại có công thức truy hồi như sau :

Mind[I]:=Min Mind[J] +Giá Trị Để JI ;J=0..I Hoặc là :

Maxd[I]:=MaxMaxd[J]+Giá Trị Để JI ;J=0..I .

Chúng ta có thể thấy rõ ràng đối với các bài toán mà chúng ta sẽ xét sau đây :

Bài toán mẫu 1: Bài toán đổi tiền

Đề bài :

Cho một ngân hàng có N loại tiền mệnh giá A[1],A[2],…A[N] với số lượng tiền mỗi loại không giới hạn . Cần chi trả cho khách hàng một số tiền M đồng . Hãy cho biết cần bao nhiêu tiền mỗi loại để chi trả sao cho số lượng tờ là ít nhất .

Dữ liệu vào từ file: Tien.Inp  như sau :

  • Dòng đầu tiên ghi 2 số N,M . ( N<=100,M<=10000)
  • Dòng thứ hai ghi N Số : A[1], A[2],…A[N]

Kết quả:    ghi ra File : Tien.Out Nh Sau :

  • Dòng Đầu tiên ghi số tờ cần dùng ,Nếu không thể đổi đựoc thì ghi số 0 và không cần thực hiện tiếp.
  • Dòng tiếp theo ghi số n số biểu hiện cho số tờ cần dùng cho mỗi loại. “

Hướng dẫn :

Chúng ta gọi Mind[I] là số lượng tờ ít nhất để trả số tiền I, như vậy bài toán yêu cầu chúng ta xác định Mind[M] . Ta nhận thấy rằng để được số tiền là I thì chúng ta sẽ có các cách để tạo thành số tiền đó khi chúng ta dùng thêm một tờ là : I-A[K1],I-A[K2],…I-A[KJ] ,Trong đó KJ là số thoả mãn mà A[KJ] < I. Vậy để số tiền tối ưu nhất là chúng ta cần tìm thấy trong các Mind[I-A[K1]]+1, Mind[I-A[K2]]+1, … , Mind[I-A[KJ]]+1 . Có công thức quy hoạch động như sau:

Mind[I]:=MinMind[I-A[J]]+1,  J  – thoả mãn : A[J]<I.

Từ đó chúng ta có thủ tục quy hoạch động như sau :

Procedure Quy_Hoach_Dong;

Begin

Mind[0]:=0;

For I:=1 To M Do

Begin

Min:=Maxint;

For J:=1 To N Do

If (Mind[I-A[J]]+1<Min)And (A[J]<I) Then

Begin

Min:=Mind[I-A[J]]+1;

Luu[I]:=J;

End;

Mind[I]:=Min;

End;

End;

Trong đó mảng Luu là mảng chứa đựng loại tiền nào cần dùng cuối cùng để đến số tiền I. Như vậy chúng ta có cách để tìm lại các loại tiền cần dùng bằng mảng Luu như sau :

J:=Luu[M];

I:=M;

While J0 Do

Begin

Write(A[J]);

I:=I-J;

J:=Luu[I];

End;

Như vậy chúng ta sẽ giải quyết bài toán trên một cách ngắn gọn và đơn giản. Để tăng tính tự sáng tạo của các bạn, kể từ bài toán sau chúng tôi chỉ nêu qua các thủ tục và công thức quy hoạch động. Nếu các bạn không giải quyết được vấn đề nhỏ đó thì có thể tham khảo phần lời giải của chúng tôi. Tiếp sau đây là một loạt bài toán tương tự bài toán 1, mà thực chất chúng chỉ là một dạng bài cố định, nó chỉ biến dạng đi về lời lẽ nhưng đều giống nhau về bản chất .

Bài toán mẫu 2:                           Bài toán nối diểm (Wires)

Đề bài:

Trên hai đuờng thẳng song song L1 và L2 người ta đánh dấu trên mỗi đường N điểm. Các điểm trên đừơng thẳng L1 được đánh số từ 1 đến N, từ trái qua phải, còn các điểm trên đường thẳng L2 được đánh số bởi P[1],P[2],…P[N] cũng từ trái qua phải, trong đó P[1],P[2],..P[N] là một hoán vị của các số 1,2,…N.

Ta gọi các số gán cho các điểm là số hiệu của chúng . Cho phép nối hai điểm trên 2 đường thẳng có cùng số hiệu .

Yêu cầu : Tìm cách nối được nhiều cặp điểm nhất với điều kiện các đoạn nối không được cắt nhau .

Dữ Liệu : Vào từ File BaiToan2.Inp:

  • Dòng Đầu tiên chứa số nguyên dương N (N<=1000).
  • Dòng thứ hai chứa các số P[1],P[2],….P[N].

Kết quả ghi ra file : BaiToan2.Out:

  • Dòng đầu tiên chứa K là số lượng đoạn nối tìm được
  • Dòng tiếp theo chứa K số hiệu của các đầu mút của các đoạn nối được ghi theo thứ tự tăng dần .

Ví dụ :

      WIRES.INP         WIRES.OUT
9 2 5 3 8 7 4 6 9 1 5 2 3 4 6 9

Hướng dẫn :

Gọi Maxd[I] là số đoạn thẳng tối đa của các cặp nối của các điểm từ 1I .  Chúng ta sẽ có công thức quy hoạch động như sau :

Maxd[I]:=MaxMaxd[P[J]]+1;J:=0ViTri(I)

Trong đó ViTri (I) Là hàm cho biết Vị trí Của I Trong Dãy P[1],P[2],..P[N] (Tức là I = P[X] Thì ViTri(I) = X);

Bằng cách phân tích hoàn toàn tơng tự như bài toán 1 mà ta có công thức truy hồi như trên . Các bước giải bài toán có thể được nói gọn trong hai thủ tục và hàm :

Funtion ViTri(I:Integer):Integer;

Var J:Integer;

Begin

For J:=1 To N Do

If P[J]=I Then

Begin

ViTri:=J;

Exit;

End;

End;

Thủ  Tục quy hoạch động như sau :

Procedure Quy_Hoach_Dong;

Begin

Maxd[0]:=0;

For I:=1 To N Do

Begin

Max:=0;

For J:=0 To ViTri(I) Do

If Maxd[P[J]]>Max Then

Begin

Luu[I]:=J;

Max:=Maxd[P[J]];

End;

Maxd[I]:=Max;

End;

End;

Mảng Luu là mảng Luu[I] lưu lại điểm trước I mà tiếp đó sẽ nối I . Chính vì điều đó chúng ta có thể ghi ra ngược lại một cách dễ dàng.


Các bài giảng khác


  1. _
  2. _
  3. _


Bài tập


  1. _
  2. _
  3. _
Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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ả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

lost

Cimitero San Michele

Stump Lake Star Trail

More Photos

Thống kê

  • 115,481 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: