KỸ THUẬT QUY HOẠCH ĐỘNG

Bài đăng này đã không được cập nhật trong 6 năm

1. Ý TƯỞNG VÀ NGUYÊN LÝ

1.1. Ví dụ về bài toán quy hoạch

Xét bài toán "Tìm cặp giá trị $\left( \small{x, y} \right)$ sao cho $x^{\smash{2}}$ + $y^{\smash{2}}$ ≤ 1 và $x +y$ đạt giá trị lớn nhất".

Trong mặt phẳng tọa độ, những điểm $x + y$ thỏa điều kiện $x^{\smash{2}}$ + $y^{\smash{2}}$ ≤ 1 là quỹ tích những điểm nằm trong hình tròn có tâm $O$ (gốc tọa độ) và bán kính bằng 1. Do đó nghiệm của bài toán bắt buộc nằm trong hình tròn $(O, 1)$ .

Những đường thẳng có phương tình $x$ $+$ $y$ = $K$ ( $K$ 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ố $K$ lớn nhất mà đường $x$ $+$ $y$ = $K$ vẫn có điểm chung với đường tròn $(O, 1)$ . Đường thẳng đó chính là tiếp tuyến của đường tròn và có phương trình là $x$ $+$ $y$ = $\sqrt{\smash[b]{2}}$ . Tiếp điểm là ( $\dfrac{\sqrt{\smash[b]{2}}}{2}$ ; $\dfrac{\sqrt{\smash[b]{2}}}{2}$ ) chính là nghiệm của bài toán đã cho.

Bài toán trên là bài toán tối ưu hay còn được gọi với một cái tên khác là bài toán quy hoạch. Trong bài toán này một hàm γ được gọi là hàm mục tiêu (hay hàm đánh giá) và các hàm cho giá trị luận lí $g_1$ , $g_2$ ,..., $g_n$ được gọi là các hàm ràng buộc.

Một nghiệm $x$ là tốt nhất theo nghĩa $x$ thỏa mãn điều kiện ràng buộc $g_i(x)$ = $TRUE (∀ 1 ≤ i ≤ n)$ và không tồn tại $x^{\smash{'}}$ nào khác thỏa mãn các hàm ràng buộc mà γ( $x^{\smash{'}}$ ) tốt hơn γ( $x$ ). Trong ví dụ trên hàm mục tiêu γ là γ$\left( \small{x, y} \right)$ = $x + y$ , hàm ràng buộc g là $x^2 + y^2 ≤ 1.$

Các bài toán quy hoạch rất phong phú, đa dạng và có nhiều ứng dụng trong thực tế nhưng có rất nhiều bài toán không giải được hoặc chưa tìm ra cách giải cho chúng.

1.2. Phương pháp quy hoạch động

Phương pháp quy hoạch động được nhà toán học Richard Bellman phát mình vào năm 1953. Ngành này đã được thành lập như một chủ đề về kỹ nghệ và phân tích hệ thống và đã được tổ chức IEEE thừa nhận.

Ý tưởng của nguyên lý tối ưu Bellman (được thừa nhận mà không chứng minh) là:

"Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu $A_0$ , với trạng thái $A$ trong quá trình đó phần quá trình kể từ trạng thái $A$ xem như trạng thái bắt đầu cũng là tối ưu" hay nói một cách khác "nếu một cấu hình đã tối ưu thì mọi cấu hình con của nó cũng là tối ưu".

Phương pháp quy hoạch động thường được dùng để giải các bài toán tối ưu có bản chất đệ quy, tức là 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 mà chúng ta tìm hiểu qua thì nguyên lí "Chia để trị" thường đóng vai trò chủ đạo trong thiết kế thuật toán nói chung và trong phương pháp quy hoạch động nói riêng. Ý tưởng của nguyên lý này là để giải quyết một bài toán lớn ta chia nó thành nhiều bài toán con và có 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 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 cũng như đá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. Đây là nội dung của phương pháp quy hoạch động và cũng chính là điểm khác nhau giữa những phương pháp quy hoạch động và phép phân giải đệ quy

