.svg)
ClassiqエンジンII：エレクトリック・ブーガルー、あるいは、「干し草の山から針を探す」方法
前回のClassiqエンジンのブログでは、エンジンが何をしているか、そしてそれがどのように機能しているかという、バックトラッキングアルゴリズムについて簡単に紹介しました。今回は、CSP（制約充足問題）解法の世界にさらに踏み込んでみましょう。バックトラッキングアルゴリズムはCSPを解く非常にシンプルな方法ですが、全ての探索空間を調べる必要があり、かつその探索空間は非常に巨大なため（最良のケースでも指数関数的に増加します）、多くのCSPでは現実的ではありません。前回のブログで触れた数独の例をもう一度見てみましょう。数独のマスを埋める方法は9^81通りもあり、これはおおよそ、2e77（2の後に77個の0が続く数）に相当します。マスの半分がすでに埋まっている簡単な例で考えても、約1.5e38通りの選択肢が残っています。それらをすべて確認するのは、あまりに時間がかかりすぎます。
このブログでは、バックトラッキングアルゴリズムを改良する方法、言い換えれば、干し草の山から針を効率的に探す方法について説明していきます。
はじめに
このブログでは「バックトラッキング」という単語が頻出しますが、まだその意味さえ説明していませんでした。まずはそこから始めましょう（失礼しました！）。 CSP（制約充足問題）は変数の集合として定義され、各変数には有効な値のドメインが割り当てられます。また、これらの変数に対しては特定の制約が設定されます。すべての制約を満たすようにすべての変数に値を割り当てることが、CSPの「有効な解」となります。バックトラッキングアルゴリズムは、各変数に順次値を割り当てることで段階的に有効な解を導き出す方法です。各割り当て後に、少なくとも一部の制約が満たされているかどうかを確認します。もしある制約が満たされなくなった場合、現在の部分解は行き詰まりとみなされます。そこでバックトラック（戻る）し、最後に割り当てた変数に別の値を再度割り当てるのです。有効な値が残っていない場合は、さらに戻って前の変数に戻り再度割り当てを行います。すべての変数が割り当てされ、すべての制約が満たされた状態になれば、有効な解が見つかったことになります。一方、すべての選択肢を試しても解が見つからなければ、解が存在しないということになります。注意深く見ていれば、このアルゴリズムはある種の賢いやり方であると気づくでしょう。それはつまり、ある制約がもはや満たされないと認識した瞬間に探索を止める点です。もしかしたら当たり前のように聞こえるかもしれません。確かに、数独を解いていてエラーを見つけたら、誰でも解き続けるのではなくすぐに修正しようとしますよね。実はこの単純なことが探索空間のサイズの大幅な縮小につながるのです。探索が無駄であると事前に判断できれば、探索を続ける必要はありません。この考え方については、あとでまた説明したいと思います。また、バックトラッキングで行う「賢い」ことの多くは、一見すると当たり前に思えるかもしれない点にも触れておきましょう。なぜならこれは、同じ問題を手作業で解いている人の頭の中の思考プロセスを模倣してみることが、アイデアを生み出す一つの方法だからです。私たちの脳は、今でも最高のコンピューターなのです。
秩序立てた検索方法
上記を念頭に置いて、数独を解く人の思考プロセスを模倣してみましょう。部分的に埋められた数独のマスを考えるとき、あなたは次に埋めるマスをどのように探すでしょうか？全体が空白の列を探すのか、それとも5つの数字が入っている列と4つの数字が入った行が交差する場所を探すのか？もちろん、後者ですよね。数独を解くときは、自然と多くの手がかり（埋まったマス）に目を向けます。ですから、コンピューターにも同じことをさせるのが妥当でしょう。CSP解決では、これを「順序ヒューリスティックス」と呼びます。バックトラッキングアルゴリズムを説明する際に、暗黙的に2つのケースを挙げました。次にどの変数を割り当てるか、そしてどの値を割り当てるかの選択です。これらの選択をどのように行うかは私たち次第です。この選択に役立つヒューリスティックスを実装することで、最適な選択をする可能性を高めます。これらのヒューリスティックスは、有効な解がすぐに見つかることを保証するものではありませんが、問題を解くために貪欲法を実装し、より早く有効な解を見つける可能性を高めます。一方でバックトラッキングアルゴリズム自体は全ての可能性を網羅的に調べることを保証します。私たちの数独の例は、「残り最小値ヒューリスティック（LRV）」の変種と見ることができます。この方法では、まず有効な値の数が最も少ない変数に値を割り当てようとします。こうした変数は問題解決の難所になりやすいので、最初に取り組むのが効果的です。
さて、量子回路についてはまだ話していませんでした。前回のブログで述べたように、Classiqエンジンは回路内の異なる機能にリソースを割り当てています。どの順序でリソースを割り当てるべきでしょうか？1つの自然な答えは、回路のトポロジカル順序です。つまり、ある関数が他の関数より先に適用されるべきであれば、その関数のリソースも先に割り当てるべきということです。この順序でリソースを割り当てる必要はありませんが、制約が満たされなくなった状況をエンジンが特定しやすくなるため、良いヒューリスティックになるといえます。もし、2つの関数がどちらの順序でも適用可能な場合はどうでしょうか？ここでは、必ずしも自然に導き出せる答えがあるとは限りません。しかし、もう1つのよく使われるヒューリスティック、すなわち「最制約的変数（MCV）ヒューリスティック」を活用することができます。これは、残りの変数に最も多くの制約を課す変数を選択するというものです。この場合、最も多くのリソースを必要とする関数が該当します。値の順序の決定についてはどうでしょうか？そのための一般的なヒューリスティクスの1つに、最小制約値（LCV）ヒューリスティクスがあります。これは、変数に割り当てた際に他の変数の値の選択肢が最も少なくなる値を選ぶというものです。例えば、限られた数の量子ビットで回路を合成しようとしている場合、まず少ない量子ビットを関数に割り当てようとします（次の関数に多くの量子ビットを残しておくため）。これも一見当たり前に思えるかもしれませんが、明示的に指示しない限りアルゴリズムには理解できないことです。
早ければ早い方が良い
先に、1つの制約が満たされなくなった時点で探索を停止すべきと述べましたが、この考えをさらに大きく発展させることができます。例えば、1〜8の数字で列を埋めたが、最後に残ったマスの行にすでに9が入っている場合など、制約が満たされないことが簡単にわかることがあります。しかし、時にはもっと深い思考が必要な場合があります。例えば、列に残っている3つのマスがあり、欠けている2つの数字が同じマスに入らなければならない場合、これは一見してわかるわけではありませんが、よく考えれば、この制約は満たされないと判断できます。このようなアイデアをCSP解法に実装する方法は様々あります。最初に紹介するのは「フォワードチェック」です。フォワードチェックでは、各変数に残っている有効な値を追跡します（これは、先ほど触れた順序ヒューリスティックスの実装にも使用できます）。数独を解こうとして行き詰まったとき、マスの隅にすべての可能な値を書き込むようなやり方をすることがありますが、まさにその考え方です。すべての割り当ての後に残っている有効な値を確認し、関連する制約を調べて無効になった値を取り除きます。有効な値が1つも残っていない場合は、すぐにバックトラックできます。つまり、この割り当ては有効な解には至らないことがわかります。しかし、この方法だけでは十分ではありません。すべてのマスには少なくとも1つの有効な値があるため、上記の例では解決できません。ここで必要なのは「アーク整合」です。アーク整合では、単一の変数ではなく、同じ制約に関連する変数のペアを見ます。共有された制約を満たすために、その変数とペアにできるもう1つの有効な変数の値があるかをチェックします。もし見つからなければ、明らかにその値は無効です。つまりその値を選択しても、その共通の制約を満たすことはできないのです。だんだんややこしくなってきましたね。人間の頭の中では当たり前に行っているようなことが、アルゴリズムに変換するには一手間かかることがあるのです。しかも、これで終わりではありません。経路整合は3つの変数の組み合わせをチェックし、k整合はk個の変数の組み合わせをチェックすることになります！これらはかなり複雑ですが、基本的な前提は変わりません。つまり、この部分的な解が行き詰まりであることが早く分かれば分かるほど良いのです。
これらは時間の節約になるのか？
これまでに説明した方法は、どれも相当な計算を必要とします。この非常に長い探索の途中で何度もこれらの操作を繰り返すと、ランタイムが悪化する可能性はあるでしょうか？最悪の場合、答えは「YES」です。すべての計算が無駄になり、アルゴリズムが可能なすべての解をランダムな順序で試していれば良かったというケースもあるかもしれません。しかし、実際にはこれらの余分な計算はほとんどの場合、非常に有益です。CSP解決で扱う問題は、その最良のケースでも指数関数的なサイズであるため、探索する必要がない部分空間があることは大きな利点です。もし計算が多項式時間なものであれば、広範な探索よりも計算を実行する方が常に良い結果になるでしょう。
これで終わり？
いいえ、まだ終わりではありません。
CSPソルバーに終わりはありません。常に新しいヒューリスティックスを見つけたり、実装を改良してランタイムを数パーセント削減する方法が存在します。また、バックジャンプや制約学習のようなさらに複雑な技術もあります。Classiqエンジンがより複雑な回路をさらに高速合成できるようにするための改良競争に終わりはありません。
1 これは私がプログラミング初心者の人たちにいつも言っていることなのですが、コンピューターは非常に「おバカ」で、ただ言われた通りに正確に実行するだけの存在です。私たちがコンピューターを使う唯一の理由は、人間よりもはるかに速く処理ができるからです。バックトラッキングはその良い例でしょう。
2LRV、MCV、LCV。コンピューターサイエンスの略語は非常に紛らわしいものですね。
前回のClassiqエンジンのブログでは、エンジンが何をしているか、そしてそれがどのように機能しているかという、バックトラッキングアルゴリズムについて簡単に紹介しました。今回は、CSP（制約充足問題）解法の世界にさらに踏み込んでみましょう。バックトラッキングアルゴリズムはCSPを解く非常にシンプルな方法ですが、全ての探索空間を調べる必要があり、かつその探索空間は非常に巨大なため（最良のケースでも指数関数的に増加します）、多くのCSPでは現実的ではありません。前回のブログで触れた数独の例をもう一度見てみましょう。数独のマスを埋める方法は9^81通りもあり、これはおおよそ、2e77（2の後に77個の0が続く数）に相当します。マスの半分がすでに埋まっている簡単な例で考えても、約1.5e38通りの選択肢が残っています。それらをすべて確認するのは、あまりに時間がかかりすぎます。
このブログでは、バックトラッキングアルゴリズムを改良する方法、言い換えれば、干し草の山から針を効率的に探す方法について説明していきます。
はじめに
このブログでは「バックトラッキング」という単語が頻出しますが、まだその意味さえ説明していませんでした。まずはそこから始めましょう（失礼しました！）。 CSP（制約充足問題）は変数の集合として定義され、各変数には有効な値のドメインが割り当てられます。また、これらの変数に対しては特定の制約が設定されます。すべての制約を満たすようにすべての変数に値を割り当てることが、CSPの「有効な解」となります。バックトラッキングアルゴリズムは、各変数に順次値を割り当てることで段階的に有効な解を導き出す方法です。各割り当て後に、少なくとも一部の制約が満たされているかどうかを確認します。もしある制約が満たされなくなった場合、現在の部分解は行き詰まりとみなされます。そこでバックトラック（戻る）し、最後に割り当てた変数に別の値を再度割り当てるのです。有効な値が残っていない場合は、さらに戻って前の変数に戻り再度割り当てを行います。すべての変数が割り当てされ、すべての制約が満たされた状態になれば、有効な解が見つかったことになります。一方、すべての選択肢を試しても解が見つからなければ、解が存在しないということになります。注意深く見ていれば、このアルゴリズムはある種の賢いやり方であると気づくでしょう。それはつまり、ある制約がもはや満たされないと認識した瞬間に探索を止める点です。もしかしたら当たり前のように聞こえるかもしれません。確かに、数独を解いていてエラーを見つけたら、誰でも解き続けるのではなくすぐに修正しようとしますよね。実はこの単純なことが探索空間のサイズの大幅な縮小につながるのです。探索が無駄であると事前に判断できれば、探索を続ける必要はありません。この考え方については、あとでまた説明したいと思います。また、バックトラッキングで行う「賢い」ことの多くは、一見すると当たり前に思えるかもしれない点にも触れておきましょう。なぜならこれは、同じ問題を手作業で解いている人の頭の中の思考プロセスを模倣してみることが、アイデアを生み出す一つの方法だからです。私たちの脳は、今でも最高のコンピューターなのです。
秩序立てた検索方法
上記を念頭に置いて、数独を解く人の思考プロセスを模倣してみましょう。部分的に埋められた数独のマスを考えるとき、あなたは次に埋めるマスをどのように探すでしょうか？全体が空白の列を探すのか、それとも5つの数字が入っている列と4つの数字が入った行が交差する場所を探すのか？もちろん、後者ですよね。数独を解くときは、自然と多くの手がかり（埋まったマス）に目を向けます。ですから、コンピューターにも同じことをさせるのが妥当でしょう。CSP解決では、これを「順序ヒューリスティックス」と呼びます。バックトラッキングアルゴリズムを説明する際に、暗黙的に2つのケースを挙げました。次にどの変数を割り当てるか、そしてどの値を割り当てるかの選択です。これらの選択をどのように行うかは私たち次第です。この選択に役立つヒューリスティックスを実装することで、最適な選択をする可能性を高めます。これらのヒューリスティックスは、有効な解がすぐに見つかることを保証するものではありませんが、問題を解くために貪欲法を実装し、より早く有効な解を見つける可能性を高めます。一方でバックトラッキングアルゴリズム自体は全ての可能性を網羅的に調べることを保証します。私たちの数独の例は、「残り最小値ヒューリスティック（LRV）」の変種と見ることができます。この方法では、まず有効な値の数が最も少ない変数に値を割り当てようとします。こうした変数は問題解決の難所になりやすいので、最初に取り組むのが効果的です。
さて、量子回路についてはまだ話していませんでした。前回のブログで述べたように、Classiqエンジンは回路内の異なる機能にリソースを割り当てています。どの順序でリソースを割り当てるべきでしょうか？1つの自然な答えは、回路のトポロジカル順序です。つまり、ある関数が他の関数より先に適用されるべきであれば、その関数のリソースも先に割り当てるべきということです。この順序でリソースを割り当てる必要はありませんが、制約が満たされなくなった状況をエンジンが特定しやすくなるため、良いヒューリスティックになるといえます。もし、2つの関数がどちらの順序でも適用可能な場合はどうでしょうか？ここでは、必ずしも自然に導き出せる答えがあるとは限りません。しかし、もう1つのよく使われるヒューリスティック、すなわち「最制約的変数（MCV）ヒューリスティック」を活用することができます。これは、残りの変数に最も多くの制約を課す変数を選択するというものです。この場合、最も多くのリソースを必要とする関数が該当します。値の順序の決定についてはどうでしょうか？そのための一般的なヒューリスティクスの1つに、最小制約値（LCV）ヒューリスティクスがあります。これは、変数に割り当てた際に他の変数の値の選択肢が最も少なくなる値を選ぶというものです。例えば、限られた数の量子ビットで回路を合成しようとしている場合、まず少ない量子ビットを関数に割り当てようとします（次の関数に多くの量子ビットを残しておくため）。これも一見当たり前に思えるかもしれませんが、明示的に指示しない限りアルゴリズムには理解できないことです。
早ければ早い方が良い
先に、1つの制約が満たされなくなった時点で探索を停止すべきと述べましたが、この考えをさらに大きく発展させることができます。例えば、1〜8の数字で列を埋めたが、最後に残ったマスの行にすでに9が入っている場合など、制約が満たされないことが簡単にわかることがあります。しかし、時にはもっと深い思考が必要な場合があります。例えば、列に残っている3つのマスがあり、欠けている2つの数字が同じマスに入らなければならない場合、これは一見してわかるわけではありませんが、よく考えれば、この制約は満たされないと判断できます。このようなアイデアをCSP解法に実装する方法は様々あります。最初に紹介するのは「フォワードチェック」です。フォワードチェックでは、各変数に残っている有効な値を追跡します（これは、先ほど触れた順序ヒューリスティックスの実装にも使用できます）。数独を解こうとして行き詰まったとき、マスの隅にすべての可能な値を書き込むようなやり方をすることがありますが、まさにその考え方です。すべての割り当ての後に残っている有効な値を確認し、関連する制約を調べて無効になった値を取り除きます。有効な値が1つも残っていない場合は、すぐにバックトラックできます。つまり、この割り当ては有効な解には至らないことがわかります。しかし、この方法だけでは十分ではありません。すべてのマスには少なくとも1つの有効な値があるため、上記の例では解決できません。ここで必要なのは「アーク整合」です。アーク整合では、単一の変数ではなく、同じ制約に関連する変数のペアを見ます。共有された制約を満たすために、その変数とペアにできるもう1つの有効な変数の値があるかをチェックします。もし見つからなければ、明らかにその値は無効です。つまりその値を選択しても、その共通の制約を満たすことはできないのです。だんだんややこしくなってきましたね。人間の頭の中では当たり前に行っているようなことが、アルゴリズムに変換するには一手間かかることがあるのです。しかも、これで終わりではありません。経路整合は3つの変数の組み合わせをチェックし、k整合はk個の変数の組み合わせをチェックすることになります！これらはかなり複雑ですが、基本的な前提は変わりません。つまり、この部分的な解が行き詰まりであることが早く分かれば分かるほど良いのです。
これらは時間の節約になるのか？
これまでに説明した方法は、どれも相当な計算を必要とします。この非常に長い探索の途中で何度もこれらの操作を繰り返すと、ランタイムが悪化する可能性はあるでしょうか？最悪の場合、答えは「YES」です。すべての計算が無駄になり、アルゴリズムが可能なすべての解をランダムな順序で試していれば良かったというケースもあるかもしれません。しかし、実際にはこれらの余分な計算はほとんどの場合、非常に有益です。CSP解決で扱う問題は、その最良のケースでも指数関数的なサイズであるため、探索する必要がない部分空間があることは大きな利点です。もし計算が多項式時間なものであれば、広範な探索よりも計算を実行する方が常に良い結果になるでしょう。
これで終わり？
いいえ、まだ終わりではありません。
CSPソルバーに終わりはありません。常に新しいヒューリスティックスを見つけたり、実装を改良してランタイムを数パーセント削減する方法が存在します。また、バックジャンプや制約学習のようなさらに複雑な技術もあります。Classiqエンジンがより複雑な回路をさらに高速合成できるようにするための改良競争に終わりはありません。
