Tuesday, March 14, 2017
CHƯƠNG IV. MỘT SỐ BÀI
TOÁN QUY HOẠCH ĐỘNG TIÊU BIỂU
1. Khái niệm về quy
hoạch động:
Phương pháp
quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm
phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số
hữu hạn bài toán con.
Đối với một
số bài toán đệ quy, nguyên lý chia để trị (divide and conquer) thường đóng vai
trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta
chia nhỏ nó thành nhiều bài toán cao cùng dạnh với nó để giải quyết độc lập.
Trong khi
phương án quy hoạch động, nguyên lý để trị càng được thể hiện rõ: Khi không biết
phải giải quyết những bài toán con nào, ta phải đi giải quyết toàn bộ các bài
toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại
theo một sự phối hợp nào đó để giải quyết những bài toán tổng lớn hơn.
Đó chính là
điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy và cũng lf nội dung
phương pháp quy hoạch động:
-Phép phân giải
đệ quy bắt đầu từ bài toán lớn phân ra thành nhiều bài toán con và đi giải từng
bài toán con đó. Việc giải từng bài toán con đưa lại đưa về phép phân ra tiếp
thành nhiều bài toán nhỏ hơn và lại đi giải các bài toán nhỏ hơn bất kể nó đã
được giải hay chưa.
-Quy hoạch
đông bắt đầu từ việc giải tất cả các bài toán nhỏ nhất( bài toán cơ sơ) để từ
đó từng bước giải quyết nhưng bài toán lớn hơn, cho tới khi giải được bài toán
lớn nhất(bài toán ban đầu).
Bài toán giải theo phương pháp quy hoạch động
gọi là bài toán quy hoạch động.
Công thức phối
hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn gọi là công thức
truy hồi của quy hoạch động.
Tập các bài
toán có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi là cơ sở quy
hoạch động.
Không gian
lưu trữ lười giải các bài toán con để tìm cách phối hợp chunsh ra gọi là bảng
phương án của quy hoạch động.
Trước khi áp
dụng phương pháp quy hoạch động ta phải xem xét phương pháp đo có thỏa mãn những
yêu cầu dưới đây không:
-
Bài toán lớn phải phân rã đã được thành nhiều
bài toán con, mà sự phối hợp lời giải của cá bài toán con đó cho ta lời giải của
bài toán đó.
-
Vì quy hoạc
động là đi giải tất cả các bài toán con, nên nếu không đủ không gian vật lý lưu
trữ lời giải (bộ nhớ, đĩa…) để phối hợp chúng thì phương pháp quy hoạch động
cũng không thể thực hiện được.
-
Quá trình từ bài toán cơ sở tìm ra lời giải bài
toán ban đầu phải qua hữu hạn bước. Các bước cài đặt một chương trình sử dụng
quy hoạch động.
+ Giải tất cả các bài toán cơ sở (thông thường rất dễ), lư các lời giải
vào bảng phương án.
+ Dùng công thức truy hồi phối hợp những lời giải của các bài toán nhỏ đã
lưu trong bảng phương án. Cho tới khi bài toán ban đầu tìm được lời giải.
+ Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.
Cho tới nay, vẫn chưa có một định lý nào cho biết một cách chính xác những
bài toán nào có thể giải quyết bằng quy hoạch động. Tuy nhiên để biết được bài
toán có thể giải quyết bằng quy hoạch động hay không ta có thể đặt câu hỏi:
1.”Một nghiệm tối ưu của bài
toán lớn có phải là sự phối hợp các nghiệm tối ưu của các bài toán con hay
không?”.
2.”Liệu có thể nào lưu trữ
được nghiệm các bài toán con dưới một hình thức nào đó để phối hợp tìm được
nghiệm bài toán lớn?”.
2. Ví dụ các bài toán
có thể giải bằng phương pháp quy hoạch động.
2.1 Bài toán tính N!.
Cho mảng f từ 0..30.
Gọi f[i] là giá trị của
i!.
Vì ta biết n! =
n*(n-1)! . Từ đây ta có công thức quy hoạch động sau:
f[i]:= f[i-1]*i
kết quản bài toán là
f[n].
code tham khảo:
//////// Độ phức tạp
O(n)
Const f1=’gt.inp’;
fo:= ‘gt.out’;
var n:
integer;
f: array[0..30] of qword;
procedure giaithua;
var i: integer;
begin
f[0]:= 1;
for i:= 1 to n do
f[i]:= f[i-1]*I;
end;
BEGIN
Assign(input, fi); reset(input);
Assign(output,fo); rewrite(output);
Readln(n);
giaithua;
writeln(f[n]);
close(input); close(output);
