09/14/14
1
QUY HOẠCH ĐỘNG
(Dynamic programming)
09/14/14
2

Bài toán số Fibonacci

Kỹ thuật quy hoạch động

Các bài toán áp dụng QHĐ trên
mảng một chiều và mảng hai chiều

Thảo luận, trao đổi kinh nghiệm,
đánh giá và nhận xét phương pháp
NỘI DUNG
09/14/14
3
Bài toán về dãy số Fibonacci (1)
1
1
2
3
5
Rabbits
09/14/14
4
Bài toán về dãy số Fibonacci (2)
The Fibonacci Numbers
1,1,2,3,5,8,13,21,34,55,89,144,…

6
Bài toán về dãy số Fibonacci (4)
Fibonacci numbers
f(1) = f(2) = 1
f(n) = f(n - 1) + f(n - 2)
Giải bằng chia để trị và đệ quy:
function f(i: Integer): Integer;
begin
if i <= 2 then
Result := 1
else
Result := f(i - 1) + f(i - 2);
end;
f(1) f(2)
f(3) f(2)
f(4)
f(1) f(2)
f(3)
f(5)
f(1) f(2)
f(3) f(2)
f(4)
f(6)
Số phép cộng
f(100) = 354.224.848.179.261.915.075
Số phép cộng
f(100) = 354.224.848.179.261.915.075
So… is this good?
Is it bad?
overlappingoverlapping

thường là nhỏ nhất hay lớn nhất.
QHĐ kết hợp chia để trị với kỹ
thuật tổ chức lưu trữ bộ nhớ.
09/14/14
10
Kỹ thuật QHĐ (2)
4 bước giải quyết bằng QHĐ

Tìm nghiệm của bài toán con nhỏ nhất.

Tìm ra công thức xây dựng nghiệm của bài toán
con thông qua các bài toán con nhỏ hơn.

Tạo ra một bảng lưu giữ các nghiệm của bài
toán con theo công thức đã tìm ra và lưu vào
bảng.

Từ các bài toán con đã giải để tìm nghiệm của
bài toán.
Chúng ta sẽ nghiên cứu KT này bằng các ví dụ
cụ thể sau đây.
09/14/14
11
Một số bài toán áp dụng QHĐ
Tam giác Pascal
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

nhất và Aj<=Ai

Mảng T[i]=j chỉ phần tử đứng trước Ai trong
dãy kết quả là Aj (truy vết kết quả)
09/14/14
15
Dãy con đơn điệu không giảm dài nhất
i 1 2 3 4 5 6 7 8 9 10
A 5 2 3 4 9 10 5 6 7 8
L 1 1 2 3 4 5 4 5 6 7
T 0 0 2 3 4 5 3 7 8 9
09/14/14
16
Bài toán ″Con kiến ″

Bài toán: Trên một sân hình chữ nhật
MxN, được chia thành các ô vuông đơn
vị, mỗi ô chứa một lượng thức ăn. Một
con kiến xuất phát từ ô (1,1) muốnđi
qua sân để đến dòng thứ M. Con kiến
chỉ có thể đi theo một dòng chia nhỏ
trên sân ứng với một dòng của bảng
chữ nhật hoặc đi theo trên một cột của
sân. Hãy chỉ ra đường đi giúp con kiến
có được nhiều thức ăn nhất.
09/14/14
17

FOOD.INP
3 5

ô đang đứng tới một ô mới theo hướng thẳng
đứng chéo trái hoặc chéo phải. Giả thiết rằng
người đó không được vượt ra hai mép trái và
phải của sa mạc.
Hãy tìm đường đi sao cho người đó phải vượt
qua quãng đường ngắn nhất.Mỗi lần đi từ một
ô sang ô mới tiếp theo người đó phải đi hết
quãng đường bằng độ chênh cao giữa hai ô đó
09/14/14
21

SAMAC.INP

Bài toán ″Sa mạc ″
09/14/14
22

SAMAC.OUT
12(Quãng đường Min)
(1,3)(2,4) (3,3) (4,2) (5,2)
Quy tắc đi.

09/14/14
23
Công thức QHĐ

B[i,j] là quãng đường nhỏ nhất đi từ bờ đầu
tiên đến ô (i,j).
B[1,j]= 0 với j = 1 N
B[i,1]= Min { B[i-1,1] + abs(A[i,1] - A[i-1,1]);

Ta có công thức QHĐ như sau:
F(a,b) = min{f(a1,b)+f(a2,b),f(a,b1)+f(a,b2)}
Với a = a1 + a2 và b=b1 + b2