【2026年10月版】

索引と探す技術（第5回）― 状態空間の探索

公開日: 2026/10/02
読了時間: 約 22分

第4回までは、答えの候補が事前にデータとして存在する場合を扱った。第5回からは、候補の全体を見渡せない問題に進み、まず最適性や完全性の保証がある探索を扱う。

1. 全体を見渡せない候補

カーナビの経路を考える。出発地から目的地までの道順は交差点の列として表せるが、すべての道順を先に書き出して索引にするには数が多すぎる。道順の数は、交差点を一つ進むたびに枝分かれして増えていく。将棋やチェスの次の一手も同じで、局面から指せる手が次の局面を生み、その先でまた手が分かれる。

カーナビなら、交差点を点、交差点どうしをつなぐ道を線とした地図の上で、出発地から目的地までの線のつながりを探すことになる。探索するプログラムは、この地図を最初から全部描いておくのでなく、いま立っている交差点から出ている道を調べてはその先の交差点を書き足し、見込みの薄い方向は書き足すのをやめて引き返す。将棋なら、局面が点、指し手が線にあたる。教科書ではこの点を状態、線を行動、道の長さや所要時間をコスト、目的地や詰みの局面を目標と呼び、状態と行動からなるグラフの上の探索として定義している(状態空間探索)。手元の評価と全体の絞り込みを行き来しながら進む点に、第4回で整理した照合の基準を持つ検索との違いがある。

2. 辿り方の基本 ― 幅優先、深さ優先、一様コスト

状態空間を辿る基本の方法は、展開する順番で分かれる。幅優先探索は出発点に近いノードから順に展開し、最も浅い解を必ず見つける。その代わり、保持するノードの数は深さとともに指数的に増える。幅優先探索の考え方は、1945年にツーゼが考案し、1959年にムーアが迷路に、1961年にリーが回路の配線に使ったとされる。深さ優先探索は、一本の道を行き止まりまで進んでから戻る。保持するノードが少なくて済む一方、返すのは最初に行き着いた解で、それが最短である保証はなく、辿る順番しだいで変わる。閉路や無限の深さがあると、探索がいつまでも続くこともある。

反復深化深さ優先探索は、深さの上限を一つずつ増やしながら深さ優先を繰り返す。浅い層は何度も訪れるが、ノードが最も多いのは最後の層なので、繰り返しの負担は小さい。これにより、最も浅い解を深さに比例する程度の記憶で見つけられる。一様コスト探索は出発点からのコストが小さいノードから展開し、辺ごとにコストが違う場合にも最短の解を与える。中身は実質的にダイクストラ法と同じで、ダイクストラ法は1956年に着想され、1959年に発表された。

双方向探索は、出発点と目標の両側から同時に進み、途中で出会わせる。カーナビで言えば、出発地から広げた探索と目的地から逆向きに広げた探索がどこかの交差点で重なったところで、経路がつながる。一つの交差点から平均して b 本の道が出ているとし、解の深さを d とすると、片側だけで深さ d まで調べる探索では調べるノードが b の d 乗の規模に膨らむが、両側から半分ずつ進めば、合わせて b の d/2 乗程度に抑えられる。そのためには、目的地の側からどの交差点を通って来られるかを辿れること、つまり逆向きの遷移を計算できることが前提になる。ヒューリスティック探索に双方向の考え方を持ち込んだのは、1971年の Pohl である。

3. 見込みによる枝の削減 ― ヒューリスティックと A*

A* は、出発点からそのノードまでの実際のコスト g と、そこから目標までの推定コスト h の和 f で、展開の順番を決める。1968年にハート、ニルソン、ラファエルが、SRI でシェーキーロボットの経路計画を研究する中で提案した。カーナビで h に目的地までの直線距離を使うと、道路は直線より遠回りになるので、推定はいつも実際の道のりを下回る。見込みを低めに見積もっていれば、本当に近い経路は見込みのうえでも必ず有望に見え、探索が終わる前に展開されるので、最初に目的地に着いた経路が最短になる。教科書では、h が常に真のコスト以下であることを許容的と呼び、これが最適な解を確実に見つけるための条件になる。もう一段強い条件として、隣の交差点 y へ長さ d(x,y) の道を進んだとき、推定の減り方が進んだ道の長さ以下に収まるという性質があり、直線距離なら三角形の一辺が他の二辺の和以下であることから自然に満たされる。式ではすべての辺で h(x) ≤ d(x,y) + h(y) が成り立つことと書き、これを無矛盾と呼ぶ。無矛盾な h は、許容的でもある。h が真のコストに近いほど展開するノードは減り、h がすべて 0 なら一様コスト探索に一致する。

何より h の作り方が、A* の使いどころを決める。道路なら直線距離、15パズルならマンハッタン距離のように、問題の制約を一部外した易しい問題の厳密な解を h にする方法が代表的で、その作り方は第7回で扱う。A* は保持するノードの数が指数的に増えやすく、多くの場合はメモリが先に尽きる。そのため、記憶を抑える反復深化 A* や、最適性を緩めて速くする重み付き A* といった派生が作られている。

4. 下界による枝刈り ― 分枝限定法と既存のソルバ

最短経路のように、コストが足し算で積み上がる問題には A* が合う。割り当てや日程のように、変数の値の組み合わせから最良の解を選ぶ問題では、分枝限定法が使われる。担当者に仕事を一つずつ割り当てて費用の合計を最小にする問題で考えると、最初の仕事を誰に任せるかで場合を分け、次の仕事でさらに分けていくので、割り当ての候補は木の形に広がる。途中まで決めた枝では、残りの仕事をそれぞれ最も安い担当者に任せたと仮定して費用を足すと、その枝の先でどう割り当てても下回ることのない見積もりが得られる。一人が一つの仕事を受け持つという制約を外して計算した値なので、実際の費用はこれと同じかそれより高くなるからだ。すでに見つけた割り当ての費用がこの見積もり以下なら、その枝の先は調べるだけ無駄になるので、枝ごと捨てられる。教科書ではこの手順を、探索空間を木として分割し(分枝)、各枝で、その先に得られる解の下界を計算して、下界が現在の最良の解以上になる枝を捨てる(限定)と定義している。ランドとドイグが1960年に提案した方法で、下界の質が悪ければ、ほぼ全探索にまで退化してしまう。上の例で制約を外したように、下界は問題を緩和して求めることが多く、この緩和は第7回で扱う評価関数の作り方にもつながっている。

整数計画のソルバは、分枝限定法に切除平面を組み合わせた分枝カット法を使う。HiGHS は、混合整数計画を分枝カット法で解くオープンソースのソルバで、MIT ライセンスで公開されている。充足可能性問題(SAT)は、真か偽をとる変数に値を割り当てて、与えられた条件をすべて同時に満たせるかを調べる問題である。ここでは、値を仮に決めて進み、条件の矛盾に行き着いたらその矛盾を招いた値の組み合わせを新しい条件(節)として書き留め、同じ組み合わせへ再び踏み込むのを避けながら探索を続けるCDCLが、最先端のソルバの大半で使われている。SAT Competition 2025 の主トラックでは、AE-Kissat-MAB が SAT のインスタンスで173問を解いて1位になった。Google の OR-Tools の CP-SAT は、SAT の技法と制約プログラミングを併用している。

これらのソルバには枝刈りと下界の計算が組み込まれており、問題を形式化して渡せばそのまま使える。探索のアルゴリズムを自作するか既存のソルバに渡すかの判断は、第8回で扱う。

5. 前処理と問い合わせの速さ ― 道路網の経路探索

同じ道路網に何度も経路を問い合わせる場合は、問い合わせの前に道路網を加工しておける。Contraction Hierarchies(CH)は、交差点に重要度の順をつけ、重要度の低い交差点を飛び越える近道を前もって書き足しておく方式で、問い合わせでは出発地と目的地の両側から重要な道へ上っていく向きだけを辿ればよくなる。Hub Labeling(HL)は、各交差点に主要な中継点までの距離の一覧を持たせておき、出発地と目的地の一覧に共通して載っている中継点を突き合わせて距離を求める。西欧の道路網(約1,800万の頂点)で比較したサーベイの表では、ダイクストラ法は 9,326,696 の頂点を調べて、問い合わせに 2,195,080 マイクロ秒(約2.2秒)かかる。CH は、5分の前処理と 0.4GiB の空間で、調べる頂点が 280、問い合わせが 110 マイクロ秒になる。HL は、37分の前処理と 18.8GiB で、0.56 マイクロ秒まで下がる。全頂点対の距離を表にする極端な方式では、前処理が145時間30分、表が約120万GiB で、0.06 マイクロ秒になる。実装と計測の環境が手法ごとに違うため、数値は桁の目安として読むべきだ。

