Bỏ qua

Steiner Tree

Bài toán cây Steiner là một bài toán tối ưu tổ hợp, tương tự như cây khung nhỏ nhất, thuộc nhóm các bài toán mạng ngắn nhất. Cây khung nhỏ nhất yêu cầu nối tất cả các đỉnh đã cho bằng mạng có tổng độ dài nhỏ nhất. Còn cây Steiner cho phép thêm các đỉnh phụ ngoài các đỉnh đã cho, nhằm tối thiểu hóa tổng chi phí của mạng nối các đỉnh.

Dẫn nhập bài toán

Đầu thế kỷ 19, nhà toán học hình học nổi tiếng Steiner tại Đại học Berlin đã nghiên cứu một bài toán đơn giản nhưng rất gợi mở: nối ba ngôi làng bằng hệ thống đường có tổng chiều dài nhỏ nhất. Về mặt toán học, bài toán là: cho ba điểm \(A\), \(B\), \(C\) trên mặt phẳng, tìm điểm \(P\) trên mặt phẳng sao cho tổng \(a+b+c\) là nhỏ nhất, với \(a\), \(b\), \(c\) lần lượt là khoảng cách từ \(P\) đến \(A\), \(B\), \(C\).

Đáp án là: nếu mọi góc trong tam giác \(\textit{ABC}\) đều nhỏ hơn \(120^{\circ}\), thì \(P\) là điểm sao cho các cạnh \(\textit{AB}\), \(\textit{BC}\), \(\textit{AC}\) tạo với \(P\) các góc \(120^{\circ}\). Nếu tam giác \(\textit{ABC}\) có một góc (ví dụ góc \(C\)) lớn hơn hoặc bằng \(120^{\circ}\), thì \(P\) trùng với đỉnh \(C\).

Mở rộng bài toán

  1. Trong bài toán Steiner gốc, chỉ có ba điểm cố định \(A,B,C\). Có thể mở rộng thành \(n\) điểm \(A_1,A_2,\dots,A_n\); yêu cầu tìm điểm \(P\) trên mặt phẳng sao cho tổng \(a_1+a_2+\dots+a_n\) là nhỏ nhất, với \(a_i\) là khoảng cách từ \(P\) đến \(A_i\).

  2. Xét thêm yếu tố trọng số cho các điểm. Khi đó, mỗi điểm \(A_i\) có trọng số \(w_i\), yêu cầu tìm \(P\) sao cho tổng \(\sum a_i \cdot w_i\) nhỏ nhất.

  3. Courant và Robbins cho rằng mở rộng đầu tiên là chưa đủ sâu sắc. Để có một mở rộng thực sự giá trị, cần bỏ ý tưởng chỉ tìm một điểm \(P\), mà thay vào đó là tìm một "mạng lưới đường thẳng" có tổng chiều dài nhỏ nhất nối \(n\) điểm \(A_1,A_2,\cdots,A_n\), sao cho mọi cặp điểm đều có thể nối với nhau qua mạng lưới này. Bài toán này được gọi là bài toán cây Steiner. Với \(n\) điểm, tối đa có \(n-2\) điểm phụ (gọi là điểm Steiner). Qua mỗi điểm Steiner, tối đa có ba cạnh đi qua. Nếu có ba cạnh, chúng tạo với nhau các góc \(120^{\circ}\); nếu chỉ có hai cạnh, điểm Steiner đó trùng với một điểm đã cho, và góc giữa hai cạnh đó lớn hơn hoặc bằng \(120^{\circ}\).

Kết nối nhiều hơn ba điểm để tạo mạng ngắn nhất:

steiner-tree1

Ở hình đầu tiên, lời giải gồm năm đoạn thẳng, có hai điểm Steiner (màu đỏ \(s_1,s_2\)), tại đó ba đoạn thẳng giao nhau với góc \(120^{\circ}\). Hình thứ hai có ba điểm Steiner. Hình thứ ba, một số điểm Steiner có thể bị "thoái hóa", tức là trùng với một điểm đã cho.

Chúng ta sẽ mô hình hóa bài toán cây Steiner dưới dạng đồ thị.

