Đặc trưng của bài toán Quy hoạch động¶
Trong phần trước, chúng ta đã học cách quy hoạch động giải quyết bài toán gốc bằng cách phân tách nó thành các bài toán con. Trên thực tế, phân tách bài toán con là một hướng tiếp cận thuật toán chung, với những điểm nhấn khác nhau trong chia để trị, quy hoạch động và quay lui.
- Thuật toán chia để trị (divide and conquer) phân chia bài toán gốc một cách đệ quy thành nhiều bài toán con độc lập cho đến khi đạt đến các bài toán con nhỏ nhất, và gộp lời giải của các bài toán con trong quá trình quay lui để cuối cùng thu được lời giải của bài toán gốc.
- Quy hoạch động cũng phân tách các bài toán một cách đệ quy, nhưng điểm khác biệt chính so với các thuật toán chia để trị là các bài toán con trong quy hoạch động phụ thuộc lẫn nhau, và nhiều bài toán con trùng lặp xuất hiện trong quá trình phân tách.
- Thuật toán quay lui liệt kê tất cả các lời giải khả thi thông qua thử sai, và tránh các nhánh tìm kiếm không cần thiết thông qua cắt nhánh. Lời giải cho bài toán gốc bao gồm một chuỗi các bước ra quyết định, và chúng ta có thể coi chuỗi con trước mỗi bước ra quyết định là một bài toán con.
Trên thực tế, quy hoạch động thường được sử dụng để giải quyết các bài toán tối ưu hóa (optimization problem), vốn không chỉ chứa các bài toán con trùng lặp mà còn có hai đặc trưng lớn khác: cấu trúc con tối ưu và tính không sau ảnh hưởng.
Cấu trúc con tối ưu¶
Chúng ta sửa đổi nhẹ bài toán leo cầu thang để làm cho nó phù hợp hơn nhằm thể hiện khái niệm cấu trúc con tối ưu.
Leo cầu thang với chi phí tối thiểu
Cho một cầu thang, mỗi lần bạn có thể leo \(1\) hoặc \(2\) bậc, và mỗi bậc thang được dán một nhãn số nguyên không âm đại diện cho chi phí khi bước lên bậc đó. Cho một mảng số nguyên không âm \(cost\), trong đó \(cost[i]\) đại diện cho chi phí của bậc thứ \(i\) và \(cost[0]\) là mặt đất (điểm xuất phát), hỏi chi phí tối thiểu cần thiết để leo lên đến đỉnh là bao nhiêu?
Như hình dưới đây, nếu chi phí của các bậc thứ \(1\), thứ \(2\) và thứ \(3\) lần lượt là \(1\), \(10\) và \(1\), thì việc leo từ mặt đất lên bậc thứ \(3\) đòi hỏi chi phí tối thiểu là \(2\).
Gọi \(dp[i]\) là chi phí tích lũy khi leo lên bậc thứ \(i\). Vì bậc thứ \(i\) chỉ có thể đi tới từ bậc thứ \(i-1\) hoặc bậc thứ \(i-2\), nên \(dp[i]\) chỉ có thể bằng \(dp[i-1] + cost[i]\) hoặc \(dp[i-2] + cost[i]\). Để giảm thiểu chi phí tối đa, chúng ta nên chọn giá trị nhỏ hơn trong hai giá trị đó:
Điều này dẫn chúng ta đến ý nghĩa của cấu trúc con tối ưu (optimal substructure): lời giải tối ưu của bài toán gốc được xây dựng từ lời giải tối ưu của các bài toán con.
Bài toán này rõ ràng có cấu trúc con tối ưu: chúng ta chọn phương án tốt hơn từ lời giải tối ưu của hai bài toán con \(dp[i-1]\) và \(dp[i-2]\), rồi dùng nó để xây dựng lời giải tối ưu cho bài toán gốc \(dp[i]\).
Vậy bài toán leo cầu thang ở phần trước có cấu trúc con tối ưu không? Mục tiêu của nó là tìm số lượng cách đi, vốn có vẻ là một bài toán đếm, nhưng nếu chúng ta thay đổi câu hỏi thành: "Tìm số lượng cách đi lớn nhất". Chúng ta ngạc nhiên phát hiện ra rằng mặc dù bài toán trước và sau khi sửa đổi là tương đương nhau, nhưng cấu trúc con tối ưu đã xuất hiện: số cách đi tối đa cho bậc thứ \(n\) bằng tổng số cách đi tối đa cho các bậc thứ \(n-1\) và bậc thứ \(n-2\). Do đó, việc diễn giải cấu trúc con tối ưu là khá linh hoạt và sẽ có ý nghĩa khác nhau trong các bài toán khác nhau.
Theo phương trình chuyển trạng thái và các trạng thái ban đầu \(dp[1] = cost[1]\) và \(dp[2] = cost[2]\), chúng ta có thể thu được mã nguồn quy hoạch động:
Hình dưới đây cho thấy quy trình quy hoạch động của mã nguồn trên.
Bài toán này cũng có thể được tối ưu hóa không gian, nén từ một chiều xuống không chiều (chỉ dùng các biến độc lập), giảm độ phức tạp không gian từ \(O(n)\) xuống \(O(1)\):
Tính không sau ảnh hưởng¶
Tính không sau ảnh hưởng (no aftereffects) là một trong những đặc trưng quan trọng cho phép quy hoạch động giải quyết bài toán một cách hiệu quả. Định nghĩa của nó là: khi cho trước một trạng thái nhất định, sự phát triển trong tương lai của nó chỉ liên quan đến trạng thái hiện tại và không liên quan gì đến tất cả các trạng thái trong quá khứ.
Lấy bài toán leo cầu thang làm ví dụ, cho trước trạng thái \(i\), nó sẽ phát triển thành các trạng thái \(i+1\) và \(i+2\), tương ứng với việc nhảy lên \(1\) bậc và \(2\) bậc. Khi thực hiện hai lựa chọn này, chúng ta không cần xem xét các trạng thái trước trạng thái \(i\), vì chúng không có ảnh hưởng gì đến tương lai của trạng thái \(i\).
Tuy nhiên, nếu chúng ta thêm một ràng buộc vào bài toán leo cầu thang, tình thế sẽ thay đổi.
Leo cầu thang kèm ràng buộc
Cho một cầu thang có \(n\) bậc, mỗi lần bạn có thể leo lên \(1\) hoặc \(2\) bậc, nhưng bạn không thể nhảy \(1\) bậc trong hai vòng liên tiếp. Hỏi có bao nhiêu cách để leo lên đến đỉnh?
Như hình dưới đây, chỉ có \(2\) cách khả thi để leo lên bậc thứ \(3\). Đường đi với ba lượt nhảy liên tiếp \(1\) bậc không thỏa mãn ràng buộc nên bị loại bỏ.
Trong bài toán này, nếu vòng trước đó là một bước nhảy \(1\) bậc, thì vòng tiếp theo bắt buộc phải nhảy \(2\) bậc. Điều này có nghĩa là lựa chọn tiếp theo không thể được xác định chỉ bằng trạng thái hiện tại (số bậc thang hiện tại), mà còn phụ thuộc vào trạng thái trước đó (số bậc thang ở vòng trước).
Không khó để nhận thấy rằng bài toán này không còn thỏa mãn tính không sau ảnh hưởng nữa, và phương trình chuyển trạng thái \(dp[i] = dp[i-1] + dp[i-2]\) cũng mất tác dụng, bởi vì \(dp[i-1]\) đại diện cho việc nhảy \(1\) bậc ở vòng này, nhưng nó lại bao gồm nhiều phương án mà "vòng trước đó cũng nhảy \(1\) bậc", vốn không thể được tính trực tiếp vào \(dp[i]\) để thỏa mãn ràng buộc.
Vì lý do này, chúng ta cần mở rộng định nghĩa trạng thái: trạng thái \([i, j]\) đại diện cho việc đang ở bậc thứ \(i\) với vòng trước đó đã nhảy \(j\) bậc, trong đó \(j \in \{1, 2\}\). Định nghĩa trạng thái này phân biệt hiệu quả việc vòng trước là nhảy \(1\) bậc hay \(2\) bậc, cho phép chúng ta xác định trạng thái hiện tại bắt nguồn từ đâu.
- Khi vòng trước nhảy \(1\) bậc, vòng trước đó nữa chỉ có thể chọn nhảy \(2\) bậc, tức là \(dp[i, 1]\) chỉ có thể chuyển đổi từ \(dp[i-1, 2]\).
- Khi vòng trước nhảy \(2\) bậc, vòng trước đó nữa có thể chọn nhảy \(1\) bậc hoặc \(2\) bậc, tức là \(dp[i, 2]\) có thể chuyển đổi từ \(dp[i-2, 1]\) hoặc \(dp[i-2, 2]\).
Như hình dưới đây, theo định nghĩa này, \(dp[i, j]\) đại diện cho số cách đi của trạng thái \([i, j]\). Khi đó phương trình chuyển trạng thái là:
Cuối cùng, trả về \(dp[n, 1] + dp[n, 2]\), trong đó tổng của cả hai đại diện cho tổng số cách leo lên bậc thứ \(n\):
Trong trường hợp trên, vì chúng ta chỉ cần xem xét thêm một trạng thái đi trước trực tiếp, nên chúng ta vẫn có thể làm cho bài toán thỏa mãn tính không sau ảnh hưởng bằng cách mở rộng định nghĩa trạng thái. Tuy nhiên, một số bài toán có "ảnh hưởng sau" cực kỳ nghiêm trọng.
Leo cầu thang sinh chướng ngại vật
Cho một cầu thang có \(n\) bậc, mỗi lần bạn có thể leo \(1\) hoặc \(2\) bậc. Bất cứ khi nào bạn đạt đến bậc thứ \(i\), hệ thống sẽ tự động đặt một chướng ngại vật ở bậc thứ \(2i\), và không có vòng tiếp theo nào được phép nhảy tới bậc thứ \(2i\) đó nữa. Ví dụ, nếu hai vòng đầu tiên nhảy đến các bậc thứ \(2\) và thứ \(3\), thì sau đó bạn không thể nhảy tới các bậc thứ \(4\) và thứ \(6\). Hỏi có bao nhiêu cách để leo lên đến đỉnh?
Trong bài toán này, bước nhảy tiếp theo phụ thuộc vào tất cả các trạng thái trong quá khứ, bởi vì mỗi bước nhảy đều tạo ra các chướng ngại vật ở các bậc cao hơn, ảnh hưởng đến các bước nhảy trong tương lai. Đối với những bài toán như vậy, quy hoạch động thường khó có thể giải quyết được.
Trên thực tế, nhiều bài toán tối ưu hóa tổ hợp phức tạp (chẳng hạn như bài toán người bán hàng du lịch (traveling salesman problem)) không thỏa mãn tính không sau ảnh hưởng. Đối với các bài toán như vậy, chúng ta thường sử dụng các phương pháp khác, chẳng hạn như tìm kiếm heuristics (heuristic search), thuật toán di truyền (genetic algorithm) và học tăng cường (reinforcement learning) để thu được các lời giải tối ưu cục bộ có thể sử dụng được trong thời gian giới hạn.