Quy hoạch động

Ví dụ

Cho số tự nhiên n ≤ 100. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng của dãy các

số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là một cách.

(Lưu ý: n = 0 vẫn coi là có 1 cách phân tích thành tổng các số nguyên dương (0 là tổng của dãy rỗng))

Để giải bài toán này, trong chuyên mục trước ta đã dùng phương pháp liệt kê tất cả các cách phân tích và đếm số cấu hình. Bây giờ ta thử nghĩ xem, cócáchnàotínhngayrasốlượngcáccách phântíchmàkhôngcầnphảiliệtkêhaykhông?. Bởi vì khi số cách phân tích tương đối lớn, phương pháp liệt kê tỏ ra khá chậm. (n = 100 có 190569292 cách phân tích).

Nhận xét:

Nếu gọi F[m, v] là số cách phân tích số v thành tổng các số nguyên dương ≤ m. Khi đó: Các cách phân tích số v thành tổng các số nguyên dương ≤ m có thể chia làm hai loại:

• Loại 1: Không chứa số m trong phép phân tích, khi đó số cách phân tích loại này chính là số cách phân tích số v thành tổng các số nguyên dương < m, tức là số cách phân tích số v thành tổng các số nguyên dương ≤ m - 1 và bằng F[m - 1, v].
• Loại 2: Có chứa ít nhất một số m trong phép phân tích. Khi đó nếu trong các cách phân tích loại này ta bỏ đi số m đó thì ta sẽ được các cách phân tích số v - m thành tổng các số nguyên dương ≤ m (Lưu ý: điều này chỉ đúng khi không tính lặp lại các hoán vị của một cách). Có nghĩa là về mặt số lượng, số các cách phân tích loại này bằng F[m, v - m]

Trong trường hợp m > v thì rõ ràng chỉ có các cách phân tích loại 1, còn trong trường hợp m ≤ v thì sẽ có cả các cách phân tích loại 1 và loại 2. Vì thế:

• F[m, v] = F[m - 1, v] nếu m > v
• F[m, v] = F[m - 1, v] + F[m, v - m] nếu m ≤ v

Ta có công thức xây dựng F[m, v] từ F[m - 1, v] và F[m, v - m]. Công thức này có tên gọi là công thứctruyhồiđưa việc tính F[m, v] về việc tính các F[m', v'] với dữ liệu nhỏ hơn. Tất nhiên cuối

cùng ta sẽ quan tâm đến F[n, n]: Số các cách phân tích n thành tổng các số nguyên dương ≤ n.

Nhìn vào bảng F, ta thấy rằng F[m, v] được tính bằng tổng của:

Một phần tử ở hàng trên: F[m - 1, v] và một phần tử ở cùng hàng, bên trái: F[m, v - m].

Chính vì vậy để tính F[m, v] thì F[m - 1, v] và F[m, v - m] phải được tính trước. Suy ra thứ tự hợp lý để tính các phần tử trong bảng F sẽ phải là theo thứ tự từ trên xuống và trên mỗi hàng thì tính theo thứ tự từ trái qua phải.

Điều đó có nghĩa là ban đầu ta phải tính hàng 0 của bảng: F[0, v] = số dãy có các phần tử ≤ 0 mà tổng bằng v, theo quy ước ở đề bài thì F[0, 0] = 1 còn F[0, v] với mọi v > 0 đều là 0.

Vậy giải thuật dựng rất đơn giản: Khởi tạo dòng 0 của bảng F: F[0, 0] = 1 còn F[0, v] với mọi v > 0 đều bằng 0, sau đó dùng công thức truy hồi tính ra tất cả các phần tử của bảng F. Cuối cùng F[n, n] là số cách phân tích cần tìm

PROG01_1.PAS * Đếm số cách phân tích số n

program Analyse1; {Bài toán phân tích số}

const

max = 100;

var

F: array[0..max, 0..max] of LongInt;

n, m, v: Integer;

begin

Write('n = '); ReadLn(n);

FillChar(F[0], SizeOf(F[0]), 0); {Khởi tạo dòng 0 của bảng F toàn số 0}

F[0, 0] := 1; {Duy chỉ có F[0, 0] = 1}

for m := 1 to n do {Dùng công thức tính các dòng theo thứ tự từ trên xuống dưới}

for v := 0 to n do {Các phần tử trên một dòng thì tính theo thứ tự từ trái qua phải}

if v < m then F[m, v] := F[m - 1, v]

else F[m, v] := F[m - 1, v] + F[m, v - m]; WriteLn(F[n, n], ' Analyses');{Cuối cùng F[n, n] là số cách phân tích}

end.

Cải tiến thứ nhất

Cách làm trên có thể tóm tắt lại như sau: Khởi tạo dòng 0 của bảng, sau đó dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2 v.v... tới khi tính được hết dòng n. Có thể nhận thấy rằng khi đã tính xong dòng thứ k thì việc lưu trữ các dòng từ dòng 0 tới dòng k - 1 là không cần thiết bởi vì việc tính dòng k+ 1 chỉ phụ thuộc các giá trị lưu trữ trên dòng k. Vậy ta có thể dùng hai mảng một chiều: Mảng Current lưu dòng hiện thời đang xét của bảng và mảng Next lưu dòng kế tiếp, đầu tiên mảng Current được gán các giá trị tương ứng trên dòng 0. Sau đó dùng mảng Current tính mảng Next, mảng Next sau khi tính sẽ mang các giá trị tương ứng trên dòng 1. Rồi lại gán mảng Current := Next và tiếp tục dùng mảng Current tính mảng Next, mảng Next sẽ gồm các giá trị tương ứng trên dòng 2 v.v... Vậy ta có cài đặt cải tiến sau:

