backtracking・可逆な探索状態

概要

一つの候補を途中まで作り、その先を調べ終えたら選択を取り消して、別の続きを試す。この探索を バックトラック(backtracking) と呼ぶ。現在の選択に必要な状態だけを保持し、枝を移るたびに元へ戻すことで、多数の候補に共通する途中計算を使い回す。

重要なのは、どの情報が現在の候補に属し、どこまで戻せば次の候補を正しく試せるかである。再帰を書くこと自体よりも、状態の意味と復元の約束を先に定める。

考え方

一つの頂点にも、異なる履歴で到着する

無向グラフに辺 1 ⁣− ⁣21\! -\! 2、1 ⁣− ⁣31\! -\! 3、2 ⁣− ⁣42\! -\! 4、3 ⁣− ⁣43\! -\! 4 があるとする。頂点1から出発し、同じ頂点を二度使わない経路をすべて数えたい。ここでは、出発点だけの経路も一つと数える。

小さい順の隣接頂点を先に調べると、経路は次の7本になる。各行は、その時点で探索を止めた一つの経路である。

順番現在の経路次の候補
112, 3
21 → 24
31 → 2 → 43
41 → 2 → 4 → 3なし
51 → 34
61 → 3 → 42
71 → 3 → 4 → 2なし

通常の到達可能性のDFSでは、一度訪れた頂点を以後ずっと訪問済みにする。しかし、この表で頂点4を最初の到着後に禁止すると、6行目の経路が失われる。二つは終点が同じでも、異なる経路として数える必要がある。

さらに、1 → 2 → 4 の後には3へ進めるが、1 → 3 → 4 の後には2へ進める。終点だけでは、次に使える頂点も決まらない。 記録したいのは過去の探索全体で訪れたかどうかではなく、現在作っている経路に含まれるかどうかである。

現在の経路を path、その経路に頂点 vv が含まれるかを used[v] とする。前進するときに頂点を使用中にし、戻るときに使用中の印を外せば、別の枝では同じ頂点を再び使える。

選択を取り消すと、次の枝の出発点がそろう

上の探索の途中で、状態がどう戻るかを追ってみよう。used の集合は、各行の操作を終えた後の状態を表す。

操作path使用中の頂点
1から2を選ぶ1 → 2{1,2}\{1,2\}
2から4を選ぶ1 → 2 → 4{1,2,4}\{1,2,4\}
4から3を選ぶ1 → 2 → 4 → 3{1,2,3,4}\{1,2,3,4\}
3の探索を終えて戻る1 → 2 → 4{1,2,4}\{1,2,4\}
4の探索を終えて戻る1 → 2{1,2}\{1,2\}
2の探索を終えて戻る1{1}\{1\}
1から次の候補3を選ぶ1 → 3{1,3}\{1,3\}

最後の行で3が空いているのは、先に試した枝で使った印を取り消したからである。取り消す対象は、今戻ろうとしている呼び出しで追加した頂点一つになる。

ここから、関数の約束を定められる。search(v) の呼び出し前には、path は親までの経路で、vv は未使用とする。関数に入ったら vv を追加し、子の探索を行い、最後に vv を取り除く。関数が戻った後の path と used は、呼び出す直前と完全に一致する。 この約束があるので、親は毎回同じ状態から次の子を試せる。

一方、これまでに数えた経路数を表す count は、探索全体の集計である。こちらは戻るときも減らさない。局所的な選択の状態と、探索全体に残す集計を区別しよう。

元のグラフではなく、経路を節点とする木をたどる

バックトラックの動きを、選択履歴を節点とする木で捉える。この例では根が 1、その子が 1 → 2 と 1 → 3 であり、子へ進むたびに未使用の隣接頂点を一つ追加する。この木を探索木と呼ぶ。

各節点で、used がちょうど path 内の頂点を表すように保つ。未使用の隣接頂点だけを追加するので、作られる経路は必ず単純である。任意の単純経路を一つ固定すれば、その頂点列の順に選択する枝が必ず存在し、途中で使用済み判定に阻まれることもない。単純グラフなら同じ頂点列を別の選択で生成することもないため、各経路と探索木の節点が一対一に対応する。

この対応から、経路数は葉の数ではなく、根を含む全節点数である。1 → 2 も、それより先へ進めるかにかかわらず一つの経路だからだ。特定の終点までの経路だけを求める別問題では、数える条件をその終点への到着時に変える。

グラフの頂点数・辺数に対する通常のDFSの評価を、そのまま使うことはできない。一つの頂点が多くの経路の終点として現れるため、探索木の節点数は元の頂点数よりはるかに多くなりうる。

必要な個数に達したら、何が確定するか

ABC284 Eは、頂点1を始点とする単純経路数を求めるが、答えは百万で打ち止めである。全経路を生成しなくても、百万本を発見した時点で出力が確定する。公式問題文には最大次数10という条件もあり、公式解説は訪れた探索状態数で計算量を評価している。

一般化して、始点を ss、必要な個数の上限を正整数 LL とし、実際の経路数を PP とする。欲しい答えが min⁡(P,L)\min(P,L) なら、各節点を一つ数え、LL に達した後は子へ進まずに戻ればよい。例えば先ほどのグラフで L=4L=4 なら、1 → 2 → 4 → 3 を数えた時点で4が確定する。残り3本の存在を調べる必要はない。

次は手順を示す擬似コードである。adj[v] は頂点 vv の隣接リスト、s は始点、L は1以上とする。used をすべて偽、path を空、count を0に初期化する。

search(v):
    used[v] = true
    path.push(v)
    count += 1

    for w in adj[v]:
        if count == L:
            break
        if not used[w]:
            search(w)

    path.pop()
    used[v] = false

search(s)
出力 count

子を呼ぶのは count < L の間だけなので、上限を超えて数えない。上限に達した場合もループを抜けてから復元し、親へ戻る。親も同じ上限判定で以後の分岐を止める。このため、途中で打ち切っても関数の復元の約束が保たれる。上限に達しなければ探索木を最後までたどって PP を、達すれば LL を出力する。

枝を捨てる根拠と、状態の戻し方を分けて考える

バックトラック自体は候補を列挙する手順であり、指数的な探索を自動で小さくするものではない。途中状態から必要な答えが得られないと証明し、その部分木を省く判断を枝刈りと呼ぶ。

例えば、NN 個の品物からちょうど KK 個を選ぶ探索なら、選択済みの個数と残りの個数の和が KK 未満になった枝は完成できない。また、非負の費用を追加して予算内に収める探索では、すでに予算を超えた枝から先へ進む必要はない。負の費用を許すと後で合計が下がりうるため、同じ枝刈りは使えない。

最適値を求める探索では、その枝から達成できる値の上界や下界と、発見済みの最良値を比較して省くこともある。ただし、最適解の個数も数えるなら、最良値と並ぶ枝を捨ててよいとは限らない。要求が「存在」「最適値」「全個数」のどれかによって、捨てられる枝が変わる。

先ほどの上限到達による打ち切りは、未探索の経路がないという判断ではない。未探索部分の個数が出力を変えないから終了できる。枝刈りと同様、何を証明すれば省略できるかを答えの定義から確かめる。

状態の保持方法も選べる。子へ進むごとに配列をコピーすれば親の状態を直接壊さずに済むが、コピーの費用がかかる。変更箇所が少ないなら、同じ配列を使い、変更した順の逆に取り消すと軽い。使用中の印や経路末尾なら、前進・復元とも定数時間である。複数箇所を書き換える場合は、元の値を保存してから変更し、戻るときに復元する。途中の return が復元を飛ばさないよう、出口もそろえる。

成立条件と計算量

バックトラックを適用するには、候補を有限回の選択で作れ、現在の選択に対する合法な次の手を判定できることが必要である。単純経路では一回進むごとに未使用頂点を一つ使うため、深さは高々頂点数で止まる。頂点の再使用を許す歩道を長さ無制限に列挙すると、閉路を何度でも回れて停止しない場合がある。

グラフの頂点数を NN、辺数を MM、最大次数を Δ\Delta とする。上限付きの擬似コードでは、探索木で訪れる節点数は R=min⁡(P,L)R=\min(P,L) 個であり、各節点で隣接リストを高々一度走査する。入力の保存と初期化を含む全時間は

O(N+M+(Δ+1)R)O\bigl(N+M+(\Delta+1)R\bigr)

となる。+1+1 は、孤立頂点のように次数が0でも呼び出しと計数には時間がかかることを含めている。ABC284 Eなら Δ≤10\Delta\leq10、L=106L=10^6 なので、この二つの制約が探索量を抑える。最大次数だけでは、深い探索木の全節点数は抑えられない。

used は O(N)O(N)、path と再帰スタックは深さ分の O(N)O(N)、隣接リストは O(N+M)O(N+M) なので、全空間は O(N+M)O(N+M) である。経路を数えるたびに頂点列全体をコピー・出力すれば、その長さに比例する追加時間も必要になる。深い経路では言語の再帰スタックが不足するため、明示的なスタックを使う場合は、頂点に加えて「次に調べる隣接要素の位置」を保存し、子から戻った後の走査と復元を再現する。

配列を毎回コピーする方式では、長さ NN の使用配列のコピーだけで O(NR)O(NR) 時間が必要になる。同時に残る呼び出しの深さを DD とすると、コピーを各呼び出しが保持する追加空間も O(ND)O(ND) になる。元へ戻す方式が節約するのは、この履歴ごとの複製である。

集合をbitmaskで表して子へ値渡しする実装も可能である。これは状態の表現を変えるもので、経路をどの順に列挙するかは同じバックトラックでよい。一方、終点と使用集合が等しい複数の履歴をまとめて計算する方法は部分集合DPの領域になる。小例の二つの経路のように、使用集合が違うものを終点だけでまとめることはできない。

主配置のABC284 Eでは、「経路と探索木の節点の対応」「復帰時の使用状態の解除」「上限到達後の打ち切り」を結び付けて確認しよう。関連するABC419 Gでは、グラフの構造から候補数を抑える議論へ進む。バックトラックを見つけた後も、なぜ探索木を最後まで、または答えが確定するところまでたどれるのかを別に示すことが、次の問題でも必要になる。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。再帰と訪問済み管理を使い、選択と取り消しが対応する探索を実装する。

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

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-backtracking-search

習得する技能

  • 元のグラフの頂点と、選択履歴を表す探索木の節点を区別する。
  • 現在の経路に対する使用状態を定義し、選択と取り消しによって不変条件を保つ。
  • 枝刈りと探索全体の打ち切りを、答えの要求に応じて正当化する。
  • 探索木で実際に訪れる節点数と、節点ごとの処理費用から全体を評価する。

前提と範囲

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

直接の前提単元: なし。

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

再帰へ入る直前に局所選択を反映し、復帰時に必ずundoして現在pathだけの制約を保ちながら探索木を列挙する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • backtracking・可逆な探索状態の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