Quy hoạch động là một trong những phương pháp quan trọng trong khoa học máy tính, giúp giải quyết các bài toán tối ưu mà không cần phải tính lại kết quả cho những phần bài toán đã được giải quyết. Phương pháp này rất hữu ích trong việc giảm độ phức tạp tính toán và tiết kiệm thời gian. Trong bài viết này, hãy cùng LPTech tìm hiểu cách sử dụng quy hoạch động để giảm thời gian chạy các thuật toán trong bài viết sau!

Quy hoạch động là gì?

Quy hoạch động (Dynamic Programming - DP) là một phương pháp giải quyết các bài toán tối ưu bằng cách chia bài toán lớn thành các bài toán con nhỏ hơn, sau đó lưu trữ kết quả của từng bài toán con để tránh việc tính lại. Phương pháp này đặc biệt hiệu quả với các bài toán có tính chất ‘tối ưu con’ và ‘bài toán con gối nhau’, tức là các bài toán con có thể chia sẻ các kết quả tính toán giống nhau.

Quy hoạch động không chỉ giúp tối ưu hóa các bài toán tính toán, mà trong lập trình đặc biệt là thiết kế website có chức năng còn giúp giảm thiểu số lần tính toán lại, từ đó tiết kiệm thời gian và tài nguyên hệ thống.

Nguyên lý hoạt động của Dynamic Programming

Quy hoạch động (Dynamic Programming - DP) là phương pháp giải quyết các bài toán tối ưu bằng cách chia bài toán lớn thành nhiều bài toán con nhỏ hơn và sau đó giải quyết từng phần riêng biệt.

1. Chia bài toán thành các bài toán con

Trong quy hoạch động, bài toán ban đầu được phân chia thành các bài toán con nhỏ hơn, mỗi bài toán con này sẽ là một phần của bài toán lớn hơn. Các bài toán con này thường có sự trùng lặp, nghĩa là kết quả của chúng có thể được tái sử dụng trong quá trình giải quyết bài toán gốc.

2. Lưu trữ kết quả của các bài toán con

Để tránh việc tính toán lại nhiều lần các bài toán con giống nhau, kết quả của từng bài toán con sẽ được lưu vào một bảng nhớ, thường là một mảng hoặc ma trận. Việc này giúp giảm thiểu số lượng phép toán cần thực hiện.

3. Sử dụng lại kết quả đã lưu

Khi chương trình cần kết quả của một bài toán con nào đó, thay vì tính toán lại từ đầu, nó sẽ kiểm tra bảng lưu trữ để xem liệu kết quả của bài toán con đó đã được tính trước đó hay chưa. Nếu đã có kết quả, nó sẽ sử dụng lại thay vì thực hiện phép tính mới, giúp tiết kiệm thời gian và tài nguyên tính toán.

Các bước thực hiện quy hoạch động

Để áp dụng quy hoạch động, bạn cần thực hiện các bước sau:

• Bước 1: Xác định bài toán tối ưu: Trước tiên, cần xác định bài toán cần giải quyết có tính chất tối ưu con hay không, tức là bài toán có thể chia nhỏ thành các bài toán con độc lập.
• Bước 2: Định nghĩa các bài toán con: Sau khi nhận diện được bài toán con, bạn cần chỉ ra cách giải quyết từng bài toán con đó. Đây là bước quan trọng để xác định được hướng giải quyết tối ưu.
• Bước3: Xác định công thức quy hoạch động: Đây là bước quan trọng để kết nối các bài toán con và bài toán gốc. Công thức này giúp tính toán kết quả của bài toán gốc từ các bài toán con đã giải quyết.
• Bước 4: Lưu trữ kết quả: Để tránh tính toán lại các bài toán con, bạn cần lưu trữ kết quả vào một bảng nhớ (memoization). Bảng này giúp truy xuất nhanh kết quả mỗi khi cần.

Giải quyết bài toán: Cuối cùng, bạn áp dụng công thức và các kết quả đã lưu trữ để giải quyết bài toán gốc.

Các trường hợp sử dụng quy hoạch động

Quy hoạch động có thể được áp dụng trong nhiều trường hợp khác nhau, nhất là trong các bài toán tối ưu hóa, tối thiểu hóa hay tối đa hóa. Dưới đây là một số trường hợp tiêu biểu:

Bài toán con gối nhau

Quy hoạch động cũng phân chia bài toán lớn thành các bài toán con nhỏ hơn. Tuy nhiên, điểm khác biệt là trong quy hoạch động, các bài toán con này thường xuyên được gọi đi gọi lại. Chính vì vậy, thay vì tính toán lại mỗi khi gặp bài toán con, quy hoạch động sẽ lưu trữ kết quả của các bài toán con đã giải quyết. Khi một bài toán con được yêu cầu, kết quả đã lưu sẽ được sử dụng ngay lập tức, giúp tiết kiệm thời gian tính toán.