steiner-tree2

Với hình thức thứ nhất, nếu chọn các điểm quan trọng là \(\{1,2,3,4\}\), dễ thấy nếu chỉ nối trực tiếp bốn điểm này thì tổng trọng số nhỏ nhất là 12, nhưng đây không phải là phương án tối ưu. Nếu sử dụng thêm đỉnh số 5, tổng trọng số nhỏ nhất là 9, cho đáp án tốt hơn.

Với hình thức thứ hai, nếu chọn các điểm quan trọng là \(\{1,2,3,4\}\), có thể thấy một số điểm trong số này thậm chí không có cạnh nối trực tiếp, nên bắt buộc phải dùng các điểm phụ (điểm Steiner). Khi xét thêm đỉnh 5, tổng trọng số nhỏ nhất là 9.

Ta cũng nhận thấy trong cả hai hình, điểm Steiner của đỉnh 1 và 4 bị "thoái hóa", tức là trùng với chính đỉnh 1 hoặc 4.

Bài tập mẫu

Trước tiên, hãy làm quen với bài toán cây Steiner nhỏ nhất qua một bài mẫu: 【模板】最小斯坦纳树.

Đề bài đã rất rõ ràng: cho một đồ thị liên thông \(G\) với \(n\) đỉnh và \(k\) đỉnh quan trọng, yêu cầu nối \(k\) đỉnh này sao cho tổng trọng số các cạnh trong cây khung là nhỏ nhất.

Như đã phân tích, nếu chỉ nối trực tiếp \(k\) đỉnh quan trọng thì chưa chắc đã tối ưu, hoặc các đỉnh này không nhất thiết phải nối trực tiếp với nhau. Do đó, cần sử dụng thêm \(n-k\) đỉnh còn lại.

Ta sử dụng quy hoạch động trạng thái (state compression DP) để giải. Gọi \(f(i,S)\) là tổng trọng số nhỏ nhất của cây gốc tại \(i\), bao phủ tất cả các đỉnh trong tập \(S\).

Xét chuyển trạng thái:

  • Trước tiên, chuyển giữa các tập con liên thông: \(f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T))\).

  • Sau đó, với trạng thái liên thông hiện tại, thực hiện phép nới lỏng cạnh: \(f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))\). Trong code dưới, dùng tree[tot] để lưu thông tin hai đỉnh \(i,j\) liên thông.

Cài đặt tham khảo 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

constexpr int MAXN = 510;
constexpr int INF = 0x3f3f3f3f;
using P = pair<int, int>;
int n, m, k;

struct edge {
  int to, next, w;
} e[MAXN << 1];

int head[MAXN << 1], tree[MAXN << 1], tot;
int dp[MAXN][5000], vis[MAXN];
int key[MAXN];
priority_queue<P, vector<P>, greater<P>> q;

void add(int u, int v, int w) {
  e[++tot] = edge{v, head[u], w};
  head[u] = tot;
}

void dijkstra(int s) {  // 求解最短路
  memset(vis, 0, sizeof(vis));
  while (!q.empty()) {
    P item = q.top();
    q.pop();
    if (vis[item.second]) continue;
    vis[item.second] = 1;
    for (int i = head[item.second]; i; i = e[i].next) {
      if (dp[tree[i]][s] > dp[item.second][s] + e[i].w) {
        dp[tree[i]][s] = dp[item.second][s] + e[i].w;
        q.push(P(dp[tree[i]][s], tree[i]));
      }
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  memset(dp, INF, sizeof(dp));
  cin >> n >> m >> k;
  int u, v, w;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v >> w;
    add(u, v, w);
    tree[tot] = v;
    add(v, u, w);
    tree[tot] = u;
  }
  for (int i = 1; i <= k; i++) {
    cin >> key[i];
    dp[key[i]][1 << (i - 1)] = 0;
  }
  for (int s = 1; s < (1 << k); s++) {
    for (int i = 1; i <= n; i++) {
      for (int subs = s & (s - 1); subs;
           subs = s & (subs - 1))  // 状压 dp 可以看下题解里写的比较详细
        dp[i][s] = min(dp[i][s], dp[i][subs] + dp[i][s ^ subs]);
      if (dp[i][s] != INF) q.push(P(dp[i][s], i));
    }
    dijkstra(s);
  }
  cout << dp[key[1]][(1 << k) - 1] << '\n';
  return 0;
}

Một bài kinh điển khác: [WC2008] Kế hoạch tham quan.

Bài này yêu cầu tìm cây Steiner có tổng trọng số các đỉnh nhỏ nhất. Gọi \(f(i,S)\) là tổng trọng số nhỏ nhất của cây gốc tại \(i\), bao phủ tất cả các đỉnh trong tập \(S\), \(a_i\) là trọng số đỉnh.

Chuyển trạng thái:

  • \(f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T)-a_i)\). Vì khi hợp nhất hai tập, \(a_i\) bị cộng hai lần nên phải trừ đi.

  • \(f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))\).

