¶ Quy hoạch động trên cây
¶ Người viết:
- Phạm Công Minh, THPT chuyên Khoa học Tự Nhiên, ĐHQGHN.
¶ Reviewer:
- Lê Minh Hoàng, Đại học Khoa học Tự nhiên, ĐHQG-HCM.
- Nguyễn Minh Hiển, Trường Đại học Công nghệ, ĐHQGHN.
- Nguyễn Minh Nhật, THPT chuyên Khoa học Tự Nhiên, ĐHQGHN.
¶ Giới thiệu
Bài viết này sẽ đề cập một số bài toán quy hoạch động trên cây điển hình. Nếu chưa nắm vững về quy hoạch động, các bạn có thể đọc thêm về quy hoạch động ở VNOI - Quy hoạch động.
¶ Định nghĩa
Trước khi đi vào các bài toán, ta có một số các định nghĩa như sau:
- là trọng số của cạnh nối đỉnh và đỉnh
- là độ dài đường đi ngắn nhất từ đỉnh đến đỉnh .
- Trong một cây có đỉnh gốc là , đỉnh nằm trong cây con đỉnh nếu đường đi ngắn nhất từ đến đi qua .
- là tập hợp tất cả các đỉnh nằm trong cây con , trong đó có cả .
- là số đỉnh nằm trong cây con , hay .
¶ Bài toán 1
¶ Đề bài
Cho một cây gồm đỉnh , đỉnh thứ có một đồng xu giá trị . Bài toán yêu cầu chọn một tập con các đỉnh sao cho tập con không tồn tại 2 đỉnh được nối trực tiếp bởi một cạnh và tổng các đồng xu trên các đỉnh được chọn là lớn nhất.
¶ Lời giải
Bài toán này khá giống với một bài toán quy hoạch động trên mảng 1 chiều: cho một mảng , chọn một tập con các phần tử sao cho không có 2 phần tử nằm cạnh nhau đều được chọn và tổng các phần tử là lớn nhất.
Đối với bài toán trên mảng 1 chiều, ta định nghĩa trạng thái quy hoạch động là đáp án của bài toán nếu xét phần tử đầu .
Ta có 2 trường hợp là chọn hoặc không chọn . Vì vậy ta suy ra được công thức truy hồi
Đối với bài toán trên cây, thay vì xét một tiền tố, trạng thái quy hoạch động thường là đáp án nếu xét một cây con nào đó. Để định nghĩa cây con, cây cần có một gốc nào đó. Ta đặt gốc của cây là đỉnh và định nghĩa là đáp án của bài toán nếu chỉ xét cây con của đỉnh , như vậy, đáp án cuối cùng của bài toán là .
Tương tự như bài toán trên mảng 1 chiều, tại mỗi đỉnh ta cần quyết định có chọn hay không. Nếu không chọn đỉnh , ta có thể chọn các đỉnh con tùy ý. Nếu có chọn đỉnh , ta không được chọn đỉnh con nhưng vẫn có thể chọn các đỉnh cháu của
Gọi là con của . Như vậy ta có công thức truy hồi như sau:
Để chuyển trạng thái gọn gàng hơn, ta định nghĩa 2 trạng thái quy hoạch động mới:
- là đáp án bài toán nếu chỉ xét các đỉnh trong cây con của và đỉnh không được chọn.
- là đáp án bài toán nếu chỉ xét các đỉnh trong cây con của và đỉnh được chọn.
Đối với , đỉnh không được chọn nên ta có thể chọn các con của , do đó
Đối với , đỉnh được chọn nên ta không được chọn các con của , do đó
Đáp án của bài toán sẽ là .
¶ Cài đặt
Do trạng thái quy hoạch động chỉ dựa vào các đỉnh con, ta chỉ cần duyệt và tính trong quá trình DFS:
const int MAX_N = 2e5 + 5;
int N;
int C[MAX_N]; //
long long dp1[MAX_N], dp2[MAX_N]; // Khai báo cây và mảng lưu trạng thái quy hoạch động
vector<int> adj[MAX_N]; //
void calc(int V, int pV) { // hàm tính dp1[V] và dp2[V]
dp1[V] = 0;
dp2[V] = C[V];
for(int v_i: adj[V]) {
if(v_i == pV)continue;
calc(v_i, V); // DFS xuống và tính các đỉnh con
dp1[V] += max(dp1[v_i], dp2[v_i]);
dp2[V] += dp1[v_i];
}
}
long long solve(){ // hàm tính và trả về đáp án
calc(1, 0);
return max(dp1[1], dp2[1]);
}
¶ Độ phức tạp
- Ta thực hiện DFS trên cây một lần, do đó độ phức tạp thời gian là .
- Độ phức tạp không gian:
¶ Bài toán 2 - Kỹ thuật chuyển gốc
¶ Đề bài
Cho một cây gồm đỉnh , các cạnh có trọng số nguyên dương không quá . Tính với mọi từ đến . Nói cách khác, với mỗi đỉnh, tìm tổng khoảng cách từ đỉnh đó đến mọi đỉnh từ đến .
¶ Lời giải
Ta xét bài toán nếu chỉ cần tính với . Ta đặt gốc của cây là và định nghĩa trạng thái quy hoạch động: . Nói cách khác, lưu tổng khoảng cách từ đỉnh đến mọi đỉnh trong cây con của chính nó.
Để xây dựng công thức truy hồi, ta cần xét đóng góp của từng đỉnh con của vào .
Xét đỉnh con của . Ta nhận thấy mọi đường đi từ đến một đỉnh bất kỳ trong cây con của đều đi qua cạnh . Do đó, với một đỉnh nằm trong cây con của , ta có:
Như vậy, tổng khoảng cách từ đến mọi đỉnh trong cây con của là:
Từ đây, ta có công thức chuyển đổi trạng thái quy hoạch động:
Việc tính là một bài toán quy hoạch động trên cây cơ bản.
Quay lại bài toán ban đầu, do công thức này chỉ tính được đáp án cho gốc đã chọn, nếu ta duyệt và chọn từng đỉnh làm gốc rồi tính lại, ta giải được bài toán với độ phức tạp . Ở đây ta sẽ sử dụng kĩ thuật quy hoạch động chuyển gốc, cụ thể như sau:
Giả sử gốc hiện tại đang là , ta cần tìm cách chuyển gốc thành đỉnh con trong . Ta có một số nhận xét như sau:
- Ngoài đỉnh và , tất cả các đỉnh khác đều có cây con không thay đổi, do đó trạng thái quy hoạch động của chúng cũng không thay đổi.
- Đối với đỉnh , cây con của sẽ bỏ đi cây con . Khi thành gốc mới, cây con sẽ bao gồm thêm cây con mới của .
Ta gọi và lần lượt là trạng thái quy hoạch động trước và sau khi đổi gốc, và lần lượt là số đỉnh trong cây con trước và sau khi đổi gốc. Dựa vào các nhận xét trên, ta có:
- Đối với các đỉnh không phải và , ta có và .
- Ta tính được và .
- Ta tính được và .
Như vậy, ta có thể chuyển gốc sang một đỉnh con của gốc hiện tại trong . Nếu ta chuyển gốc theo thứ tự duyệt DFS, ta giải được bài toán trong độ phức tạp .
¶ Cài đặt
const int MAX_N = 2e5 + 5;
int N;
long long dp[MAX_N], sz[MAX_N], ans[MAX_N];
vector<pair<int, int>> adj[MAX_N]; // mảng kề lưu pair (chỉ số, trọng số cạnh)
void pre_calc(int V, int pV) { // hàm tính sz và dp ban đầu
dp[V] = 0;
sz[V] = 1;
for(pair<int, int> edge: adj[V]) {
int v_i = edge.first;
int w = edge.second;
if(v_i == pV)continue;
pre_calc(v_i, V);
dp[V] += sz[v_i]*w + dp[v_i];
sz[V] += sz[v_i];
}
}
void calc(int V, int pV) { // hàm chuyển gốc theo thứ tự DFS trong cây con V, sau đó chuyển gốc về V
ans[V] = dp[V]; // đáp án tại đỉnh V là dp[V] khi V là gốc
for(pair<int, int> edge: adj[V]) {
int v_i = edge.first;
int w = edge.second;
if(v_i == pV)continue;
long long old_dp_v_i = dp[v_i]; //
long long old_dp_V = dp[V]; // Khai báo các giá trị old. Giá trị new thay đổi trực tiếp vào mảng dp và sz
long long old_sz_v_i = sz[v_i]; //
long long old_sz_V = sz[V]; //
dp[V] = old_dp_V - (old_sz_v_i*w + old_dp_v_i); //
sz[V] = old_sz_V - old_sz_v_i; // Chuyển gốc từ V thành v_i
dp[v_i] = old_dp_v_i + (sz[V]*w + dp[V]); //
sz[v_i] = N; //
calc(v_i, V); // tiếp tục chuyển gốc trong cây con v_i
dp[V] = old_dp_V; //
sz[V] = old_sz_V; // Chuyển gốc từ v_i thành V
dp[v_i] = old_dp_v_i; //
sz[v_i] = old_sz_v_i; //
}
}
void solve() { // hàm tính đáp án
pre_calc(1, 0); // tính dp và sz với gốc là đỉnh 1
calc(1, 0); // chuyển gốc và tính đáp án bắt đầu từ đỉnh 1
}
¶ Độ phức tạp
- Độ phức tạp thời gian:
- Độ phức tạp thời gian:
¶ Bài toán 3 - Kỹ thuật knapsack trên cây
¶ Đề bài
Cho cây gồm đỉnh có gốc là đỉnh , đỉnh thứ có giá trị là và một chỉ số . Chọn một tập con các đỉnh sao cho trong cây con đỉnh có không quá đỉnh được chọn và tổng giá trị các đỉnh được chọn là lớn nhất.
¶ Lời giải
Bài toán này khá tương đồng với bài toán quy hoạch động cơ bản knapsack.
Trạng thái quy hoạch động ở bài này là tổng giá trị lớn nhất nếu chọn đỉnh trong cây con thỏa mãn điều kiện đề bài. Nếu không có cách nào chọn đỉnh mà vẫn thỏa mãn các điều kiện, ta định nghĩa . Như vậy đáp án của bài toán là
Để tính được giá trị này, ta cần thêm một trạng thái quy hoạch động phụ. Gọi là con của và là tổng giá trị lớn nhất nếu chọn đỉnh trong các cây con của đỉnh con đầu tiên thỏa mãn điều kiện đề bài. Nói cách khác, là trạng thái quy hoạch động cho tập các đỉnh thuộc .
Theo định nghĩa này, ta có và . Ta tính được dựa theo :
Để tính , ta có 2 lựa chọn là lấy hoặc không lấy đỉnh . Kết hợp điều kiện đề bài, ta có:
Độ phức tạp để tính là do giá trị của không quá , và độ phức tạp để tính là . Có trạng thái và trạng thái cần tính nên độ phức tạp tổng là .
¶ Cài đặt 1
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 5e3+5;
const long long INF = -1e18;
int N;
int C[MAX_N], K[MAX_N], sz[MAX_N];
long long dp[MAX_N][MAX_N];
long long fV[MAX_N][MAX_N];
vector<int> child[MAX_N]; // child[V] chứa các con của V
void calc(int V){
int n = child[V].size();
for(int v_i: child[V]) {
calc(v_i);
}
for(int i = 0; i <= n; i++)fill(fV[i], fV[i] + N + 1, -INF); // Khởi tạo giá trị cho fV
fV[0][0] = 0; //
for(int i = 1; i <= n; i++){
int v_i = child[V][i - 1];
for(int k = 0; k <= N; k++){
for(int j = 0; j <= k; j++){
fV[i][k] = max(fV[i][k], fV[i-1][j] + dp[v_i][k - j]); // Tính fV[i][k]
}
}
}
for(int k = 0; k <= N; k++){
if(k > K[V])dp[V][k] = -INF; //
else { // Tính dp[V][k]
if(k > 0)dp[V][k] = max(fV[n][k], fV[n][k-1] + C[V]); //
else dp[V][k] = fV[n][k]; //
}
}
}
long long solve() {
calc(1);
return *max_element(dp[1], dp[1] + N + 1);
}
¶ Tối ưu
Tuy nhiên ta có thể làm tốt hơn như thế. Nhận thấy rằng khi tính dựa vào và , ta có thể duyệt qua mọi cặp và rồi cập nhật vào . Ta cần duyệt mọi cặp thỏa mãn và . Tổng số cặp cần duyệt là . Ta biểu diễn tổng này thành .
Số cặp duyệt này tương đương với số cặp đỉnh sao cho nằm trong cây con và nằm trong cây con thỏa mãn .
Do 2 đỉnh và nằm ở 2 cây con khác nhau của đỉnh , sẽ là tổ tiên chung thấp nhất của và . Mỗi cặp đỉnh chỉ có duy nhất một tổ tiên chung thấp nhất, do đó với cách duyệt này mỗi cặp đỉnh chỉ được duyệt tối đa lần. Có cặp đỉnh khác nhau, do đó độ phức tạp của cách duyệt này là !
¶ Cài đặt 2
const int MAX_N = 5e3+5;
const long long INF = 1e18;
int N;
int C[MAX_N], K[MAX_N], sz[MAX_N];
long long dp[MAX_N][MAX_N];
long long fV[MAX_N][MAX_N];
vector<int> child[MAX_N]; // child[V] chứa các con của V
void calc(int V){
int n = child[V].size();
for(int v_i: child[V]) {
calc(v_i);
}
for(int i = 0; i <= n; i++)fill(fV[i], fV[i] + N + 1, -INF); // Khởi tạo giá trị cho fV
fV[0][0] = 0; //
for(int i = 1; i <= n; i++){
int v_i = child[V][i - 1];
for(int a = 0; a <= sz[V]; a++){ // sz[V] lưu tổng sz[v_i] từ 1 đến i - 1
for(int b = 0; b <= sz[v_i]; b++){
fV[i][a+b] = max(fV[i][a+b], fV[i-1][a] + dp[v_i][b]); // Cập nhật fV[i][a+b] từ fV[i-1][a] và dp[v_i][b]
}
}
sz[V] += sz[v_i];
}
for(int k = 0; k <= N; k++){
if(k > K[V])dp[V][k] = -INF; //
else { // Tính dp[V][k]
if(k > 0)dp[V][k] = max(fV[n][k], fV[n][k-1] + C[V]); //
else dp[V][k] = fV[n][k]; //
}
}
sz[V]++;
}
long long solve() {
calc(1);
return *max_element(dp[1], dp[1] + N + 1);
}
¶ Độ phức tạp
- Độ phức tạp thời gian:
- Độ phức tạp không gian:
Tuy nhiên, ta có thể phân tích độ phức tạp thời gian kĩ hơn. Giả sử bài toán trên có điều kiện (), khi đó việc cập nhật thêm một cây con vào knapsack có độ phức tạp và độ phức tạp tổng sẽ là . Phần chứng minh sẽ là bài tập dành cho bạn đọc