Quy hoạch động chỉ thực sự hiệu quả khi các bài toán con có sự lặp lại (gối nhau). Nếu các bài toán con không tái sử dụng kết quả, quy hoạch động sẽ không mang lại hiệu quả, hoặc thậm chí không thể áp dụng. Chẳng hạn, trong thuật toán tìm kiếm nhị phân, mỗi bài toán con chỉ được giải quyết một lần mà không có sự tái gọi lại, vì vậy quy hoạch động không có tác dụng gì.
Một ví dụ điển hình về bài toán con gối nhau là bài toán tính dãy Fibonacci. Với công thức tính dãy Fibonacci như sau:

def fib(n):

if n <= 1:

return n

return fib(n - 1) + fib(n - 2)

Cách tính này sẽ dẫn đến việc tính toán lại rất nhiều bài toán con, điển hình là giá trị fib(0) và fib(1) sẽ bị tính đi tính lại nhiều lần. Quy hoạch động có thể cải thiện vấn đề này bằng cách lưu trữ kết quả của các bài toán con trước khi tính toán các bài toán con lớn hơn. Nhờ đó, mỗi bài toán con chỉ cần được tính một lần, giúp giảm đáng kể thời gian tính toán tổng thể.

Cấu trúc con tối ưu

Cấu trúc con tối ưu là một đặc điểm quan trọng của bài toán, trong đó lời giải cho bài toán lớn có thể được xây dựng từ những lời giải của các bài toán con nhỏ hơn.

Để dễ hiểu hơn, hãy xem ví dụ về bài toán tìm đường đi ngắn nhất trong đồ thị. Nếu có một điểm x nằm trên đường đi ngắn nhất giữa hai điểm u và v, thì đường đi ngắn nhất từ u đến v có thể được chia thành hai phần: đường đi ngắn nhất từ u đến x và từ x đến v. Một số thuật toán tìm đường đi ngắn nhất, ví dụ như thuật toán Dijkstra, sử dụng tính chất này và áp dụng quy hoạch động để tìm ra kết quả tối ưu.

Ví dụ về đồ thị dưới đây thể hiện cho bài toán không có cấu trúc con tối ưu:

Trong bài toán tìm đường đi dài nhất giữa hai điểm q và t, có thể có nhiều cách đi như q -> r -> t hoặc q -> s -> t. Tuy nhiên, khác với bài toán tìm đường đi ngắn nhất, bài toán tìm đường đi dài nhất không thể đơn giản xem như một sự kết hợp của các đoạn đường đi con.

Cụ thể, đường đi dài nhất từ q đến t qua r (q -> r -> t) không phải là sự kết hợp của đường đi dài nhất từ q đến r và từ r đến t. Thực tế, đường đi dài nhất từ q đến r có thể là q -> s -> t -> r, trong khi đường đi dài nhất từ r đến t lại có thể là r -> q -> s -> t. Chính vì vậy, bài toán tìm đường đi dài nhất không có tính chất cấu trúc con tối ưu và không thể áp dụng quy hoạch động để giải quyết.

Lợi ích và hạn chế của quy hoạch động

Quy hoạch động có nhiều lợi ích và hạn chế cụ thể như sau:

Lợi ích của quy hoạch động

Dynamic Programming (DP) mang lại nhiều lợi ích nổi bật trong việc giải quyết các bài toán tối ưu, bao gồm:

Giảm thiểu thời gian tính toán

Phương pháp này giúp giảm đáng kể số lượng phép toán cần thực hiện, đặc biệt hiệu quả khi xử lý các bài toán có tính chất lặp lại như bài toán dãy Fibonacci hay các bài toán tối ưu hóa.

Giải quyết các bài toán phức tạp

DP là công cụ mạnh mẽ để giải quyết nhiều bài toán tối ưu hóa và lập lịch phức tạp mà các phương pháp khác không thể xử lý hiệu quả. Ví dụ điển hình là các bài toán như ba lô (Knapsack), tìm chuỗi con chung dài nhất (LCS) hoặc các bài toán trên đồ thị.

Tránh tính toán thừa

Bằng cách lưu trữ kết quả của những bài toán con, DP giúp tránh tính toán lại các phần đã được giải quyết trước đó. Điều này giúp tiết kiệm tài nguyên và nâng cao hiệu suất tính toán, giảm thiểu các phép toán không cần thiết.

Đảm bảo độ chính xác

Phương pháp quy hoạch động đảm bảo rằng giải pháp tối ưu sẽ được tìm thấy nhờ vào việc xây dựng các bài toán con tối ưu.

Nhược điểm của Dynamic Programming

Tuy nhiên, bên cạnh các ưu điểm, quy hoạch động cũng có một số nhược điểm cần lưu ý:

