グラフアルゴリズムを1から — 最短経路とその応用

言い換えると「$n$ の評価 $f(n)$ は、出発点から $n$ まで実際に歩いた距離 $g(n)$ と、$n$ からゴールまでの残り距離の見積もり $h(n)$ の和」です。$h$ はヒューリスティック関数と呼ばれ、たとえば地図なら「ゴールまでの直線距離」がよく使われます。道路は曲がりくねっていても直線より短くはならないので、これは実際の残距離を決して過大評価しない見積もりです。

この「過大評価しない」という性質（許容性）が成り立つ限り、Aは最短経路を見つけることが保証されます。しかも探索はゴール方向に絞られ、ダイクストラ法より調べる頂点がずっと少なくて済みます。実は $h(n)=0$ とおくとAはダイクストラ法そのものに戻ります。つまりダイクストラ法は「勘ゼロのA*」であり、2つは別物ではなく地続きです。

コードで書くダイクストラ法

Pythonの heapq（二分ヒープ）を使うと本体は10行ほどです。

import heapq

def dijkstra(graph, start):          # graph[u] = [(v, w), ...]
    dist = {start: 0}
    pq = [(0, start)]                # (暫定距離, 頂点)
    while pq:
        d, u = heapq.heappop(pq)     # 暫定最小の頂点を確定
        if d > dist.get(u, float("inf")):
            continue                 # 古い記録は読み捨て
        for v, w in graph[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w      # 緩和
                heapq.heappush(pq, (d + w, v))
    return dist

A*にするには、pushするキーを d + w から d + w + h(v) に変えるだけ。骨格は共通です。

そしてベクトル検索へ — HNSWはグラフ探索の応用

ここからが本題の応用です。RAGやレコメンドでは、文書や商品を埋め込みベクトルにして「クエリに最も近いベクトルを探す」処理（最近傍探索）が心臓部になります。愚直にやるなら全ベクトルとの距離を総当たりで測ればよいのですが、データが数千万本になると1クエリごとの全件走査は割に合いません。

そこで登場するのが HNSW（Hierarchical Navigable Small World、一次資料の論文で提案）です。発想はこうです。あらかじめ、互いに近いベクトル同士を辺でつないだグラフを作っておく。検索時は適当な入口の頂点から出発し、「いまいる頂点の隣接頂点のうち、クエリに最も近いものへ移る」を繰り返す。どの隣に移ってもクエリに近づけなくなったら、そこが答えの候補です。グラフの上を「クエリへの近さ」という見積もりに導かれて歩く——A*で見た発想の親戚だと分かります。

HNSWの「H」は階層です。上の層ほど頂点を間引いた粗いグラフを重ね、検索は最上層の長距離ジャンプで大まかに近づき、下の層に降りて細かく詰めます。高速道路で都市まで飛び、一般道で住所まで詰めるイメージで、スキップリストというデータ構造と同じ発想です。この構造により、実用上は全件走査よりはるかに少ない距離計算で近傍が見つかります。ただし貪欲に歩くぶん、真の最近傍を取り逃がすことがある近似手法です。取り逃しにくくする仕掛けが、1本道ではなく上位 ef 件の候補を持ち歩くビーム探索で、この ef が後述する実務の主役になります。

「近い」を測る物差しは内積・コサイン類似度・ユークリッド距離のいずれかです。物差しの感覚は下の図で確かめられます。

現場ではこう使う

RAG・検索基盤の担当者がインデックスを選ぶとき。 Faiss・pgvector・Qdrant・Milvus・OpenSearchなど主要なベクトルDBはほぼすべてHNSWを実装しています。触るパラメータは3つ: 各頂点から張る辺の本数 M（メモリと精度のトレードオフ）、構築時の候補数 efConstruction（インデックス品質）、検索時の候補数 efSearch（再現率と遅延のトレードオフ）。チューニングは「efSearch を上げて再現率がどこで頭打ちになるか」を実データで測るのが定石です。

落とし穴1: 再現率の低さを距離関数のせいにする。 「RAGが明らかに関連する文書を取ってこない」とき、埋め込みモデルを疑う前に efSearch（ライブラリによっては ef）が既定値のままでないかを見る。近似検索の取り逃しは仕様であり、候補数を増やせば消えることが多い問題です。

落とし穴2: 距離メトリクスの不一致。 コサイン類似度のつもりでベクトルを正規化せずに内積インデックスへ入れると、ノルムの大きいベクトルばかり返ってきます。インデックス作成時と検索時でメトリクス設定が一致しているかは、障害調査の最初の確認項目です。

落とし穴3: 負の重みにダイクストラ法。 経路コストに「割引」や「報酬」を混ぜた途端、前提が崩れて答えが黙って間違います。エラーは出ません。負の辺が入る設計ならベルマン–フォード法系に切り替えます。

ゲーム・地図系の担当者なら、Aのヒューリスティックが許容的か（過大評価していないか）のレビューが必須です。面接でも「$h$ が過大評価するとAはどうなるか」（答え: 速くなるが最短性が壊れる）は定番の問いです。

まとめ

• グラフは「点と線」で関係を表す万能の言語。最短経路はその最重要問題
• BFSは辺の本数の最短をキューで、ダイクストラ法は重み付きの最短を優先度付きキューと緩和で解く
• A*は「残距離の過大評価しない見積もり」で探索をゴールへ絞る。$h=0$ でダイクストラ法に一致
• HNSWは「近いもの同士をつないだグラフを、近さに導かれて貪欲に歩く」近似最近傍探索。LLM時代の検索の土台にも、最短経路と同じグラフ探索の骨格が生きている

計算量の読み方は計算量の基礎、キューやヒープそのものはデータ構造ツアー、HNSWが組み込まれる検索システム全体はRAGの基礎で扱っています。