Đại học Công Nghệ Thông Tin
Đại học Quốc gia Thành phố Hồ Chí Minh

BÁO CÁO:
PHƯƠNG PHÁP GIẢI TOÁN TRONG TIN HỌC:
QUY HOẠCH ĐỘNG
Môn học: PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC
GVHD : GS.TSKH. Hoàng Kiếm
Học viên: Trần Ngọc Huy – CH1301027
TP.HCM, tháng 5 năm 2014
Mục lục
1. Mở đầu
Để giải quyết một bài toán tối ưu trong tin học, ta có thể sử dụng nhiều cách khác
nhau [3]. Trong đó, phương pháp quy hoạch động được nhiều người quan tâm vì tính
hiệu quả về mặt lưu trữ cũng như thời gian xử lý kết quả. Về cơ bản, quy hoạch động
2
chia nhỏ bài toán lớn về các bài toán con có phạm vi nhỏ hơn, tiếp tục như vậy đến khi
bài toán nhỏ “đủ dễ” để có thể giải quyết. Như vậy, việc tổng hợp lời giải từ các bài toán
con là bước đi tìm lời giải cho bài toán lớn hơn. Có thể nói quy hoạch động là phương
pháp giải toán trong tin học ứng dụng nguyên lý sáng tạo “phân nhỏ” và “kết hợp”. Nội
dung được đề cập trong bài luận này là khái niệm cơ bản và phương pháp để giải một bài
toán quy hoạch động, lần lượt được giới thiệu trong phần 2 và 3. Đồng thời giới thiệu hai
cách tiếp cận bài toán quy hoạch động: một là cách tiếp cận bottom-up, hai là cách tiếp
cận top-down trong phần 4. Cuối cùng, phần 5 sẽ tóm tắt nội dung toàn bộ bài luận.
2. Khái niệm
Một trong các hướng giải quyết các bài toán tối ưu hóa trong tin học là ứng dụng
quy hoạch động. Đây là một phương pháp thường dùng để giải quyết các bài toán tối ưu
có cấu trúc phức tạp (khó có thể giải được bằng phương pháp trực tiếp). Nền tảng của
phương pháp này được xây dựng dựa trên nguyên lý tối ưu của Richard Bellman
(Bellman’s Principle of Optimality, 1940) :
“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”

• Tồn tại cấu trúc tối ưu giữa các bài toán.
• Kích thước của không gian các bài toán phải đủ nhỏ để có thể lưu trữ trong quá
trình xử lý.
Để xác định cấu trúc tối ưu cho không gian F[w] của các bài toán, ta cần phải xây
dựng một hệ thức truy toán (công thức quy hoạch động) biểu diễn mối liên quan giữa
một bài toán bất kỳ F[w] với các bài toán liên quan có kích thước nhỏ hơn :
4
F[w] = Q{F[w’], F[w’’], …} (*)
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 để xây
dựng cấu trúc tối ưu 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 rất nhiều thời gian suy nghĩ.
Một điểm cần lưu ý nữa khi ta xác định không gian biểu diễn cho bài toán (hay
còn gọi là trạng thái quy hoạch động) là đồ thị biểu diễn sự chuyển tiếp giữa các trạng
thái quy hoạch động phải là đồ thị có hướng không chu trình. Nói cho đơn giản, giả sử
đồ thị biểu diễn đó tồn tại một chu trình A
1
, A
2
, …, A
N
, A
1
thì khi tính giá trị cho hàm
quy hoạch động tại A
1
ta sẽ dựa trên A
2
và A
2
lại dựa trên A