Tốn nhiều bộ nhớ

DP yêu cầu phải lưu trữ kết quả của tất cả các bài toán con đã được giải quyết. Điều này có thể gây ra sự tiêu tốn lớn về bộ nhớ, đặc biệt khi bài toán có không gian trạng thái rộng lớn. Khi áp dụng DP cho các bài toán có quy mô lớn, vấn đề này có thể trở thành một yếu tố hạn chế đáng kể.

Khó triển khai

Việc hiểu và triển khai giải pháp DP đòi hỏi người lập trình phải nắm vững cấu trúc bài toán và cách chia nhỏ bài toán thành các bài toán con. Quá trình này có thể khá phức tạp và yêu cầu nhiều thời gian để thiết kế, thử nghiệm và debug.

Không phải lúc nào cũng khả thi

Quy hoạch động không phải là phương pháp phù hợp cho tất cả các bài toán. Chỉ những bài toán có tính chất tối ưu con (optimal substructure) và bài toán con gối nhau (overlapping subproblems) mới có thể áp dụng được phương pháp này. Nếu bài toán thiếu những đặc điểm này, DP sẽ không đem lại hiệu quả tối ưu.

Tiêu tốn thời gian cho việc lưu trữ và truy xuất dữ liệu

Mặc dù quy hoạch động giúp giảm thiểu thời gian tính toán nhưng việc lưu trữ và truy xuất các kết quả từ bộ nhớ cũng tiêu tốn một phần thời gian đáng kể. Điều này đặc biệt trở nên rõ rệt khi bảng lưu trữ có kích thước lớn.

Top 2 bài toán quy hoạch động kinh điển

Để bạn dễ hình dung hơn về quy hoạch động, hãy cùng LPTech tìm hiểu qua 2 bài toán kinh điển này nhé!

Bài toán 1: Bài toán với đồng xu

Một trong những ví dụ điển hình khi học về quy hoạch động là bài toán tìm số lượng đồng xu ít nhất có tổng khối lượng bằng một giá trị cho trước. Có thể có nhiều cách diễn đạt khác nhau, nhưng cốt lõi của bài toán như sau:

Giả sử chúng ta có n đồng xu với trọng lượng lần lượt là W1, W2, ..., Wn, và nhiệm vụ là tìm số lượng đồng xu nhỏ nhất sao cho tổng khối lượng của chúng bằng một giá trị S. Lưu ý rằng số lượng đồng xu là không giới hạn, nghĩa là có thể sử dụng mỗi đồng xu nhiều lần.

Để giải quyết bài toán này bằng quy hoạch động, chúng ta cần chia bài toán thành các bài toán con gối nhau. Cụ thể, mỗi bài toán con dp(P), với P ≤ S, sẽ tương ứng với việc tìm số đồng xu nhỏ nhất có tổng trọng lượng bằng P. Lời giải của dp(P) chính là số đồng xu tối thiểu cần thiết cho trọng lượng P.

Quy trình giải quyết bài toán bằng quy hoạch động bắt đầu từ bài toán con dp(0) và tiến dần đến các bài toán con lớn hơn, cho đến khi ta giải quyết được bài toán dp(S). Lúc này, dp(S) chính là kết quả của bài toán gốc. Một điều cần lưu ý trong quy hoạch động là, để giải quyết được bài toán con dp(P), ta cần phải giải quyết các bài toán con nhỏ hơn trước đó.

Giả sử chúng ta có một trọng lượng P cần đạt được từ các đồng xu có trọng lượng W1, W2, ..., Wn. Để có được khối lượng P, ta có thể chọn một đồng xu có trọng lượng U, cộng vào tổng khối lượng Q sao cho Q + U = P. Vì ta đã biết số đồng xu tối thiểu để đạt được Q (là dp(Q)), ta có thể tính ra số đồng xu tối thiểu cho dp(P) bằng cách thêm 1 đồng xu có trọng lượng U. Tất nhiên, có nhiều loại đồng xu với trọng lượng khác nhau, vì vậy ta sẽ cần phải giải quyết nhiều bài toán con để tính được dp(P). Cuối cùng, dp(P) sẽ là giá trị nhỏ nhất từ các bài toán con đã giải quyết.

Ví dụ cụ thể:

Giả sử chúng ta có n = 3, S = 11, và mảng trọng lượng đồng xu là W = [1, 3, 5]. Dưới đây là cách giải quyết từng bài toán con:

dp(0) = 0 (không cần đồng xu nào)

dp(1) = dp(0) + 1 = 1 (sử dụng 1 đồng xu trọng lượng 1)

dp(2) = dp(1) + 1 = 2 (sử dụng 2 đồng xu trọng lượng 1)

dp(3) = min(dp(2) + 1, dp(0) + 1) = 1 (sử dụng 1 đồng xu trọng lượng 3)