PROG01_2.PAS * Đếm số cách phân tích số n

program Analyse2;

const

max = 100;

var

Current, Next: array[0..max] of LongInt;

n, m, v: Integer;

begin

Write('n = '); ReadLn(n); FillChar(Current, SizeOf(Current), 0);

Current[0] := 1; {Khởi tạo mảng Current tương ứng với dòng 0 của bảng F}

for m := 1 to n do

begin {Dùng dòng hiện thời Current tính dòng kế tiếp Next → size 12{ rightarrow } {} Dùng dòng m - 1 tính dòng m của bảng F}

for v := 0 to n do

if v < m then Next[v] := Current[v]

else Next[v] := Current[v] + Next[v - m];

Current := Next; {Gán Current := Next tức là Current bây giờ lại lưu các phần tử trên dòng m của bảng F}

end;

WriteLn(Current[n], ' Analyses');

end.

Cách làm trên đã tiết kiệm được khá nhiều không gian lưu trữ, nhưng nó hơi chậm hơn phương

pháp đầu tiên vì phép gán mảng (Current := Next). Có thể cải tiến thêm cách làm này như sau:

PROG01_3.PAS * Đếm số cách phân tích số n

program Analyse3;

const

max = 100;

var

B: array[1..2, 0..max] of LongInt;{Bảng B chỉ gồm 2 dòng thay cho 2 dòng liên tiếp của bảng phương án}

n, m, v, x, y: Integer;

begin

Write('n = '); ReadLn(n);

{Trước hết, dòng 1 của bảng B tương ứng với dòng 0 của bảng phương án F, được điền cơ sở quy hoạch động}

FillChar(B[1], SizeOf(B[1]), 0); B[1][0] := 1;

x := 1; {Dòng B[x] đóng vai trò là dòng hiện thời trong bảng phương án}

y := 2; {Dòng B[y] đóng vai trò là dòng kế tiếp trong bảng phương án}

for m := 1 to n do begin

{Dùng dòng x tính dòng y → size 12{ rightarrow } {} Dùng dòng hiện thời trong bảng phương án để tính dòng kế tiếp}

for v := 0 to n do

if v < m then B[y][v] := B[x][v]

else B[y][v] := B[x][v] + B[y][v - m];

x := 3 - x; y := 3 - y; {Đảo giá trị x và y, tính xoay lại}

end;

WriteLn(B[x][n], ' Analyses');

end.

Cải tiến thứ hai

Ta vẫn còn cách tốt hơn nữa, tại mỗi bước, ta chỉ cần lưu lại một dòng của bảng F bằng một mảng 1 chiều, sau đó dùng mảng đó tính lại chính nó để sau khi tính, mảng một chiều sẽ lưu các giá trị của bảng F trên dòng kế tiếp.

PROG01_4.PAS * Đếm số cách phân tích số n

program Analyse4;

const

max = 100;

var

L: array[0..max] of LongInt; {Chỉ cần lưu 1 dòng}

n, m, v: Integer;

begin

Write('n = '); ReadLn(n); FillChar(L, SizeOf(L), 0);

L[0] := 1; {Khởi tạo mảng 1 chiều L lưu dòng 0 của bảng}

for m := 1 to n do {Dùng L tính lại chính nó}

for v := m to n do

L[v] := L[v] + L[v - m]; WriteLn(L[n], ' Analyses');

end.

Bài tập:

Bài toán quy hoạch

Bài toán quy hoạch là bài toán tối ưu :gồm có một hàm f gọi là hàm mục tiêu hay hàm đánh giá; các hàm g1, g2, ..., gn cho giá trị logic gọi là hàm ràng buộc. Yêu cầu của bài toán là tìm một cấu hình x thoả mãn tất cả các ràng buộc g1, g2, ...gn: gi(x) = TRUE (∀i: 1 ≤ i ≤ n) và x là tốt nhất, theo nghĩa không tồn tại một cấu hình y nào khác thoả mãn các hàm ràng buộc mà f(y) tốt hơn f(x).

Các dạng bài toán quy hoạch rất phong phú và đa dạng, ứng dụng nhiều trong thực tế, nhưng cũng cần biết rằng, đa số các bài toán quy hoạch là không giải được, hoặc chưa giải được. Cho đến nay, người ta mới chỉ có thuật toán đơn hình giải bài toán quy hoạch tuyến tính lồi, và một vài thuật toán khác áp dụng cho các lớp bài toán cụ thể.

Phương pháp 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 các bài toán con. Đối với nhiều thuật toán đệ quy chúng ta đã tìm hiểu, 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 nó làm nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên lý này càng được thể hiện rõ: Khi không biết cần phải giải quyết những bài toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưutrữnhữnglờigiảihayđápsốcủa chúngvới mục đích sửdụnglạitheo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa và phép phân giải đệ quy và cũng là 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 rã 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 lại đưa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa.
• bắt đầu từ việcgiả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).

Ta xét một ví dụ đơn giản:

Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương pháp đó có thoả mãn những yêu cầu dưới đây hay 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ác bài toán con đó cho ta lời giải của bài toán lớn.
• Vì quy hoạch độ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 khái niệm:

• 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 nhỏ nhất 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 chúng gọi là bảngphươngán của quy hoạch động

Các bước cài đặt một chương trình sử dụng quy hoạch động: (nhớ kỹ)

• Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu 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 những bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của những bài toán lớn hơn và lưu chúng vào 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.

Một số bài toán quy hoạch động