6
Khi đó, để tối ưu hóa F[x, y] ta chỉ đơn giản là lấy giá trị tối ưu trong số các giá trị
ứng với các lựa chọn nói trên :
F[x, y] = max{F[x – 1, y – 1], F[x, y – 1], F[x + 1, y – 1]} + A[x, y]
Cuối cùng, chúng ta cần xác định khi nào bài toán F[x, y] là đủ “nhỏ” để giải
quyết một cách trực tiếp : x và y = 1 : F[x, y] = A[x, y].
Qua ví dụ này, chúng ta có thể rút ra nhận xét sau : Bản chất của phương pháp quy
hoạch động là nhằm xác định một chuỗi các chuyển tiếp với chi phí tối ưu từ các trạng
thái khởi đầu, ứng với các bài toán đủ “nhỏ” để giải trực tiếp, qua một số trạng thái
trung gian, ứng với các bài toán con trung gian, và đến trạng thái đích, ứng với bài
toán lớn cần giải.
Ví dụ 2 : Xét bảng kích thước M * N (M, N 100) với một con cờ đặt ở ô trên trái
của bảng. Tại mỗi nước đi, con cờ chỉ có thể đi thẳng xuống hay đi sang phải một ô.
Hỏi có bao nhiêu cách di chuyển khác nhau để con cờ di chuyển từ vị trí ban đầu đến
ô phải dưới của bàn cờ.
Giải pháp : Bài toán nêu ra trong ví dụ này về bản chất là một bài toán đếm chứ
không phải một bài toán tối ưu. Tuy nhiên, đối với các dạng bài toán đếm như vậy
chúng ta vẫn có thể áp dụng được nguyên tắc “chia để trị” : Thay vì tìm công thức
tính trực tiếp, chúng ta xây dựng công thức truy hồi biểu diễn hàm giá trị (đáp số) của
bài toán lớn dưới dạng tổ hợp các hàm giá trị của các bài toán con có quy mô nhỏ
hơn.
7
Ta có nhận xét, để đến được một ô (x, y) bất kỳ trên bảng thì trước đó con cờ phải
ở một trong hai ô (x – 1, y) và (x, y – 1). Như vậy, tương tự như ở ví dụ trên, chúng ta
có hai trường hợp :
• Nếu trước khi đến ô (x, y) ta ràng buộc là con cờ phải đến ô (x – 1, y) trước thì ta
có tất cả F[x – 1, y] cách di chuyển khác nhau để đến ô (x, y).
• Tương tự, nếu ràng buộc con cờ phải đến ô (x, y – 1) trước khi đến (x, y) thì ta có
tất cả F[x, y – 1] cách di chuyển khác nhau.
Khi đó, để xác định F[x, y] ta lấy tổng các cách đi khác nhau của hai trường hợp

) về ô (x, y) trong đúng z
bước”
Dễ thấy trạng thái biểu diễn cho một bài toán con thuộc lớp bài toán nói trên là
một bộ ba (x, y, z). Ta gọi F[x, y, z] là lời giải cho bài toán tương ứng. Như vậy, khi
ta thay x = x
1
, y = y
1
thì lời giải cho bài toán lớn ban đầu là .
Để tính F[x, y, z] thì ta có xét bốn vị trí có thể có của con cờ ngay trước khi di
chuyển đến ô (x, y) ở nước đi z : (x – 1, y), (x, y – 1), (x + 1, y) và (x, y + 1). Khi đó,
công thức quy hoạch động tính F[x, y, z] có thể được viết như sau :
F[x, y, z] = max{F[x – 1, y, z – 1] + |A[x, y] – A[x – 1, y]|,
F[x, y – 1, z – 1] + |A[x, y] – A[x, y – 1]|,
F[x + 1, y, z – 1] + |A[x, y] – A[x + 1, y]|,
F[x, y + 1, z – 1] + |A[x, y] – A[x, y + 1]|}
Khi đặt z = 0, ta được lớp các bài toán con đủ “nhỏ” để có thể giải trực tiếp :
• F[x
0
, y
0
, 0] = 0.
• F[x, y, 0] = +oo. (xem như không thể đến được)
Ví dụ 4 : Cho hai chuỗi A
1
A
2
…A
M
và B

i
và B
j
sao cho ký tự cuối x = A[i] = B[j]. Ở trường hợp này, rõ ràng
F[i, j] = F[i – 1, j – 1] + 1.
• A[i] B[j] : Lúc này lại có hai khả năng có thể xảy ra là A[i] không thuộc dãy
con chung dài nhất hay B[j] không thuộc dãy con chung dài nhất. Ở trường hợp
này, F[i, j] sẽ có giá trị tương ứng là F[i – 1, j] hay F[i, j – 1] tùy theo việc ta chọn
A[i] hay B[j] thuộc dãy con chung dài nhất. Tất nhiên, để tối ưu hóa giá trị của F[i,
j] ta sẽ luôn chọn trường hợp tốt nhất : F[i, j] = max { F[i – 1, j], F[i, j – 1] }
Cuối cùng, ta giải trực tiếp các bài toán con đủ “nhỏ” : F[i, 0] = 0 và F[0, j] = 0.
10
Ví dụ 5 : Cho một valy có thể chứa W 10000 đơn vị trọng lượng. Có N 200 loại
đồ vật (số lượng mỗi đồ vật không hạn chế). Đồ vật i có trọng lượng A[i] và giá trị là
C[i]. Hỏi nên chọn mỗi loại đồ vật bao nhiêu để xếp vào valy để tổng giá trị hàng hóa
trong valy là lớn nhất ?
Giải pháp : Để xây dựng không gian quy hoạch động cho bài toán, ta định nghĩa họ
bài toán sau đây :
“Xác định xem với một valy có thể chứa x đơn vị trọng lượng và y loại đồ vật từ
1 đến y trong số N loại đồ vật nói trên thì ta có thể chất đồ vào valy để đạt tổng
giá trị hàng hóa lớn nhất là bao nhiêu ?”
Trạng thái quy hoạch động cho các bài toán trên được biểu diễn dưới dạng một
cặp tham số (x, y). Gọi F[x, y] là lời giải tối ưu cho bài toán tương ứng, ta sẽ lập hệ
thức truy toán cho F[x, y] như sau :
• Nếu ta quyết định bỏ đồ vật loại y vào trong valy (chỉ xét khi A[y] x) thì ta có
thể tính F[x, y] = F[x – A[y], y] + C[y].
• Nếu ta quyết định không bỏ thêm bất cứ đồ vật loại y nào vào trong valy nữa thì
F[x, y] = F[x, y – 1].
Như vậy, ta một thời điểm bất kỳ khi tính F[x, y] ta cần chọn quyết định tối ưu để
cực đại hóa giá trị của F[x, y] : F[x, y] = max { F[x – A[y], y] + C[y], F[x, y – 1] }

