Day 145-Q5 | Steiner Tree 2-近似

問題

$N$ 頂点 $M$ 辺の連結無向グラフ（辺重み $w_i \ge 1$）と、端末集合 $R \subseteq \{1,\dots,N\}$（$|R| \ge 2$）が与えられる。以下の手順で「メトリック閉包上のSteiner Tree 2-近似解」の重みを求めよ。

全点対最短路（Floyd-Warshall法）を計算し、任意の2頂点間の最短距離 $d(u,v)$ を求める。
端末集合 $R$ の頂点だけを頂点集合とし、任意の2端末間に重み $d(u,v)$ の辺を張った完全グラフ（メトリック閉包の端末部分グラフ）を構築する。
この完全グラフ上で最小全域木（MST）を求め、その総重みを出力する。

この値は元のグラフ上の厳密なSteiner Treeの重みの高々2倍であることが理論的に保証されている（Takahashi-Matsuyama 1980）。

入力形式

N M
u_1 v_1 w_1
:
u_M v_M w_M
|R|
r_1 r_2 ... r_{|R|}

制約

$2 \le N \le 100$

$1 \le M \le 500$

$1 \le w_i \le 1000$

$2 \le |R| \le N$、グラフは連結

入出力例

入力例1

出力例1

端末{1,3,5}。パス1-2-3-4-5(各辺重み1)沿いに全端末を連結するのが最小で重み4。

概念図：メトリック閉包 → 端末MST

ヒント（段階的開示）

ヒント1（方向性）

厳密なSteiner Tree（Day044のDreyfus-Wagner法）は端末数$K$に対して指数時間が必要で、端末数が多いと現実的でなくなる。多項式時間で「そこそこ良い」解を得たい場合、グラフの構造を「距離」という情報だけに圧縮してしまうアプローチが有効。

ヒント2（アプローチ）

任意の2端末間の最短経路を「直接辺」とみなした完全グラフ（メトリック閉包）を作る。この端末部分グラフ上でMSTを求めると、MSTの各辺は元のグラフ上の最短経路に展開できるため、それらをつなぎ合わせれば端末を連結する部分木が得られる。この構成コストは最適Steiner Treeの高々2倍であることが証明されている。

ヒント3（誘導）

def floyd_warshall(N, dist):
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            dik = dist[i][k]
            if dik == INF:
                continue
            for j in range(1, N + 1):
                if dik + dist[k][j] < dist[i][j]:
                    dist[i][j] = dik + dist[k][j]

# 端末部分グラフでPrim法によるMST
u = -1
for v in range(k):
    if not in_mst[v] and (u == -1 or min_edge[v] < min_edge[u]):
        u = v

Floyd-Warshallで全点対最短路を求めた後、端末集合だけを取り出してPrim法でMSTを構築する。

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    INF = float('inf')
    dist = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        dist[i][i] = 0

    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    for k in range(1, N + 1):
        dk = dist[k]
        for i in range(1, N + 1):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            for j in range(1, N + 1):
                nd = dik + dk[j]
                if nd < di[j]:
                    di[j] = nd

    R_size = int(data[idx]); idx += 1
    R = []
    for _ in range(R_size):
        R.append(int(data[idx])); idx += 1

    k = len(R)
    in_mst = [False] * k
    min_edge = [INF] * k
    min_edge[0] = 0
    total = 0
    for _ in range(k):
        u = -1
        for v in range(k):
            if not in_mst[v] and (u == -1 or min_edge[v] < min_edge[u]):
                u = v
        in_mst[u] = True
        total += min_edge[u]
        for v in range(k):
            if not in_mst[v]:
                d = dist[R[u]][R[v]]
                if d < min_edge[v]:
                    min_edge[v] = d

    print(total)

main()

Step-by-Step 解説

1メトリック閉包の構築
Floyd-Warshall法（$O(N^3)$）で全点対間の最短距離を求め、詳細な経路情報を「2点間のコスト」だけに圧縮する。

2端末部分グラフ上でのMST構築
メトリック閉包のうち端末集合$R$の頂点だけを取り出した完全グラフ上でMSTを構築する。$|R|\le N\le100$なのでPrim法で$O(|R|^2)$。

32-近似であることの直感
MSTの各辺は最短経路を表すので展開すると端末を全て連結する部分グラフが得られる。三角不等式（メトリック閉包は必ず満たす）を使うとMST重み$\le2\cdot w(T^*)$が導かれる。

4Dreyfus-Wagner（Day044）との対比
厳密解法は端末数$K$に対して指数時間だが必ず最適値を返す。本問の近似解法は多項式時間だが最悪で最適値の2倍まで悪化しうる。

5計算量
全体で$O(N^3+|R|^2)$。$N\le100$なのでFloyd-Warshallが支配的で$10^6$オーダー、十分高速。

よくあるミス

ミス	原因	正しい書き方
多重辺で大きい方の重みを採用してしまう	辺の重複を考慮せず単純に上書きする	同じ頂点対の辺が複数あれば最小重みを採用する
メトリック閉包を作らずに元グラフ上で直接端末MSTを求めようとする	Steiner Tree近似の本質（最短路による圧縮）を理解していない	必ず全点対最短路（メトリック閉包）を経由してから端末部分グラフのMSTを求める
Floyd-Warshallのループ順序を間違える	中継点$k$の意味を理解していない	中継点$k$を最も外側のループにし$k=1,\dots,N$の順で確定させる
2-近似を「常に最適解の2倍ぴったり」と誤解する	近似比の意味（上界）を誤解する	2-近似は最悪でも2倍以内という保証であり、多くの入力ではもっと良い
$\|R\|<2$のケースを想定していない	制約確認を怠る	本問では$\|R\|\ge2$が保証されているが一般化時は端末1個ならコスト0とする

次のステップ

発展: Takahashi-Matsuyama (1980) の詳細な証明を追い、なぜMST重み$\le2w(T^*)$が成り立つかを厳密に示せ。
次回予告: 未定（Master Levelローテーション継続）

自己評価

完全理解おおむね理解要復習

Day 145-Q5 — メトリック閉包上のSteiner Tree 2-近似（全点対最短路 + 端末MST）

問題