Quy hoạch động
Tài liệu tham khảo về quy hoạch động
Quy hoạch động - Presentation Transcript
Chương III: Qui hoạch động (Dynamic Programming)
Giới thiệu
Phương pháp thực hiện
Một số bài toán tối ưu giải bằng phương pháp quy hoạch động
1. Giới thiệu
Việc thực hiện một giải thuật đệ quy có thể không tối ưu về mặt thời gian/không gian nhớ.
Ví dụ: Tính phần tử thứ n của dãy số Fibonaci
Function F(n: integer): integer;
2 then F:=1 Begin If n
else F:= F(n-1)+F(n-2);
End;
1.61803 ... Độ phức tạp: O(a n ) với a
Do F(n-1) và F(n-2) được tính một cách độc lập! Số lần gọi cần để tính F(n) là số lần gọi để tính F(n-1) cộng
với số lần gọi để tính F(n-2).
Đặc điểm của lời giải đệ quy: thực hiện bài toán từ việc phân tích ở mức cao xuống mức thấp.
Nếu giải quyết bài toán này từ mức thấp lên mức cao ta có giải thuật sau:
Function F(n: integer): integer;
var i: integer; a: array[1..100] of integer;
Begin
a[1]:=1; a[2]:=1;
For i:=3 to n do
a[i]:=a[i-1]+a[i-2];
F:= a[i];
End;
Độ phức tạp: O(n)
Đặc điểm của lời giải bài toán theo phương pháp quy hoạch động: giải quyết bài toán đệ quy từ mức thấp
trước, lời giải của chúng được lưu lại và được sử dụng để tìm lời giải của các bài toán ở mức cao hơn.
Tư tưởng của phương pháp
Sử dụng nguyên lý: “chia để trị”
Cách tiếp cận: “dưới-lên”
Phạm vi áp dụng
Các bài toán có được bằng việc tổ hợp các nghiệm của các bài toán con
Các bài toán tối ưu hoá rời rạc
Nguyên lý của phương pháp:
Nguyên lý tối ưu của Bellman: Trong một dãy tối ưu của các lựa chọn thì một dãy con của nó cũng là tối ưu.
2. Phương pháp thực hiện
Phân tích bài toán (biểu diễn bài toán dưới dạng một bài toán nhiều mức)
Xây dựng giải pháp đệ quy (lập công thức truy hồi)
Lập bảng (sử dụng các mảng để tính toán các giá trị theo kiểu dưới-lên)
Tổng hợp kết quả (kiến tạo một lời giải cho bài toán từ các thông tin đã tính toán)
Xét ví dụ trên
Phân tích bài toán: Xây dựng hàm:
Function F(n: integer): integer;
Giải pháp đệ quy: F(n) = F(n-1)+F(n-2)
Lập bảng: Sử dụng mảng 1 chiều a (array[1..max] of integer) để tính: a[i] = F(i). với i = 1..n .
Cụ thể:
a[1] = a[2] = 1, và:
a[i] = a[i-1] + a[i-2]; với i = 3..n,
Tổng hợp kết quả: F(n) = a[n];
Độ phức tạp tính toán: O(n)
Ví dụ tính C(k,n): tổ hợp chập k của n
Phân tích bài toán: Xây dựng hàm:
Function C(k, n: byte): longint; {giả thiết kĐộ phức tạp tính toán: O(k.n)
3. Một số bài toán tối ưu giải bằng phương pháp quy hoạch động
Chiếc túi xách
Phép nhân tổ hợp nhiều ma trận
Các bài tập
Bài toán chiếc túi xách
Một cái kho chứa n loại đồ vật có kích thước và giá trị khác nhau. Cụ thể:
N* Loại đồ vật i (i=1..n) có: - kích cỡ m[i]
R - gía trị c[i]
- số lượng: không hạn chế
N*. Vậy hắn phải chọn lựaự Một tên trộm mang theo chiếc túi có kích cỡ là p một danh sách các đồ vật sẽ
mang đi như thế nào để cho tổng giá trị lấy cắp được là lớn nhất.
N : số lượng loại đồ vật thứ i cầnầ Tức: Tìm x[1], x[2],..., x[n] (với x[i] x[i].c[i] đạt giá trị cực đạiạ p và
x[i].m[i] x lấy) sao cho:
Bài toán chiếc túi xách
Phân tích bài toán:
Gọi P (r, s) là bài toán chiếc túi xách, với:
N*: kích cỡ chiếc túiế r
N*: số các loại đồ vật khác nhauậ s
(bài toán ban đầu là P (p, n) )
Các giá trị cần tìm:
x[i].c[i] của bài toán P (r, s)ủ l[r,s]: giá trị cực đại
u[r,s]: số lượng loại đồ vật s tối ưu cần lấy (tức: x[s]) của bài toán P (r, s)
Bài toán chiếc túi xách P (r, s)
Giải pháp đệ quy:
Khi s = 1:
u[r, 1] = r div m[1]
c[1] l[r, 1] = u[r, 1]
Khi s > 1:
m[s], s-1] } c[s] + l[r – k l[r, s] = max { k
r div m[s] k 0
m[s], s-1] c[s] + l[r – k’ = k’
u[r, s] = k’
Lập bảng (Bài toán chiếc túi xách)
Procedure LapBang;
Begin
For r:=0 to p do
For s:=1 to n do
If s=1 then Tính u[r, 1] và l[r, 1]
else Tính u[r, s] và l[r, s];
End;
Độ phức tạp tính toán: O(np 2 )
Tổng hợp kết quả (Bài toán chiếc túi xách)
Procedure TongHop;
Begin
r:=p;
For s:=n downto 1 do
begin
x[s]:= u[r,s];
r:= r – x[s].m[s];
end;
End;
Độ phức tạp tính toán: O(n)
Bài toán Phép nhân tổ hợp nhiều ma trận
M n ... M 2 Cần tính M = M 1
m[i] (i=1..n) Trong đó: M i là ma trận cấp m[i-1]
Hãy xác định thứ tự thực hiện các phép nhân sao cho số phép tính là tối thiểu.
M 3 M 2 Ví dụ: Tính M = M 1
5] 50] [50 20] [20 [10
M 3 có số phép toán là:ố M 2 ) ( M 1
5 = 12500 50 50 + 1 0 20 10
M 3 ) có số phép toán là:ố ( M 2 M 1
5 = 6000 50 5 + 2 0 20 10
Phép nhân tổ hợp nhiều ma trận
Phân tích bài toán:
s M s , với r ớ ... M r+1 Gọi P (r, s) là bài toán nhân ma trận: M r
(bài toán ban đầu là P (1, n) )
Giá trị cần tìm:
k[r,s]: vị trí phép toán thực hiện cuối cùng của bài toán P (r, s)
M s ) ... M k+1 ( M k M k-1 ) ... M r+1 (M r
[r+1, s] k = k[r,s]
l[r, s]: số phép tính nhân tối ưu của bài toán P (r, s)
Phép nhân tổ hợp nhiều ma trận
Giải pháp đệ quy:
Trường hợp 1: Khi s = r : l[r, r] = 0
Trường hợp 2: Khi s = r+1:
m[r+1] m[r] l[r, r+1] = m[r-1]
k[r, r+1] = r+1
Trường hợp 3: Khi s > r+1:
m[s] + l[v, s] } m[v-1] l[r, s] = min { l[r, v-1] + m[r-1]
s v r+1
(v là các vị trí phép toán thực hiện cuối cùng khác nhau)
m[s] + l[v’, s] m[v’-1] = l[r, v’-1 ] + m[r-1]
(v’ là vị trí tối ưu trong số các vị trí của v)
k[r, s] = v’
Nhận xét : Có thể ghép trường hợp 2 vào trường hợp 3!
Lập bảng (Bài toán phép nhân tổ hợp nhiều ma trận)
Procedure LapBang;
Begin
For s:=1 to n do
For r:=s downto 1 do
If r = s then l[r, r] := 0
else Tính l[r, s] và k[r, s];
End;
Độ phức tạp tính toán: O(n 3 )
Tổng hợp kết quả (Bài toán phép nhân tổ hợp nhiều ma trận)
Procedure TongHop;
Begin
writeln(‘S ố phép tính là tối thiểu:’, l[1, n]);
i:=n;
TimVT(1, n); {Nhằm lần lượt xác định các giá trị x[i]: vị trí phép nhân cần thực hiện trong lần nhân thứ i
(i=1..n-1)}
writeln(‘ Thứ tự thực hiện các phép nhân :’);
For i:=1 to n-1 do writeln(x[i]);
End;
Trong đó thủ tục TimVT được xây dựng đệ quy như sau:
Procedure TimVT(r, s);
Begin i:=i-1; vt:= k[r, s]; x[i]:= vt;
If (vt > r+1) and (vt < s) then
begin TimVT(r, vt-1);
TimVT(vt, s);
end;
End;
Bài tập
1. Tính giá trị xác suất P(i, j) (i, j: byte). Biết rằng:
P(i, j) = 1 nếu i=0 và j>0
= (P(i-1, j)+ P(i, j-1))/2 nếu i>0 và j>0
= 0 nếu ngược lại
Bài toán xâu trong cực đại: S là xâu trong của T nếu S nhận được bằng cách xoá đi một số ký tự nào đó. Ví
dụ: ‘ABC’ là xâu trong của ‘GAHEBOOC’
Bài toán: Cho 2 xâu T1, T2. Tìm một xâu S là xâu trong chung của T1 và T2 có độ dài cực đại.
Ví dụ: T1=‘ABCDAE’ và T2=‘XYACADK’ có xâu ‘ACD’ là xâu trong chung với độ dài cực đại.
Bài toán du lịch: Một người đi từ thành phố 0 đến thành phố n và có thể đi đ i k i 2 ….. i 1 qua n-1
thành phố khác 1, 2,..., n-1 , theo lộ trình : 0 n, t rong đó: 0 < i 1 < i 2 < …< i k < n, Giá vé của xe đi từ thành
phố i đến thành phố j là c[i,j]. Tìm một lộ trình từ thành phố 0 đến thành phố n sao cho tổng chi phí về giá vé
đạt cực tiểu.
Bài toán sinh viên ôn thi: Một sinh viên còn m ngày để ôn thi n môn. Theo kinh nghiệm của anh ta, nếu ôn
môn j trong i ngày thì được điểm là a[i,j]. Giả sử cho biết các a[i,j] (với a[i,j]
