Baby-Step Giant-Step・可逆作用の反復到達探索

概要

一歩ずつ進むと長すぎる到達探索でも、時刻を「大きな幅で進む回数」と「端数」に分け、二つの状態の一致を探すと探索量を減らせる。この手法をBaby-Step Giant-Step(BSGS)と呼ぶ。有限群の累乗を例に仕組みを導き、有限集合上の可逆写像へ広げる。

考え方

群の累乗では指数を商と余りに分ける

群とは、結合則を満たす積、何も変えない単位元、各要素の逆元を持つ集合である。例えば、素数を法とする0以外の剰余は、剰余の積について群をなす。以下の a0a^0 は単位元、a−ka^{-k} は aka^k の逆元を表す。

群の要素 a,ba,b に対して ax=ba^x=b を満たす最小の非負整数 xx を探す。調べる範囲を 0≤x<U0\leq x<U、探索幅を W=⌈U⌉W=\lceil\sqrt U\rceil と決めると、各候補は一意に

x=iW+j,0≤j<W,0≤iW+j<Ux=iW+j,\qquad 0\leq j<W,\quad 0\leq iW+j<U

と書ける。右から a−iWa^{-iW} を掛けると、照合する二つの状態が現れる。

aiW+j=b⟺aj=b a−iWa^{iW+j}=b\quad\Longleftrightarrow\quad a^j=b\,a^{-iW}

左辺の aja^j を一歩ずつ作って表に保存するのがbaby stepである。同じ値が複数回現れたら最小の jj を残す。右辺は bb から始め、前計算した a−Wa^{-W} を右から掛けるたびに ii を一つ増やす。これがgiant stepである。i=0,1,…,⌊(U−1)/W⌋i=0,1,\ldots,\lfloor(U-1)/W\rfloor の順に表との一致を調べ、iW+j<UiW+j<U ならその指数を返す。

例えば法7で 3x=43^x=4 を探す。U=6,W=3U=6,W=3 とすると、表は j=0,1,2j=0,1,2 に対して 1,3,21,3,2。一方、3−3=6(mod7)3^{-3}=6\pmod 7 なのでgiant側は 4,4⋅6 mod 7=3,…4,4\cdot6\bmod7=3,\ldots と進む。i=1i=1 で表の j=1j=1 と一致し、x=1⋅3+1=4x=1\cdot3+1=4 を得る。実際、34≡4(mod7)3^4\equiv4\pmod7 である。

可逆写像でも同じ手順を使う

今度は有限集合上の可逆写像 ff、出発点 ss、目標 gg に対して、ft(s)=gf^t(s)=g となる最小時刻を探す。fkf^k は ff の kk 回の適用を表し、f0f^0 は何も変えない写像とする。可逆とは各状態の直前の状態が一意に定まり、逆写像 f−1f^{-1} で戻れるという意味である。

ここでは、目標から逆向きにbaby step、出発点から順向きにgiant stepを作る。上の群の説明とは表の向きが異なるので、表へ何を保存するかを改めて定める。

探索範囲を 0≤t<U0\leq t<U、幅を同じく W=⌈U⌉W=\lceil\sqrt U\rceil とし、t=iW+jt=iW+j と分ける。両辺へ逆写像を jj 回適用すれば、

fiW+j(s)=g⟺fiW(s)=f−j(g)f^{iW+j}(s)=g\quad\Longleftrightarrow\quad f^{iW}(s)=f^{-j}(g)

となる。従って次の手順で探せる。

  1. g,f−1(g),…,f−(W−1)(g)g,f^{-1}(g),\ldots,f^{-(W-1)}(g) を順に作り、状態をキー、最小の jj を値として表に保存する。
  2. F=fWF=f^W を前計算する。giant側の初期状態を ss とする。
  3. i=0,1,…,⌊(U−1)/W⌋i=0,1,\ldots,\lfloor(U-1)/W\rfloor の順に現在の状態を表で探す。一致した jj が iW+j<UiW+j<U を満たしたら、その時刻を返す。次の状態は FF の一適用で得る。

例えば法5で f(x)=2x+1f(x)=2x+1、s=1,g=0s=1,g=0 とする。以下の計算はすべて法5で行う。2の逆元は3なので、y=2x+1y=2x+1 を xx について解くと f−1(y)=3(y−1)f^{-1}(y)=3(y-1) である。U=5,W=3U=5,W=3 とした照合は次のようになる。

baby側の添字 jj012
f−j(0)f^{-j}(0)023

giant側は i=0i=0 で1、i=1i=1 で f3(1)=0f^3(1)=0。ここで表の j=0j=0 と一致するので、時刻 1⋅3+0=31\cdot3+0=3 を返す。元の列も 1→3→2→01\to3\to2\to0 となる。

一致から得た時刻で目標に到達することは上の同値式が保証する。また、任意の範囲内の時刻は商 ii と余り jj に分解できるため、到達するなら対応する状態は必ず照合される。一致がなければ範囲内では到達不能である。集合の大きさが UU なら、可逆写像の軌道は出発点を含む長さ高々 UU の周期なので、最初の到達時刻は UU 未満であり、この範囲だけで十分になる。

最小性は二段階で確認する。同じ ii の候補では表に保存した最小の jj が最も早い。異なる ii では、時刻の区間 [iW,(i+1)W)[iW,(i+1)W) が昇順に並ぶ。従って、範囲内の最初の一致を返すと最小時刻になる。最終区間で最小の jj が範囲外なら、同じキーのそれ以外の jj も範囲外なので捨ててよい。

短い周期では表の重複を無視できない。法11で f(x)=10xf(x)=10x、s=1,g=10,W=4s=1,g=10,W=4 とすると、baby側は 10,1,10,110,1,10,1 である。状態1へは最小の j=1j=1 を保存する。giant側の最初の状態1と一致して答えは1になるが、最後の j=3j=3 で上書きすると3を返してしまう。存在判定には足りる表でも、最小時刻の復元には足りないことがある。

giant stepを速く進められることも必要である。群の作用 f(x)=axf(x)=ax なら、aWa^W を高速累乗で用意すれば fW(x)=aWxf^W(x)=a^W x は積一回になる。ABC270 Gのような一次式の写像でも、合成を使えば反復を一つの式へまとめられる。写像 x↦ax+bx\mapsto ax+b を組 (a,b)(a,b) で表し、(c,d)(c,d) の後に適用すると、

a(cx+d)+b=(ac)x+(ad+b)a(cx+d)+b=(ac)x+(ad+b)

なので合成結果は (ac,ad+b)(ac,ad+b) である。単位写像 (1,0)(1,0) から合成の二分累乗で F=fWF=f^W を求めれば、その後の一giant stepは一次式の評価だけになる。

一般の可逆写像では fWf^W を高速に適用できるとは限らない。各giant stepで WW 回の素朴な反復を行うと、全体は O(U)O(U) に戻ってしまう。可逆性と、反復をまとめて速く進める方法を別々に確かめる。

成立条件と計算量

探索範囲 UU に対して、baby側は WW 個、giant側は高々 ⌈U/W⌉\lceil U/W\rceil 個である。一歩の逆向き遷移と fWf^W の一適用、状態の比較やhash計算を定数時間とすると、表の構築・照合はhash表なら期待 O(W+U/W)O(W+U/W) 時間、平衡二分探索木などの順序付き辞書なら最悪 O((W+U/W)log⁡W)O((W+U/W)\log W) 時間となる。表の空間は O(W)O(W)。W=⌈U⌉W=\lceil\sqrt U\rceil で、期待 O(U)O(\sqrt U) 時間または最悪 O(Ulog⁡U)O(\sqrt U\log U) 時間、O(U)O(\sqrt U) 空間になる。

これに逆写像と fWf^W の前計算費用を加える。群の累乗は O(log⁡U)O(\log U) 回の群演算で用意でき、法 PP の一次式の写像では逆元と合成の二分累乗に O(log⁡P+log⁡U)O(\log P+\log U) 時間がかかる。状態が大きい問題では、保存・比較の費用も別途数える。

範囲の上限 UU が分からなければ、一致なしから到達不能とは結論できない。また、非可逆写像には逆側の表をそのまま作れない。合同算術で逆元を使うときは法と互いに素であることが必要であり、非互いに素の場合には別の縮約などが必要になる。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。可逆性を使って反復回数を二分し、平方根個の状態を照合する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-baby-step-giant-step

Baby-Step Giant-Step・可逆作用の反復到達探索

習得する技能

  • 有限群の累乗または可逆な有限orbitについて、反復到達時刻をbaby/giant幅へ分解し、逆向きbaby tableと前向きgiant sequenceの衝突からindexを復元できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 法上の四則演算・高速累乗・逆元。

このUnitを直接前提とする単元: なし。

有限集合上の可逆な作用と逆作用を定義し、離散対数やaffine反復を含む反復到達時刻をbaby/giantの衝突へ変換して平方根時間で求める。合同算術が必要な問題では個別のreadinessとして接続する。

このUnitでは扱わないもの

  • Baby-Step Giant-Step・可逆作用の反復到達探索の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