Phương pháp giải quyết bài toán Quy hoạch động¶
Hai phần trước đã giới thiệu các đặc trưng chính của bài toán quy hoạch động. Tiếp theo, hãy cùng khám phá hai vấn đề thực tế hơn.
- Làm thế nào để xác định một bài toán có phải là bài toán quy hoạch động hay không?
- Quy trình hoàn chỉnh để giải quyết một bài toán quy hoạch động là gì, và chúng ta nên bắt đầu từ đâu?
Nhận biết bài toán¶
Nói một cách tổng quát, nếu một bài toán chứa các bài toán con trùng lặp, cấu trúc con tối ưu và thỏa mãn tính không sau ảnh hưởng, thì nó thường phù hợp để giải quyết bằng quy hoạch động. Tuy nhiên, rất khó để trích xuất trực tiếp các đặc trưng này từ mô tả bài toán. Do đó, chúng ta thường nới lỏng các điều kiện và trước tiên quan sát xem bài toán có phù hợp để giải bằng quay lui (tìm kiếm vét cạn) hay không.
Các bài toán phù hợp để giải bằng quay lui thường thỏa mãn mô hình cây quyết định (decision tree model), nghĩa là bài toán có thể được mô tả bằng cấu trúc cây, trong đó mỗi nút đại diện cho một quyết định và mỗi đường đi đại diện cho một chuỗi các quyết định.
Nói cách khác, nếu một bài toán chứa khái niệm quyết định rõ ràng, và lời giải được tạo ra thông qua một chuỗi các quyết định, thì nó thỏa mãn mô hình cây quyết định và thường có thể giải quyết bằng quay lui.
Trên cơ sở này, các bài toán quy hoạch động cũng có một số dấu hiệu nhận biết tích cực.
- Bài toán chứa các mô tả như lớn nhất (nhỏ nhất) hoặc nhiều nhất (ít nhất), biểu thị tính tối ưu hóa.
- Trạng thái của bài toán có thể được biểu diễn bằng danh sách, ma trận đa chiều hoặc cây, và một trạng thái có hệ thức truy hồi với các trạng thái xung quanh nó.
Tương ứng, cũng có một số dấu hiệu nhận biết tiêu cực.
- Mục tiêu của bài toán là tìm tất cả các lời giải khả thi, thay vì tìm lời giải tối ưu.
- Mô tả bài toán có các đặc trưng rõ rệt của chỉnh hợp và tổ hợp (permutation and combination), yêu cầu trả về cụ thể nhiều lời giải khác nhau.
Nếu một bài toán thỏa mãn mô hình cây quyết định và có các dấu hiệu tích cực tương đối rõ ràng, chúng ta có thể giả định đó là một bài toán quy hoạch động và xác thực giả định đó trong quá trình giải quyết.
Các bước giải quyết bài toán¶
Quy trình giải quyết bài toán quy hoạch động thay đổi tùy thuộc vào tính chất và độ khó của bài toán, nhưng nhìn chung tuân theo các bước sau: mô tả các quyết định, định nghĩa trạng thái, thiết lập bảng \(dp\), rút ra phương trình chuyển trạng thái, xác định các điều kiện biên, v.v.
Để minh họa các bước giải quyết bài toán một cách trực quan sinh động hơn, chúng ta sử dụng một bài toán kinh điển làm ví dụ: tổng đường đi nhỏ nhất (minimum path sum).
Question
Cho một lưới hai chiều kích thước \(n \times m\) có tên là grid, trong đó mỗi ô chứa một số nguyên không âm đại diện cho chi phí của nó. Một robot xuất phát từ ô trên cùng bên trái và chỉ có thể di chuyển xuống dưới hoặc sang phải ở mỗi bước cho đến khi đến ô dưới cùng bên phải. Trả về tổng đường đi nhỏ nhất từ ô trên cùng bên trái đến ô dưới cùng bên phải.
Hình dưới đây cho thấy một ví dụ trong đó tổng đường đi nhỏ nhất cho lưới đã cho là \(13\).
Bước 1: Suy nghĩ về quyết định trong từng vòng, định nghĩa trạng thái, và từ đó có được bảng \(dp\)
Quyết định trong mỗi vòng của bài toán này là di chuyển một bước xuống dưới hoặc sang phải từ ô hiện tại. Gọi chỉ số dòng và cột của ô hiện tại là \([i, j]\). Sau khi di chuyển xuống dưới hoặc sang phải, các chỉ số sẽ trở thành \([i+1, j]\) hoặc \([i, j+1]\). Do đó, trạng thái nên bao gồm hai biến là chỉ số dòng và chỉ số cột, ký hiệu là \([i, j]\).
Trạng thái \([i, j]\) tương ứng với bài toán con: tổng đường đi nhỏ nhất từ điểm xuất phát \([0, 0]\) đến \([i, j]\), được ký hiệu là \(dp[i, j]\).
Từ đây, chúng ta có được ma trận \(dp\) hai chiều như hình dưới đây, có kích thước tương tự ma trận đầu vào grid.
Note
Quy trình quy hoạch động và quay lui có thể được mô tả như một chuỗi các quyết định, và trạng thái bao gồm tất cả các biến quyết định. Trạng thái nên chứa tất cả các biến mô tả tiến trình giải quyết bài toán, và phải chứa đủ thông tin để suy ra trạng thái tiếp theo.
Mỗi trạng thái tương ứng với một bài toán con, và chúng ta định nghĩa một bảng \(dp\) để lưu trữ lời giải của tất cả các bài toán con. Mỗi biến độc lập của trạng thái là một chiều của bảng \(dp\). Về bản chất, bảng \(dp\) là một ánh xạ giữa các trạng thái và lời giải của các bài toán con.
Bước 2: Xác định cấu trúc con tối ưu, từ đó rút ra phương trình chuyển trạng thái
Đối với trạng thái \([i, j]\), nó chỉ có thể chuyển đổi từ ô phía trên \([i-1, j]\) hoặc ô bên trái \([i, j-1]\). Do đó, cấu trúc con tối ưu là: tổng đường đi nhỏ nhất để đạt được \([i, j]\) được xác định bởi giá trị nhỏ hơn trong số các tổng đường đi nhỏ nhất của \([i, j-1]\) và \([i-1, j]\).
Dựa trên phân tích trên, phương trình chuyển trạng thái được rút ra như hình bên dưới:
Note
Dựa trên bảng \(dp\) đã được định nghĩa, hãy suy nghĩ về mối quan hệ giữa bài toán gốc và các bài toán con, đồng thời tìm phương pháp xây dựng lời giải tối ưu của bài toán gốc từ lời giải tối ưu của các bài toán con, đó chính là cấu trúc con tối ưu.
Sau khi xác định được cấu trúc con tối ưu, chúng ta có thể sử dụng nó để xây dựng phương trình chuyển trạng thái.
Bước 3: Xác định điều kiện biên và thứ tự chuyển trạng thái
Trong bài toán này, các trạng thái ở dòng đầu tiên chỉ có thể bắt nguồn từ trạng thái bên trái chúng, và các trạng thái ở cột đầu tiên chỉ có thể bắt nguồn từ trạng thái phía trên chúng. Do đó, dòng đầu tiên \(i = 0\) và cột đầu tiên \(j = 0\) là các điều kiện biên (boundary condition).
Như hình dưới đây, vì mỗi ô chuyển đổi từ ô bên trái và ô phía trên nó, chúng ta sử dụng các vòng lặp để duyệt qua ma trận, với vòng lặp ngoài duyệt theo dòng và vòng lặp trong duyệt theo cột.
Note
Các điều kiện biên trong quy hoạch động được sử dụng để khởi tạo bảng \(dp\), trong khi ở các bài toán tìm kiếm chúng được sử dụng để cắt nhánh.
Cốt lõi của thứ tự chuyển trạng thái (state transition order) là đảm bảo rằng khi tính toán lời giải cho bài toán hiện tại, tất cả các bài toán con nhỏ hơn mà nó phụ thuộc vào đều đã được tính toán chính xác trước đó.
Dựa trên phân tích trên, chúng ta có thể trực tiếp viết mã nguồn quy hoạch động. Tuy nhiên, sự phân tách bài toán con là hướng tiếp cận từ trên xuống, do đó việc triển khai theo thứ tự "tìm kiếm vét cạn \(\rightarrow\) đệ quy có nhớ \(\rightarrow\) quy hoạch động" sẽ phù hợp hơn với thói quen tư duy.
Phương pháp 1: Tìm kiếm vét cạn¶
Bắt đầu từ trạng thái \([i, j]\), chúng ta liên tục phân tách nó thành các trạng thái nhỏ hơn \([i-1, j]\) và \([i, j-1]\). Hàm đệ quy bao gồm các yếu tố sau.
- Tham số đệ quy: trạng thái \([i, j]\).
- Giá trị trả về: tổng đường đi nhỏ nhất từ \([0, 0]\) đến \([i, j]\), tức là \(dp[i, j]\).
- Điều kiện dừng: khi \(i = 0\) và \(j = 0\), trả về chi phí
grid[0, 0]. - Cắt nhánh: khi \(i < 0\) hoặc \(j < 0\), chỉ số vượt quá biên, trả về chi phí \(+\infty\), biểu thị phương án không khả thi.
Mã nguồn triển khai như sau:
Hình dưới đây cho thấy cây đệ quy có gốc tại \(dp[2, 1]\), bao gồm một số bài toán con trùng lặp có số lượng sẽ tăng mạnh khi kích thước của lưới grid tăng lên.
Về bản chất, lý do xuất hiện các bài toán con trùng lặp là: có nhiều đường đi từ góc trên bên trái để đến được một ô nhất định.
Mỗi trạng thái có hai lựa chọn là đi xuống dưới và sang phải, do đó tổng số bước từ góc trên bên trái đến góc dưới bên phải là \(m + n - 2\), mang lại độ phức tạp thời gian trong trường hợp xấu nhất là \(O(2^{m + n})\), với \(n\) và \(m\) lần lượt là số dòng và số cột của lưới. Lưu ý rằng phép tính này chưa tính đến các tình huống gần biên lưới, nơi chỉ còn lại một lựa chọn khi chạm đến biên lưới, vì vậy số lượng đường đi thực tế sẽ ít hơn một chút.
Phương pháp 2: Đệ quy có nhớ¶
Chúng ta đưa vào một mảng ghi nhớ mem có cùng kích thước với lưới grid để ghi lại lời giải của các bài toán con và cắt nhánh các bài toán con trùng lặp:
Như hình dưới đây, sau khi đưa vào đệ quy có nhớ, tất cả lời giải của các bài toán con chỉ cần tính toán một lần, do đó độ phức tạp thời gian phụ thuộc vào tổng số trạng thái, chính là kích thước lưới \(O(nm)\).
Phương pháp 3: Quy hoạch động¶
Triển khai lời giải quy hoạch động dựa trên vòng lặp, như mã nguồn dưới đây:
Hình dưới đây biểu diễn quy trình chuyển trạng thái cho tổng đường đi nhỏ nhất, duyệt qua toàn bộ lưới, do đó độ phức tạp thời gian là \(O(nm)\).
Mảng dp có kích thước \(n \times m\), do đó độ phức tạp không gian là \(O(nm)\).
Tối ưu hóa không gian¶
Vì mỗi ô chỉ liên quan đến ô bên trái nó và ô phía trên nó, chúng ta có thể sử dụng một mảng một dòng để triển khai bảng \(dp\).
Lưu ý rằng vì mảng dp chỉ có thể đại diện cho trạng thái của một dòng, chúng ta không thể khởi tạo trước trạng thái cột đầu tiên, mà thay vào đó sẽ cập nhật nó khi duyệt qua từng dòng: