Day 144-Q2 — ALT法（A*探索・ランドマーク+三角不等式による下界枝刈り）

2026-09-05 赤色 Master / Phase 8+ ★★★★★★★★★ ランドマーク距離+三角不等式で許容的ヒューリスティックを作りA*でダイクストラ法を目的地方向へ枝刈り

問題

$N$ 頂点 $M$ 辺の無向重み付きグラフと $K$ 個のランドマーク頂点 $L_1,\dots,L_K$ が与えられる。頂点 $s$ から頂点 $t$ への最短距離を、ALT法（A* + ランドマーク + 三角不等式）で求めよ。

アルゴリズムの骨子

  1. 各ランドマーク $L_i$ から全頂点への最短距離 $d(L_i,\cdot)$ をダイクストラ法で前計算
  2. ヒューリスティック $h(v) = \max_i |d(L_i,t) - d(L_i,v)|$（三角不等式より $h(v)\le d(v,t)$、admissible）
  3. $f(v)=g(v)+h(v)$ の昇順に頂点を取り出すA*探索で最短距離を確定

入力形式

N M K
u_1 v_1 w_1
:
u_M v_M w_M
L_1 ... L_K
s t

制約

$2 \le N \le 2\times10^5$
$1 \le M \le 2\times10^5$
$1 \le K \le 10$
$1 \le w_i \le 10^9$

入出力例

入力例1

5 6 1
1 2 2
1 3 5
2 3 1
2 4 4
3 4 1
4 5 3
3
1 5

出力例1

7

最短経路 1→2→3→4→5（2+1+1+3=7）。ランドマーク3からの距離を使ったヒューリスティックで目的地方向を優先探索。

概念図：ランドマークによる下界

三角不等式による下界 h(v) = |d(L,t) - d(L,v)| L v t d(L,v) d(L,t) d(v,t) ≥ |d(L,t) - d(L,v)| = h(v) Lからの距離差の絶対値は常にd(v,t)を超えない → admissibleな下界

ヒント（段階的開示）

ヒント1（方向性）

通常のダイクストラ法は目的地を考慮せず一様に探索を広げる。目的地方向へのバイアスを、最短距離の正しさを崩さずに導入する方法を考えよ。

ヒント2（アプローチ）

A*探索は$f(v)=g(v)+h(v)$の順に処理するダイクストラ法の一般化であり、$h(v)$が真の残り距離を超えない下界（admissible）である限り正しさが保証される。ALT法はこの下界を事前計算したランドマーク距離+三角不等式で安く求める。複数ランドマークの最大値を取ればよりタイトな下界になる。

ヒント3（誘導） 
landmark_dist = [dijkstra_from(N, adj, L) for L in landmarks]

def h(v, t):
    best = 0
    for ld in landmark_dist:
        best = max(best, abs(ld[t] - ld[v]))
    return best

g = [float('inf')] * (N + 1)
g[s] = 0
pq = [(h(s, t), s)]
# あとは f(v)=g(v)+h(v) をキーにした通常のダイクストラ法

模範解答 (Python)

import sys
import heapq

def dijkstra(N, adj, src):
    dist = [float('inf')] * (N + 1)
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

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

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))

    landmarks = [int(data[idx + i]) for i in range(K)]
    idx += K
    s = int(data[idx]); idx += 1
    t = int(data[idx]); idx += 1

    land_dist = [dijkstra(N, adj, L) for L in landmarks]
    INF = float('inf')

    def h(v):
        best = 0
        for ld in land_dist:
            if ld[t] == INF or ld[v] == INF:
                continue
            best = max(best, abs(ld[t] - ld[v]))
        return best

    g = [INF] * (N + 1)
    g[s] = 0
    visited = [False] * (N + 1)
    pq = [(h(s), s)]
    while pq:
        f, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        if u == t:
            break
        for v, w in adj[u]:
            ng = g[u] + w
            if ng < g[v]:
                g[v] = ng
                heapq.heappush(pq, (ng + h(v), v))

    print(g[t] if g[t] < INF else -1)

main()

Step-by-Step 解説

1許容的ヒューリスティックと正しさの保証
三角不等式$|d(L,t)-d(L,v)|\le d(v,t)$より、admissibleな下界が得られA*はダイクストラ法と同じ正しい距離を返す。
2複数ランドマークによる下界の強化
異なる位置の複数ランドマークからの下界の最大値を取ることで、どの方向のクエリでもタイトな下界を得る。
3A*探索の実装
優先度付きキューのキーをg(v)からf(v)=g(v)+h(v)に変えるだけで、あとは通常のダイクストラ法と同じロジック。
4なぜ探索が減るのか
目的地から遠ざかる方向のノードはf(v)が大きくなり後回しにされる。
5計算量
前計算O(KM log N)、クエリ処理は通常のダイクストラ法と同じO(M log N)。

よくあるミス

ミス原因正しい書き方
ヒューリスティックに負の値を許してしまう$d(L,t)-d(L,v)$が負のままだと下界として不整合必ず絶対値を取り複数ランドマークの最大値を使う
訪問済み頂点をキューから取り出した際に再処理してしまうキューに重複エントリが入る遅延削除方式の理解不足取り出し時にvisitedを確認し確定済みならスキップする
到達不能なランドマーク距離(inf)を混ぜて不正な値になる非連結グラフでinf同士の差分計算が発生infを含む差分計算はスキップし寄与しないランドマークとして無視する
h(v)を毎回全頂点分テーブル化しようとし計算量が爆発するALT法の利点(クエリに依存しない前計算)を勘違いするh(v)はクエリ時にO(K)で都度計算し前計算はランドマーク距離配列のみに留める
優先度付きキューのキーをg(v)のままにし見た目だけA*にしてしまうヒューリスティックの足し込みを実装し忘れるheappushのキーに必ずh(v)を加算する

次のステップ

  • 発展: ランドマークの選び方（ランダム/最遠点貪欲/平面分割ベース）が探索効率にどう影響するか実験せよ。
  • 発展2: 双方向A*（Q4の双方向ダイクストラ法と組み合わせる）にする場合、前向き・後ろ向きヒューリスティックの整合性(consistency)をどう保つか調べよ。

自己評価

自分の回答

気づき・メモ