Từ hai nhận xét trên ta thấy trạng thái của bài toán con (X, S) có thể được biểu
diễn trên máy tính dưới dạng một số nguyên N bit, trong đó có X bit 1. Như vậy,
không gian bài toán con của ta sẽ có kích thước 2
N
và với N 16 thì kích thước đó
hoàn toàn thích hợp cho việc lưu trữ.
Ở bước tiếp theo, ta cần xây dựng cấu trúc tối ưu / hàm quy hoạch động cho không
gian bài toán nói trên. Để dễ hình dung, ta gọi Q(S) là giá trị của số nguyên N bit biểu
diễn cho bài toán con (X, S) và định nghĩa F[Q(S)] là số cách ghép tương ứng. Ta xét
các bó hoa T có khả năng ghép với bình hoa X :
• A[X, T] = A[T, X] = 1.
• Q(S) & 2
T
= 2
T
(bit thứ T của Q(S) có giá trị bằng 1).
13
Nếu ta chọn ghép X với T, thì khi đó số cách ghép cho X – 1 bình hoa với tập hợp
S – {T} bó hoa còn lại là F[Q(S – {T})] = F[Q(S) – 2
T
]. Từ đó, ta rút ra công thức tính
F[Q(S)] như sau : F[Q(S)] = F[Q(S) – 2
T
]
Để rút ra đáp số cho bài toán đếm ban đầu, ta thay X = N : F[Q(S)] = F[2
N
– 1].
Lưu ý : Trong trường hợp này, các bài toán đủ “nhỏ” để có thể giải trực tiếp chính
là các bài toán (X, S) với X = |S| = 1.
Qua ví dụ này, chúng ta thấy tầm quan trọng của việc hoạch định không gian / xác

phải tính lại như ở các mô hình đệ quy vét cạn thường chỉ lưu trữ trạng thái hiện hành
đang xem xét.
Để minh họa cho hai phương pháp trên, chúng ta sẽ thử phân tích một số đoạn
code cài đặt cho ví dụ 2 ở trên :
\
Bottom – Up:
15
// Giải trực tiếp các trường hợp biên
for (int i = 1; i <= N; i++) F[1, i] = 1;
for (int i = 1; i <= M; i++) F[i, 1] = 1;
// Tổng hợp lời giải cho trường hợp lớn từ các trường hợp con
for (int i = 2; i <= M; i++)
for (int j = 2; j <= N; j++) F[i, j] = F[i – 1, j] + F[i, j – 1];
// Lời giải cho bài toán gốc
return F[M, N];
Top – Down :
// Giải quyết bài toán con (i, j)
int P(int i, int j)
{
// Nếu (i, j) đủ nhỏ thì giải trực tiếp
if (i == 1 || j == 1) return 1;
// Kiểm tra trong bộ nhớ xem (i, j) đã được giải chưa
if (F[i][j] >= 0) return F[i][j];
// Nếu chưa, giải (i, j) bằng cách đệ quy phân rã
F[i, j] = P(i – 1, j) + P(i, j – 1);
// Trả về lời giải tìm được
return F[i, j];
}
// Chương trình chính
int main()

nhỏ hơn theo nguyên lý “phân nhỏ”. Sau đó, tổng hợp lời giải của các bài toán con
để tìm lời giải cuối cùng cho bài toán lớn sử dụng nguyên lý sáng tạo “kết hợp”.
Để giải quyết một bài toán bằng phương pháp quy hoạch động, trước hết ta phải
xác định không gian trạng thái của bài toán, sau đó áp dụng một trong hai phương
pháp bottom-up, hoặc top-down để cài đặt.
Tài liệu tham khảo
[1] Giải Thuật và Lập Trình, ĐHSP Hà Nội (1999 – 2002), Lê Minh Hoàng
[2] Phương pháp nghiên cứu khoa học trong tin học, GS.TSKH. Hoàng Kiếm.
[3] Giáo trình thuật toán thuật giải, GS.TSKH. Hoàng Kiếm.
[4] Introduction To Algorithm, 2
nd
Edition, Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest.
18