Và tiếp tục tính toán như vậy cho các giá trị tiếp theo cho đến dp(11), chính là kết quả chúng ta cần tìm.

Cài đặt giải thuật quy hoạch động

Trong thực tế, quy hoạch động thường được triển khai bằng cách lưu trữ các kết quả vào một mảng. Ví dụ, mảng dp[0..S] sẽ lưu kết quả của từng bài toán con. Tương tự, dp[P] sẽ lưu số lượng đồng xu ít nhất cần thiết để có được tổng khối lượng P. Cách tính toán các giá trị trong mảng dp sẽ được thực hiện thông qua vòng lặp, như sau:

n, S = map(int, input().split())

w = list(map(int, input().split()))

dp = [0] * (S + 1)

dp[0] = 0

for P in range(1, S + 1):

dp[P] = min(dp[P - x] for x in w if x <= P) + 1

print(dp)

print(dp[S])

Đầu vào:

n = 3, S = 11, w = [1, 3, 5]

Kết quả dp(11) = 3, nghĩa là số đồng xu ít nhất cần thiết để có tổng khối lượng bằng 11 là 3.

Bài toán 2: Bài toán xâu con chung dài nhất

Một ví dụ điển hình khác về quy hoạch động là bài toán tìm xâu con chung dài nhất giữa hai xâu ký tự. Bài toán này yêu cầu chúng ta xác định độ dài của xâu con chung dài nhất giữa hai xâu cho trước. Ví dụ, với hai xâu "quetzalcoatl" và "tezcatlipoca", xâu con chung dài nhất sẽ là "ezaloa" với độ dài là 6.

Để giải quyết bài toán này bằng quy hoạch động, ta cần chia bài toán thành các bài toán con nhỏ hơn. Cụ thể, bài toán con dp(i, j) đại diện cho việc tìm độ dài xâu con chung dài nhất giữa i ký tự đầu tiên của xâu thứ nhất và j ký tự đầu tiên của xâu thứ hai. Lời giải của bài toán lớn sẽ được xây dựng từ các bài toán con này theo cách tiếp cận từng bước.

Quy trình giải quyết bài toán

Trường hợp cơ bản: Nếu một trong hai xâu là rỗng, thì xâu con chung dài nhất sẽ có độ dài là 0. Do đó, ta có:

dp(0,j)=0v

dp(i,0)=0

Đây là điều kiện ban đầu, bởi vì nếu một xâu rỗng thì không thể có xâu con chung với xâu khác. Trường hợp một trong hai ký tự không trùng: Nếu ký tự cuối cùng của hai xâu không giống nhau, thì xâu con chung dài nhất sẽ không thay đổi khi ta bỏ qua một trong hai ký tự này. Lúc này, ta có công thức:

dp(i,j)=max(dp(i−1,j),dp(i,j−1))

Điều này có nghĩa là ta sẽ tìm độ dài xâu con chung dài nhất giữa hai xâu mà không xét đến ký tự cuối cùng của một trong hai xâu.

Trường hợp hai ký tự cuối cùng giống nhau: Nếu ký tự cuối cùng của cả hai xâu là giống nhau (tức là x1 == x2), thì ta có thể bao gồm ký tự này trong xâu con chung. Lúc này, độ dài của xâu con chung sẽ được tính bằng:

dp(i,j)=dp(i−1,j−1)+1

Điều này có nghĩa là xâu con chung dài nhất giữa hai xâu sẽ dài hơn một ký tự so với xâu con chung của các phần tử trước đó.

Qua ba trường hợp trên, ta sẽ tính toán dần dần và tìm ra độ dài xâu con chung dài nhất giữa hai xâu cho trước.

Cài đặt bài toán

Mảng dp sẽ được lưu trong một ma trận hai chiều, trong đó mỗi phần tử dp(i, j) lưu trữ độ dài xâu con chung dài nhất của xâu con với độ dài i và j từ hai xâu. Quy trình tính toán mảng dp diễn ra thông qua hai vòng lặp lồng nhau, bắt đầu từ các giá trị nhỏ nhất và dần dần mở rộng ra đến toàn bộ xâu.

Dưới đây là cài đặt giải thuật:

n1, n2 = map(int, input().split())

s1, s2 = input().split()

t = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

for i, x1 in enumerate(s1, 1):

for j, x2 in enumerate(s2, 1):

if x1 == x2:

t[i][j] = t[i - 1][j - 1] + 1

else:

t[i][j] = max(t[i][j - 1], t[i - 1][j])

print(t[-1][-1])

Quy hoạch động là phương pháp hiệu quả dùng cho các thuật toán trong khoa học máy tính, hiểu được những kiến thức cơ bản sẽ giúp bạn có những ứng dụng phù hợp vào công việc và đời sống. Cảm ơn bạn đã theo dõi bài viết cùng LPTech nhé!