Tóm tắt¶

Điểm mấu chốt¶

Quy hoạch động phân tách các bài toán và tránh tính toán thừa bằng cách lưu trữ lời giải của các bài toán con, từ đó cải thiện đáng kể hiệu quả tính toán.
Nếu không xem xét giới hạn thời gian, tất cả các bài toán quy hoạch động đều có thể được giải quyết bằng quay lui (tìm kiếm vét cạn), nhưng cây đệ quy chứa một lượng lớn các bài toán con trùng lặp, dẫn đến hiệu quả cực kỳ thấp. Bằng cách đưa vào mảng ghi nhớ, chúng ta có thể lưu trữ lời giải của tất cả các bài toán con đã được tính toán, đảm bảo rằng các bài toán con trùng lặp chỉ được tính toán một lần.
Đệ quy có nhớ là giải pháp đệ quy từ trên xuống, trong khi quy hoạch động tương ứng là giải pháp lặp từ dưới lên, tương tự như việc "điền vào bảng". Vì trạng thái hiện tại chỉ phụ thuộc vào một số trạng thái cục bộ nhất định, chúng ta có thể loại bỏ một chiều của bảng \(dp\) để giảm độ phức tạp không gian.
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 các thuộc tính khác nhau trong chia để trị, quy hoạch động và quay lui.
Các bài toán quy hoạch động có ba đặc trưng lớn: bài toán con trùng lặp, cấu trúc con tối ưu và tính không sau ảnh hưởng.
Nếu lời giải tối ưu của bài toán gốc có thể được xây dựng từ lời giải tối ưu của các bài toán con, thì nó có cấu trúc con tối ưu.
Tính không sau ảnh hưởng có nghĩa là đối với một trạng thái cho trước, sự phát triển trong tương lai của nó chỉ liên quan đến trạng thái đó và không liên quan gì đến tất cả các trạng thái trong quá khứ. Nhiều bài toán tối ưu hóa tổ hợp không thỏa mãn thuộc tính này và không thể giải quyết hiệu quả bằng quy hoạch động.

Bài toán Balo

Bài toán balo là một trong những bài toán quy hoạch động điển hình nhất, với các biến thể như balo 0-1, balo vô hạn và balo bội.
Định nghĩa trạng thái cho balo 0-1 là giá trị lớn nhất có thể đạt được khi chọn từ \(i\) đồ vật đầu tiên với sức chứa balo là \(c\). Dựa trên hai quyết định: không bỏ đồ vật vào balo và bỏ vào balo, cấu trúc con tối ưu có thể được xác định và phương trình chuyển trạng thái được xây dựng. Trong tối ưu hóa không gian, vì mỗi trạng thái phụ thuộc vào trạng thái ngay phía trên và phía trên bên trái nó, danh sách cần được duyệt theo thứ tự ngược để tránh ghi đè lên trạng thái phía trên bên trái.
Bài toán balo vô hạn không có giới hạn về số lượng lựa chọn cho mỗi loại đồ vật, vì vậy chuyển trạng thái khi chọn bỏ đồ vật vào balo sẽ khác với bài toán balo 0-1. Vì trạng thái phụ thuộc vào trạng thái ngay phía trên và ngay bên trái nó, việc tối ưu hóa không gian nên sử dụng duyệt xuôi.
Bài toán đổi tiền xu là một biến thể của bài toán balo vô hạn. Nó thay đổi từ việc tìm kiếm giá trị "lớn nhất" sang tìm kiếm số lượng tiền xu "ít nhất", do đó hàm \(\max()\) trong phương trình chuyển trạng thái được đổi thành \(\min()\). Nó thay đổi từ việc tìm kiếm kết quả "không vượt quá" sức chứa balo sang tìm kiếm kết quả "chính xác" tạo thành số tiền mục tiêu, vì vậy số \(amt + 1\) được sử dụng để biểu diễn lời giải vô hiệu "không thể tạo thành số tiền mục tiêu".
Bài toán đổi tiền xu II thay đổi từ việc tìm kiếm "số lượng đồng tiền tối thiểu" sang tìm kiếm "số cách kết hợp tiền xu", do đó phương trình chuyển trạng thái cũng thay đổi tương ứng từ \(\min()\) sang phép toán tổng cộng.

Bài toán Khoảng cách Chỉnh sửa

Khoảng cách chỉnh sửa (khoảng cách Levenshtein) được sử dụng để đo lường mức độ tương đồng giữa hai chuỗi ký tự, được định nghĩa là số bước chỉnh sửa tối thiểu từ chuỗi này sang chuỗi kia, với các thao tác chỉnh sửa bao gồm chèn, xóa và thay thế.
Định nghĩa trạng thái cho bài toán khoảng cách chỉnh sửa là số bước chỉnh sửa tối thiểu cần thiết để biến đổi \(i\) ký tự đầu tiên của \(s\) thành \(j\) ký tự đầu tiên của \(t\). Khi \(s[i] \ne t[j]\), có ba quyết định: chèn, xóa, thay thế, mỗi quyết định có các bài toán con còn lại tương ứng. Từ đây, cấu trúc con tối ưu có thể được xác định và phương trình chuyển trạng thái được xây dựng. Khi \(s[i] = t[j]\), không cần chỉnh sửa cho ký tự hiện tại.
Trong khoảng cách chỉnh sửa, trạng thái phụ thuộc vào trạng thái ngay phía trên, ngay bên trái và phía trên bên trái, do đó sau khi tối ưu hóa không gian, cả duyệt xuôi và duyệt ngược đều không thể thực hiện chuyển trạng thái một cách chính xác. Vì lý do này, chúng ta sử dụng một biến để lưu trữ tạm thời trạng thái phía trên bên trái, qua đó chuyển đổi sang một tình huống tương đương với bài toán balo vô hạn, cho phép duyệt xuôi sau khi tối ưu hóa không gian.