Phép phân giải đệ quy theo hướng "top-down" tức là 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 quyết từng bài toán con đó. Việc phân rã 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 tiếp tục đi giải tiếp những bài toán con đó bất kể nó đã được giải hay chưa. Do đó thuật giải đệ quy có thể không tối ưu về mặt thời gian thực hiện và không gian nhớ
Quy hoạch theo hướng "bottom-up" tức là bắt đầu từ việc giải quyết tất cả các bài toán nhỏ (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 quyết đượ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 đó là tính giá trị của phần tử $F_n$ của dãy Fibonaci. Dãy Fibonaci ${F_n }$ được định nghĩa truy hồi như sau : $ F(n) = \begin{cases} 1 &\text{if } n=0 \land n = 1 \ F(n-1) + F(n-2) &\text{if } n ≥ 2 \end{cases} $

Chúng ta sẽ cùng thào luận dựa trên hai cách cài đặt chương trình khác nhau để tình giá trị $F_n$ . Giả sử rằng 100 ≥ n:

#cách 1
def fibonaci n
  n <= 1 ? n :  fibonaci( n - 1 ) + fibonaci( n - 2 ) 
end

#cách2
def fibonaci n
  f = []
  f[0] = f[1] = 1
  for i in 2...n
    f[i] = f[i-1] + f[i-2]
  end
  return f[n-1]
end

Quan sát hai cách trên chúng ta có nhận xét như sau:

Cách thứ nhất phân rã bài toán lớn thành các bài toán nhỏ hơn và đi giải tùng bài toán nhỏ đó nhờ đệ quy. theo cây đễ quy thì để tính được $F_4$ chương trình phải tính 1 lần $F_3$ , tính 2 lần $F_2$ , tính 3 lần $F_1$ tính 2 lần $F_0$ . Nhìn chung độ phức tạp của giải thuật này là $O(a^n)$ với $a$ xấp xỉ 1.6183
Không như cách giải thứ nhất cách thứ hai xử lí các bài toán nhỏ hơn và dựa vào đó làm cơ sở để giải các bài toán lớn hơn (bước này ta gọi là quy hoạch) và vì thế chương trình đảm bảo rằng mỗi giá trị Fibonaci chỉ phải tính một lần. Giải thuật này có độ phức tạp tuyến tính là $O(n)$ .

Hơn nữa khi quan sát kĩ cách 2 ta nhận thấy chỉ cần có nghiệm của "2 bài toán nhỏ hơn trước đó", tức là giá trị hiện tại$F[ i ]$ chỉ cần tính dựa vào $F[i-1]$ và $F[i-2]$ . Vì vậy chúng ta có thể cải tiến cách 2 bằng phương pháp chỉ cần lưu lại 2 giá trị liền trước giá trị cần tính mà không cần phải lưu lại toàn bộ.

Hơn nữa nhờ không cần dùng mảng để lưu toàn bộ các phần tử đã tính trước đó cách cải tiến này không cần giới hạn điều kiện 100 ≥ n nữa

def Fibonaci n
  lastF = f = k = 1
  while k < n-1 do
    f += lastF
    lastF = f - lastF
    k += 1
  end
  return f
end

Kết luận

Phương pháp quy hoạch động đã được áp dụng để giải hàng loạt bài toán thực tế trong các quá trình kỹ thuật công nghệ, tổ chức sản xuất, kế hoạch hóa kinh tế,...Ưu điểm của phương pháp này là chương trình thực thi nhanh do không tốn thì gian giải lại các bài toán con nhưng khuyết điểm là số lượng các bài toán con cần giải và lưu trữ kết quả rất lớn và việc kết hợp lời giải các bài toán con chưa chắc đã cho lời giải của bài toán đầu. Do đó có một số bài toán mà cách giải bằng quy hoạch động tỏ ra không thích hợp.

Nguồn: Sách "Kỹ thuật lập trình" của tác giả Trần Đan Thư - Đinh Bá Tiến - Nguyễn Thanh Phương - Trần Minh Triết -Đặng Bình Phương