実際のシステムは、前処理の重さと更新の速さを比べて方式を選んでいる。OSRM は CH とマルチレベル・ダイクストラ(MLD)の二つの前処理の経路を持ち、README は基本として MLD を勧め、非常に大きな距離行列では CH がまだ適すると書いている。MLD は経路計算こそ CH より遅いものの、交通情報の更新が速い。GraphHopper は、速度重視のモードで CH、中間のモードで Landmarks、柔軟なモードで前処理を省いたダイクストラ法と A* を使い分けている。

探索の最中に枝を削る方法もある。Jump Point Search は、どのマスへの移動も同じコストのマス目の地図で、障害物のない区間は一直線に進み続けるのが最短になることを利用する。壁の角のように進む向きを選び直す必要が出てくるマス(ジャンプ点)まで一気に進み、ジャンプ点だけを展開して、その間のノードは飛ばす。追加の記憶も前処理も不要で、A* を桁違いに速くすると報告されている。ただし全面が通行可能な空の地図では、4連結の変種よりも A* のほうが速い。前処理の有無だけで速さは決まらない。効いてくるのは、手法が問題の構造に合っているかどうかだ。

ダイクストラ法の計算量そのものについては、2025年に理論上の改善が示された。Duan らの論文は、非負の重みを持つ有向グラフで、決定的な O(m log^{2/3} n) 時間のアルゴリズムを示し、疎なグラフでダイクストラ法の O(m + n log n) を初めて上回った。この論文はSTOC 2025 の最優秀論文にも選ばれている。ただしこれはあくまで漸近計算量に関する理論の結果であり、実用の経路探索では、上で見た OSRM や GraphHopper のように、CH などの前処理を使う方式が使われている。

6. 対戦相手のいる探索 ― アルファベータ法と置換表

対戦ゲームでは、自分の手に相手が最善の手で応じると仮定して先を読む。アルファベータ法は、1950年代から複数の研究者が独立に考案し、クヌースが1975年に解析した。将棋で自分の候補手を順に読む場面で、手 A を読み終えて、相手がどう応じても一定以上の形勢を保てると分かったとする。次の手 B を読み始めて、A より悪い形勢に持ち込む相手の応手が一つ見つかれば、相手はその応手を選ぶので、B に対する残りの応手を読むまでもなく B は A に劣ると決まる。アルファベータ法は、自分がすでに確保した値の下限(アルファ)と、相手が許す値の上限(ベータ)を持ち回りながら、この打ち切りを探索の全体で行う。一つの局面で指せる手が平均 b 通りあるとすると、指し手の並べ方が最良なら、深さ n の探索のノード数は b の n 乗から、b の n/2 乗程度に減る。そのため、指し手を調べる順番が、枝刈りの効き具合を大きく左右する。

指し手の順番が違っても、同じ局面に行き着くことは多い。置換表は読み終えた局面の結果をハッシュ表に保存しておき、同じ局面に再び行き着いたときはその結果を使い回す。局面のハッシュには、第2回で触れたゾブリストハッシュを使う。

評価関数にあたる部分を学習で作る方式に NNUE がある。Stockfish は2020年のバージョン12で NNUE を導入し、手作りの評価関数との対戦で、勝ち越したゲーム対が負け越した対の10倍以上あったと報告した。AlphaZero は、自己対戦の強化学習だけで、囲碁、チェス、将棋で世界王者のプログラムに勝った。評価関数を学習する話は、第7回で扱う。

ここまで扱った探索は、いずれも最適な解を求めるものだった。次の第6回では最適性の保証を手放し、良い解が得られればよい場合の探索を扱う。局所探索と、動物の行動に着想を得た手法を、部品とパラメータに分けて説明する。