ClassiqエンジンII：干し草の山から針を探す

Classiqエンジンに関する前回のブログでは、エンジンが何をしているか、そしてこれがどのように機能しているかという、バックトラッキングアルゴリズムについて簡単に紹介しました。今回は、CSP（制約充足問題）解法の世界にさらに踏み込んでみましょう。バックトラッキングアルゴリズムはCSPを解く非常にシンプルな方法である一方、全ての探索空間を調べる必要があり、かつその探索空間は非常に巨大なため（ベストケースでも指数関数的に増加）、多くのCSPにおいて現実的ではありません。前回のブログで触れた数独の例をもう一度見てみましょう。数独のマスを埋める方法は9^81通りもあり、これはおおよそ、2e77（2の後に77個の0が続く数）に相当します。マスの半分がすでに埋まっているとしても、まだ約1.5e38通りの選択肢が残るわけで、それらすべてを確認するのは、あまりに多くの時間がかかります。
このブログでは、バックトラッキングアルゴリズムを改良する方法、言い換えれば、干し草の山から針を効率的に探す方法について説明していきます。

はじめに

このブログでは「バックトラッキング」という単語が頻出しますが、まずはこの意味を説明することから始めます。 CSPは変数の集合として定義され、各変数には有効な値のドメインが割り当てられます。また、これらの変数に対しては特定の制約が設定されます。すべての制約を満たすようにすべての変数に値を割り当てることが、CSPの「有効な解」となります。
バックトラッキングアルゴリズムは、各変数に順次値を割り当てることで段階的に有効な解を導き出す方法です。各割り当て後に（少なくとも一部の）制約が満たされているかどうかを確認しますが、いずれかの制約が満たされなくなった場合、そこまでの部分解は行き詰まりとみなされます。そこでバックトラック（戻る）し、最後に割り当てた変数に別の値を再度割り当てるのです。有効な値が残っていない場合は、さらに戻って前の変数に戻り再度割り当てを行います。
すべての変数が割り当てされ、すべての制約が満たされた状態になれば、有効な解が見つかったことになります。一方で、すべての選択肢を試しても制約が満たされなければ、解は存在しないということになります。
制約が少しでも満たされないと認識した瞬間に探索を止める点で、このアルゴリズムはある種の賢いやり方であると言えます。
確かに、数独を解いていく途中でエラーを見つけたら、誰でもその場で解くことをやめて修正しようとします。実はこの単純なことが探索空間サイズの大幅な縮小につながるのです。探索が無駄であると事前に判断できれば、探索を続ける必要はありません。この考え方については、あとでまた説明したいと思います。
ここで、バックトラッキングで行う「賢いこと」の多くは、一見すると当たり前に思えるかもしれないという点にも触れておきます。なぜならこれを生み出す方法の一つが、同じ問題を人間が解く場合の思考プロセスを模倣してみることだからです。私たちの脳は、今でも最高のコンピューターなのです。

秩序立てた検索方法

以上を念頭に置いて、数独を解く人の思考プロセスを模倣してみましょう。部分的に埋められた数独のマスを考えるとき、あなたは次に埋めるマスをどのように探すでしょうか？全体が空白の列を探すのか、それとも5つの数字が入っている列と4つの数字が入った行が交差する場所を探すのかーもちろん、後者のはずです。数独を解くときは、自然と手がかり（埋まったマス）に目を向けます。ですから、コンピューターにも同じことをさせるのが妥当でしょう。
CSP解決では、これを「順序ヒューリスティックス」と呼びます。バックトラッキングアルゴリズムを説明する際に、暗黙的に2つのケースを挙げました。次にどの変数を割り当てるか、そしてどの値を割り当てるかの選択です。これらの選択をどのように行うかは私たち次第です。この選択に役立つヒューリスティックスを実装することで、最適な選択をする可能性を高めます。これらのヒューリスティックスは、有効な解がすぐに見つかることを保証するものではありませんが、問題を解くために貪欲法を実装し、より早く有効な解を見つける可能性を高めます。一方でバックトラッキングアルゴリズム自体は全ての可能性を網羅的に調べることを保証します。
数独の例は、「残り最小値ヒューリスティック（LRV）」の変種と見ることができます。この方法では、まず有効な値の数が最も少ない変数に値を割り当てようとします。こうした変数は問題解決の難所になりやすいので、最初に取り組むのが効果的です。
さて、ここからが量子回路についてです。前回のブログで述べたように、Classiqエンジンは回路内の異なる機能にリソースを割り当てています。どの順序でリソースを割り当てるべきか？これに対する自然な答えの一つが、回路のトポロジカル順序です。つまり、ある関数が他の関数より先に適用されるべきであれば、その関数のリソースも先に割り当てるべきということです。この順序でリソースを割り当てる必要はありませんが、制約が満たされなくなった状況をエンジンが特定しやすくなるため、良いヒューリスティックになるといえます。
もし、2つの関数がどちらの順序でも適用可能な場合はどうでしょうか？ここでは、必ずしも自然に導き出せる答えがあるとは限りません。しかし、よく使われるもう一つのヒューリスティック、すなわち「最制約的変数（MCV）ヒューリスティック」を活用することができます。これは、残りの変数に最も多くの制約を課す変数を選択するというものです。この場合、最も多くのリソースを必要とする関数が該当します。
値の順序の決定についてはどうでしょうか？そのための一般的なヒューリスティクスの1つに、最小制約値（LCV）ヒューリスティクスがあります。これは、変数に割り当てた際に他の変数の値の選択肢が最も少なくなる値を選ぶというものです。例えば、限られた数の量子ビットで回路を合成しようとしている場合、まず少ない量子ビットを関数に割り当てようとします（次の関数に多くの量子ビットを残しておくため）。これも一見当たり前に思えるかもしれませんが、明示的に指示しない限りアルゴリズムには理解できないことです。

早ければ早い方が良い

先ほど、制約が一つでも満たされなくなった時点で探索を停止すると述べましたが、この考えをさらに大きく発展させることができます。例えば、1〜8の数字で列を埋めたが、最後に残ったマスの行にすでに9が入っている場合など、制約が満たされないことが簡単にわかることがあります。しかし、中にはもっと深い思考を必要とする場合があります。例えば、列に残っているマスが3つあり、欠けている2つの数字が同じマスに入らなければならない場合、よく考えれば、この制約は満たされないと判断できますが一見してわかるわけではありません。
このようなアイデアをCSP解法に実装する方法が複数あります。最初に紹介するのは「フォワードチェック」です。フォワードチェックでは、各変数に残っている有効な値を追跡するやり方で、先ほど触れた順序ヒューリスティックスの実装にも使用できます。数独を解こうとして行き詰まったとき、マスの隅にすべての可能な値を書き込むようなやり方をすることがありますが、まさにその考え方です。
すべての割り当ての後に残っている有効な値を確認し、関連する制約を調べて無効になった値を取り除きます。有効な値が一つも残っていなければすぐにバックトラック、つまり、この割り当ては有効な解には至らないことになります。
ただ、この方法だけでは十分ではありません。すべてのマスには少なくとも1つの有効な値があるため、上記の例では解決できません。ここで必要なのが「アーク整合」です。
アーク整合では、単一の変数ではなく、同じ制約に関連する変数のペアを見ます。共有された制約を満たすために、その変数とペアにできる別の有効な変数値があるかチェックします。もし見つからなければ、その値は無効であるということがわかります。つまりその値を選択しても、ペアに共通する制約を満たすことはできないということです。
だいぶややこしくなってきました。人間の頭の中では当たり前に行っているようなことでも、アルゴリズムに変換するには一手間かかることがあるのです。さらに経路整合は3つの変数の組み合わせをチェックし、k整合はk個の変数の組み合わせをチェックすることになるわけです。かなり複雑ですが、基本的な前提は変わりません。つまり、部分的な解が行き詰まりであることが早く分かれば分かるほど良いのです。

これらは時間の節約になるのか？

これまでに説明した方法は、いずれも相当な計算を必要とします。この非常に長い探索の途中でこうした操作を何度も繰り返す場合に、ランタイムが悪化する可能性はあるでしょうか？最悪のケースでは、答えは「YES」です。可能なすべての解をランダムな順序で試せば良かったというように、計算が無駄になるケースもあり得ます。しかし、実際にはこれらの余分な計算はほとんどの場合、非常に有益に働きます。CSP解決で扱う問題は、うまくいくケースでも指数関数的に発散するため、探索しない部分空間があることは大きな利点です。一方で、もし計算が多項式時間なものであれば、広範な探索よりも計算を実行する方が常に良い結果になるでしょう。

これで終わり？

いいえ、まだ終わりではありません。

CSPソルバーに終わりはありません。常に新しいヒューリスティックスを見つけたり、実装を改良してランタイムを数パーセント削減する方法が探求されています。また、バックジャンプや制約学習といったさらに複雑な技術もあります。
Classiqエンジンがより複雑な回路をさらに高速合成できるようにするための改良競争に終わりはありません。