Quy hoạch động là gì Update 04/2024

2.1. 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).

Bạn đang xem: Quy hoạch động là gì

Ví dụ:

Tìm (x, y) để

Hàm mục tiêu: x + y ® max

Hàm ràng buộc: x2 + y2 £ 1.

Xét trong mặt phẳng toạ độ, những cặp (x, y) thoả mãn x2 + y2 £ 1 là tọa độ của những điểm nằm trong hình tròn có tâm O là gốc toạ độ, bán kính 1. Vậy nghiệm của bài toán bắt buộc nằm trong hình tròn đó.

Những đường thẳng có phương trình: x + y = C (C là một hằng số) là đường thẳng vuông góc với đường phân giác góc phần tư thứ nhất. Ta phải tìm số C lớn nhất mà đường thẳng x + y = C vẫn có điểm chúng với đường tròn (O, 1). Đường thẳng đó là một tiếp tuyến của đường tròn:

tương ứng với nghiệm tối ưu của bài toán đã cho.

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ể.

2.2. 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ácbà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ư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 quát 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 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.

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).

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

Ví dụ: Dãy Fibonacci là dãy số nguyên dương được định nghĩa như sau:

F1 = F2 = 1;

“ i: 3 £ i: Fi = Fi-1 + Fi-2

Hãy tính F6

Xét hai cách cài đặt chương trình:

Cách 1

program Fibo1;

function F(i: Integer): Integer;begin if i else F := F(i – 1) + F(i – 2);end;begin WriteLn(F(6));end.

Cách 2

program Fibo2;varF: array of Integer; i: Integer;begin F := 1; F := 1; for i := 3 to 6 do F := F + F; WriteLn(F);end.

Trong cách 1, ta viết một hàm đệ quy F(i) để tính số Fibonacci thứ i. Chương trình chính gọi F(6), nó sẽ gọi tiếp F(5) và F(4) để tính … Quá trình tính toán có thể vẽ như cây dưới đây. Ta nhận thấy để tính F(6) nó phải tính 1 lần F(5), hai lần F(4), ba lần F(3), năm lần F(2), ba lần F(1).

Xem thêm: Eclectic Là Gì – Phong Cách Nội Thất Chiết Trung Eclectic

Hàm đệ quy tính số Fibonacci

Cách 2 thì không như vậy. Trước hết nó tính sẵn F và F, từ đó tính tiếp F, lại tính tiếpđược F, F, F. Đảm bảo rằng mỗi giá trị Fibonacci chỉ phải tính 1 lần.

(Cách 2 còn có thể cải tiến thêm nữa, chỉ cần dùng 3 giá trị tính lại lẫn nhau)

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 (hay phương trình truy toán) 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ảng phươ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ỹ)

B1. 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.

B2. 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.

B3. Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.

Xem thêm: đại Từ Quan Hệ Là Gì, Mệnh đề Quan Hệ Trong Tiếng Anh

Cho đến 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 hiệu quả bằng quy hoạch động. Tuy nhiên để biết được bài toán có thể giải bằng quy hoạch động hay không, ta có thể tự đặt câu hỏi: “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 ?” và ”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”.

Chuyên mục: Hỏi Đáp