Quy Hoạch Động Trạng Thái

  -  

Đây là một kĩ thuật khá phổ thông mà đa số các bạn đều biết cũng biết. Kĩ thuật thường được nhận dạng khi với các thông số cho trước trong đề ta có thể giải quyết bài toán bằng độ phức tạp cấp số nhân. Một ví dụ kinh điển là bài toán TSP – Travelling Salesman, bài toán này có thể được giải bằng quy hoạch động trạng thái với độ phức tạp

*
bằng cách gọi
*
" class="latex" /> là thời gian nhỏ nhất để tham các đỉnh được đánh dấu trong
*
và kết thúc tại đỉnh
*
. Ta sẽ duyệt mọi tập con có thể tạo từ
*
đỉnh ban đầu và đỉnh
*
nên độ phức tạp của thao tác này là
*
. Với mỗi tập và một đỉnh
*
ta lại cần duyệt các đỉnh
*
nên tổng độ phức tạp là
*
.

Với DP Bitmask, thông thường chúng ta cần duyệt từ

*
đến
*
tức là từ tập
*
đến tập
*
. Vấn đề đặt ra là làm sao biết bit thứ
*
trong một tập là
*
hay
*
. Ví dụ
*
đại diện cho các đỉnh
*
được đánh dấu.


Bạn đang xem: Quy hoạch động trạng thái


Xem thêm: Hướng Dẫn Chi Tiết Về Cơ Chế Của Lstm Là Gì ? Giải Thích Chi Tiết Về Mạng Long Short


Xem thêm: Mình Là Gì Của Nhau Đạo Ý Tưởng, Onlyc Bị Dân Mạng Cho Rằng Đạo Nhái Bigbang


Thực tế cách kiểm tra bit thứ
*
trong
*
có được đánh dấu hay không rất đơn giản đó là kiểm tra giá trị của biểu thức (1 >> j) & 1 khác
*
hay bằng
*
và còn nhiều cách khác nữa.

Bây giờ ta xét một bài tập cụ thể: Little Pony and Harmony Chest

Tóm tắt đề: Có thể mô hình ngắn gọn như sau: cho dãy

*
phần tử tìm dãy
*
sao cho:

*
*
*
*
*

Bài này có thể giải quyết bằng DP Bitmask như sau: Đầu tiên ta dễ dàng chứng minh được giá trị lớn nhất của

*
có thể đặt được là
*
. Nhận xét tiếp theo là
*
và chỉ có 17 số nguyên tố trong khoảng từ
*
đến
*
nên từ dữ kiện này ta có thể sử dụng phương pháp quy hoạch động trạng thái. Bởi vì không có phần tử nào của
*
có ước chung lớn nhất khác
*
nên điều kiện đề bài cũng tương đương không có hai số nào trong
*
có phần chung trong tập các ước lớn hơn
*
của nó, ví dụ:
*
có tập ước lớn hơn
*
*
,
*
có tập ước lớn hơn
*
*
vì hai tập này không có phần tử chung nên
*
*
nguyên tố cùng nhau. Gọi
*
" class="latex" /> là kết quả tốt nhất khi chọn
*
số đầu tiên với tập ước của
*
được đánh dấu trong
*
. Định nghĩa
*
là tập ước của
*
. Vì
*
nên ta có thể thử chọn mọi giá trị
*
và tối ưu hóa. Với
*
*
là phần bù của
*
– đánh dấu các số nguyên tố chưa được dùng trong
*
, vậy số thiếp theo có thể chọn được biểu bằng một trong những tập con của
*
, gọi
*
là số mới tạo từ
*
ta có công thức quy hoạch động:

*
= min(dp, dp + \mid a_{i} - b_{i} \mid)" class="latex" />

Chỉ cần như vậy là đủ để accepted bài này