Có thể thấy chuyển trạng thái giống bài mẫu ở trên, điểm khó là xuất đáp án, cần lưu lại đường đi trong quá trình DP.

Dùng pre[i][s] để lưu thông tin chuyển trạng thái về \(i\) và tập \(s\). Sau khi DP xong, bắt đầu từ pre[root][S], lần lượt truy vết các đỉnh và tập con, dùng mảng ans để đánh dấu các đỉnh đã sử dụng, khi phân rã hết tập \(S\) thì kết thúc.

Cài đặt tham khảo 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define mp make_pair
using P = pair<int, int>;
using PP = pair<P, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr int dx[] = {0, 0, -1, 1};
constexpr int dy[] = {1, -1, 0, 0};
int n, m, K, root;
int f[101][1111], a[101], ans[11][11];
bool inq[101];
PP pre[101][1111];
queue<P> q;

bool legal(P u) {
  if (u.first >= 0 && u.second >= 0 && u.first < n && u.second < m) {
    return true;
  }
  return false;
}

int num(P u) { return u.first * m + u.second; }

void spfa(int s) {
  memset(inq, 0, sizeof(inq));
  while (!q.empty()) {
    P u = q.front();
    q.pop();
    inq[num(u)] = false;
    for (int d = 0; d < 4; d++) {
      P v = mp(u.first + dx[d], u.second + dy[d]);
      int du = num(u), dv = num(v);
      if (legal(v) && f[dv][s] > f[du][s] + a[dv]) {
        f[dv][s] = f[du][s] + a[dv];
        if (!inq[dv]) {
          inq[dv] = true;
          q.push(v);
        }
        pre[dv][s] = mp(u, s);
      }
    }
  }
}

void dfs(P u, int s) {
  if (!pre[num(u)][s].second) return;
  ans[u.first][u.second] = 1;
  int nu = num(u);
  if (pre[nu][s].first == u)
    dfs(u, s ^ pre[nu][s].second);  // 通过 dfs 来找到答案
  dfs(pre[nu][s].first, pre[nu][s].second);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  memset(f, INF, sizeof(f));
  cin >> n >> m;
  int tot = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[tot];
      if (!a[tot]) {
        f[tot][1 << (K++)] = 0;
        root = tot;
      }
      tot++;
    }
  }
  for (int s = 1; s < (1 << K); s++) {
    for (int i = 0; i < n * m; i++) {
      for (int subs = s & (s - 1); subs; subs = s & (subs - 1)) {
        if (f[i][s] > f[i][subs] + f[i][s ^ subs] - a[i]) {
          f[i][s] = f[i][subs] + f[i][s ^ subs] - a[i];  // 状态转移
          pre[i][s] = mp(mp(i / m, i % m), subs);
        }
      }
      if (f[i][s] < INF) q.push(mp(i / m, i % m));
    }
    spfa(s);
  }
  cout << f[root][(1 << K) - 1] << '\n';
  dfs(mp(root / m, root % m), (1 << K) - 1);
  for (int i = 0, tot = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (!a[tot++])
        cout << 'x';
      else
        cout << (ans[i][j] ? 'o' : '_');
    }
    if (i != n - 1) cout << '\n';
  }
  return 0;
}

Bài tập

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply