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

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

Phạm Hải Minh

Quy hoạch động là một phương pháprất hay và mạnh của tin học. Nhưng để giải được các

bài toán bằngphương pháp quy hoạch động thật chẳng dễ dàng chút nào. Chủ yếu họcsinh

hiện nay sử dụng quy hoạch động theo kiểu làm từng bài cho nhớ mẫuvà áp dụng vào

những bài có dạng tương tự.

Qua quá trình học tập tôi đã tự rútra cho mình một số kinh nghiệm về cách giải các bài

toán bằng quy hoạchđộng, xin đưa ra để mọi người cùng tham khảo và góp ý.

1. Lí thuyết:

Phương pháp quy hoạch động gồm 6 bước:

- Bước1: Chia nhỏ bài toán

Lập vectơ P cócác thành phần x1,x2,..,xn. Mỗi vectơ P ứng với một bài toán con củabài

toán. Ban đầu ta xây dựng P với 1 thành phần duy nhất.

- Bước 2: Lập hệ thức quy hoạch động

Xây dựng hàm f(P) là hàm tối ưu của vectơ P (hay hàm tối ưu cho mỗi bàitoán con)

f(P) = g(f(P1),f(P2),..,f(Pn))

g có thể là hàm Max,Min hoặctổng tuỳ yêu cầu của bài toán là tìm Max,Min hay tính tổng.

P gọi là vectơ cha

P1,P2,P3,..,Pn gọi là vectơcon

- Bước 3: Kiểm tra

Nếu không xâydựng được hàm f thì thêm tiếp hoặc bỏ đi từng thành phần của vectơP rồi

quay lại bước 2. Nếu được thì làm tiếp bước 4.

- Bước 4: Tối ưu hoá hệ thức

Tối ưu vectơ P bằng cách xét từng thành phần x của vectơ P:

Chọn vectơ PBest trong P1,P2,P3,..Pn chỉ khác nhau thành phần x sao cho có thể đưa

PBest vào thay P1,P2,P3..,Pn trong hàm g mà không làm thay đổi giá trị của hàm g thì có

thể đơn giản thành phầnx của vectơ P.

- Bước 5: Chọn kiểu quy hoạch động

+ Kiểu 1: Nếu các thànhphần của vectơ con P1 luôn ≤ hay ≥ các thành phần của vectơ cha

P thì ta có thể dùng các vònglặp for lồng nhau để cài đặt.

+ Kiểu 2: Nếu vectơ P và vectơ P1 luôn có mối quan hệ cha con một chiều thì ta có

thểdùng phương pháp đệ quy có nhớ để cài đặt.

+ Kiểu 3: Nếu vectơ P và vectơ P1 luôn có mối quan hệ cha con hai chiềunhưng không rõ

đâu là vectơ cha , đâu là vectơ con vì còn phụ thuộc vào từng bài toán thì ta có thể dùng

phương pháp repeat.. until để cài đặt.