Thuật toán quan hệ động ít biến
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (151.3 KB, 10 trang )
Tiết kiệm biến cho các bài toán quy hoạch động
Nguyễn Xuân Huy
Các bài toán quy hoạch động (QHĐ) chiếm một vị trí kháquan trọng trong việc tổ chức
hoạt động và sản xuất. Chính vì lẽ đó mà trongcác kỳ thi học sinh giỏi Quốc gia và Quốc tế
chúng ta thường gặp loại toán này.Thông thường những bạn nào dùng phương pháp quay
lui, vét cạn cho các bài toánQHĐ thì chỉ có thể vét được các tập dữ liệu nhỏ, kích thước
chừng vài chụcbyte. Nếu tìm được đúng hệ thức thể hiện bản chất QHĐ của bài toán và
khéo tổchức dữ liệu thì ta có thể xử lý được những tập dữ liệu khá lớn.
Có thể tóm lược nguyên lý QHĐ do Bellman phát biểu nhưsau: Quy hoạch động là lớp các
bài toán mà quyết định ở bước thứ i phụthuộc vào quyết định ở các bước đã xử lý trước
đó.
Để giải các bài toán QHĐ ta có thể theo sơ đồ sau đây:
Sơ đồ giải bài toán QHĐ:
1.Lập hệ thức: Lập hệ thức biểu diễn tương quan quyết định củabước đang xử lý với các
bước đã xử lý trước đó. Hệ thức này thường là các biểuthức đệ quy do đó dễ gây ra
hiện tượng tràn miền nhớ khi ta tổ chức chươngtrình trực tiếp bằng đệ quy.
2. Tổchức dữ liệu và chương trình: Tổ chức dữ liệu tính toán dần theo từngbước. Nên
tìm cách khử đệ quy. Thông thường, trong các bài toán chúng ta haygặp đòi hỏi một
vài mảng hai chiều.
3. Làmtốt: Làm tốt thuật toán bằng cách thu gọn hệ thức QHĐ và giảmkích thước miền
nhớ.
Dưới đây là thí dụ minh họa.
Bài toán 1: (Chia thưởng) Cầnchía hết m phần thưởng cho n học sinh sắp theo thứ tự từ
giỏi trở xuống sao chomỗi bạn không nhận ít phần thưởng hơn bạn xếp sau mình.
Bài giải:
1. Lập hệ thức: Gọi Chiăm,n) là số cáchchia m phần thưởng cho n học sinh, ta thấy:
1.1. Nếu không có học sinh nào(n=0) thì không có cách chia nào (Chia=0).
1.2. Nếu không có phần thưởngnào (m=0) thì chỉ có một cách chia (Chia =1 - mỗi
học sinh nhận 0 phần thưởng).Ta cũng quy ước Chia (0,0)=1.
1.3. Nếu số phần thưởng íthơn số học sinh (m < n) thì từ học sinh thứ m+1 trở đi sẽ
không được nhận phần thưởng nào, tức là m phần thưởng chỉ có thể chia tối đã cho
m học sinh.Chia (m,n)=Chia (m,m), nếu m < n.
1.4. Ta xét trường hợpm>=n. Ta tách các phương án chia thành hai nhóm không giao
nhau:
-Nhóm thứ nhất gồm các phương án trong đó học sinh thứ n không được nhận
thưởng,tức là m phần thưởng chỉ chia cho n-1 học sinh và do đó số cách chia, tức
là sốphần tử của nhóm này sẽ là: Chia (m,n-1).
-Nhóm thứ hai gồm các phương án mà học sinh thứ n cũng được nhận thưởng.
Khi đó,do học sinh đứng cuối bảng thành tích được nhận thưởng thì mọi học sinh
kháccũng sẽ có thưởng. Do ai cũng được thưởng nên ta bớt của mỗi người một
phầnthưởng (để họ lĩnh sau), số phần thưởng còn lại (m-n) sẽ được chia cho n
họcsinh. Số cách chia khi đó sẽ là Chia (m-n,n).
Tổng số cách chia cho trườnghợp m>=n sẽ là tổng số phần tử của hai nhóm, ta
có:Chia (m,n)=Chia (m,n-1)+Chia (m-n,n).
2. Tổ chức dữ liệu và chương trình: Ta cóphương án đầu tiên của giải thuật Chia như
sau:
{PHUONG AN 1: de quy}
function Chia (m,n: integer):longint;
begin
if m = 0 then Chia:=1
else {m>0}
if n = 0 then {m>0;n=0} Chia:=0
else {m,n > 0}
if m < n then {0<M
else {m>=n>0}
Chia:=Chia (m-n,n)+Chia (m,n-1);
end;
Làm tốt lần 1: Phương án 1 khá dễtriển khai nhưng chương trình sẽ chạy rất lâu, bạn hãy
thử gọi Chiă66,32) đểcảm nhận được điều trên. Diễn tả đệ quy thường trong sáng, nhàn
tản, nhưng khithực hiện sẽ sinh ra hiện tượng gọi lặp lại những hàm đệ quy. Cải tiến đầu
tiênlà tránh những lần gọi lặp như vậy. Muốn thế chúng ta tính sẵn các giá trị củahàm theo
các trị của đầu vào khác nhau và điền vào một mảng hai chiều cc. Mảngcc được mô tả như
sau:
const MN=100;{gioi han tren cua m va n}
var cc:array[0..MN,0..MN] of longint;
Ta quy ước cc[i,j] là số cách chia i phần thưởng cho jhọc sinh.
Theo phân tích của phương án 1, ta có:
-cc[0,0] = 1; cc[i,0] = 0, với i:=1..m.
-cc[i,j] = cc[i,i], nếu i < j
-cc[i,j] = cc[i,j-1]+cc[i-j,j], nếu i ≥ j.
Từ đó ta suy ra quy trình điền trị vào bảng cc như sau:
Khởi trị: Khởi trị cột đầu tiên (tức cột 0)toàn 0. Riêng cc[0,0]:=1.
Điền bảng: Lần lượt điền theo từngcột j:=1..n. Tại mỗi cột j ta đặt
-cc[i,j]:=cc[i,i] với i:=0..j-1 < j và
-cc[i,j]:=cc[i,j-1]+cc[i-j,j] với i:=j..m ≥ j.
Nhận kết quả: Sau khi điền bảng, giátrị cc[m,n] chính là kết quả cần tìm.
{PHUONG AN 2: dung mang 2 chieu cc}
function Chia2(m,n: integer):longint;
var i,j: integer;
begin
cc[0,0]:=1;
{Chia 1..vat cho 0 nguoi}
for i:=1 to m do cc[i,0]:=0;
for j:=1 to n do
begin
for i:=0 to j-1 do cc[i,j]:=cc[i,j-1];
for i:=j to m do cc[i,j]:=cc[i,j-1]+cc[i-j,j];
end;
Chia2:=cc[m,n];
end;
Làm tốt lần 2: Dùng mảng 2 chiều chúng tachỉ có thể tính toán được với dữ liệu nhỏ, cỡ
trên dưới 100. Bước cải tiến sauđây khá quan trọng: chúng ta dùng mảng một chiều. Quan
sát kỹ quy trình gán trịcho mảng 2 chiều theo từng cột chúng ta dễ phát hiện ra rằng cột thứ
j có thểđược tính toán từ cột thứ j-1. Nếu gọi c là mảng một chiều sẽ dùng, ta cho sốhọc
sinh tăng dần bằng cách lần lượt tính j bước, với j:=1..n. Tại bước thứ j,c[i] chính là số
cách chia i phần thưởng cho j học sinh. Như vậy, tại bước thứj ta có:
-c[i] mới = c[i] cũ, nếu i < j. Từ đây suy ra đoạn c[0..j-1] được bảo lưu.
-c[i] mới = c[i] cũ + c[i-j] mới, nếu i ≥ j.
Biểu thức thứ hai cho biết khi cập nhật mảng c từ bướcthứ j-1 qua bước thứ j ta phải tính
từ trên xuống, nghĩa là tính dần theo chiềutăng của i:=j..m. Mảng c được khởi trị ở bước
(j=0) như sau:
-c[0] = 1; c[i] = 0, với i:=1..m.
với ý nghĩa là, nếu có 0 học sinh thì chia 0 phần thưởngcho 0 học sinh sẽ được quy định là
1, nếu số phần thưởng m khác 0 thì chia mphần thưởng cho 0 học sinh sẽ được 0 phương
án.
Ta có phương án thứ ba, dùng một mảng một chiều c nhưsau:
{PHUONG AN 3: dung mang 1 chieu c}
function Chia1(m,n: integer):longint;
var i,j: integer;
begin
c[0]:=1;
{Chia 1..vat cho 0 nguoi}
for i:=1 to m do c[i]:=0;
for j:=1 to n do
for i:=j to m do c[i]:=c[i]+c[i-j];
Chia1:=c[m];
end;
Để so sánh các phương án bạn đặt một bộ đếm nhịp của máynhư sau:
var nhip: longint absolute $0000:$046c;
{xac dinh nhip thoi gian}
t: longint;{ghi nhan nhip}
Ngoài ra bạn khai báo hai biến n và m dùng chung cho cácthủ tục:
var m,n: integer;{so phan thuong va so hoc sinh}
Sau đó bạn tạo cho mỗi phương án một test như sau:
procedure Test1;
begin
write('Test1: De quy ');
t:=Nhip;
write(' Ket qua: ',Chiăm,n));
