クラシーク・エンジンII：エレクトリック・ブーガルー（あるいは、干し草の山から針を探す方法）

9月

2023

ラビッド・アロン

今回はCSP（制約充足問題）解法の世界を深堀りしてみよう。バックトラック・アルゴリズムはCSPを解く非常にシンプルな方法ですが、探索空間全体を見渡す必要があります。ほとんどのCSPでは、これは容認できない。探索空間が大きすぎる（最良のケースでは指数関数的）のだ。前の投稿で述べた数独の例をもう一度見てみよう。数独の盤面を埋める方法は9^81通りある。これは2e77（2の後に77個のゼロが続く）よりわずかに小さい。マスの半分がすでに埋まっている簡単な例で考えても、約1.5e38通りの可能性がある。
この投稿では、バックトラック・アルゴリズムをどのように改善できるか、言い換えれば、干し草の山から効率よく針を探す方法を説明します。

はじめに

バックトラックという単語はこの投稿で何度も出てくるが、まだその意味さえ言っていないので、バックトラックしよう（ごめんなさい）。
CSPは変数の集合として定義され、それぞれが有効な値のドメインを持ち、これらの変数への代入に関する制約の集合を持つ。有効な解とは、すべての制約が満たされるような、すべての変数への値の割り当てである。
バックトラックアルゴリズムは、各変数に連続して値を割り当てることで、有効な解を漸進的に構築しようとする。各代入の後、制約が（少なくともいくつかの制約について）満足されるかどうかを検証できる。ある制約が満たされなくなった場合、現在の部分解は行き詰まります。したがって、バックトラックします - 最後に代入された変数に別の値を再代入します。有効な値が残っていない場合、さらに前の変数に戻り（=バックトラック）、値を再割り当てします。
すべての変数が割り当てられ、すべての制約が満たされた状態に到達すれば、有効な解を見つけたことになります！一方、すべての選択肢を使い果たした場合は、有効な解がまったくないことを意味します。
注意していれば、アルゴリズムがすでにある種のスマートなことをしていることに気づいたかもしれません。ある制約がもはや満足できないと認識した瞬間に停止するのです。
分かっています、これは些細なことに聞こえます。確かに、数独を解いていてエラーを見つけたら、解き続けるのではなく、すぐに修正しようとする。しかし、この単純なことがすでに探索空間のサイズを大幅に縮小しているのだ。探索が無駄であると事前に言えるのであれば、探索を続ける必要はない。
また、バックトラックで行う多くの「賢い」ことは、些細なことに聞こえるかもしれないことを指摘しておきたい。それは、同じ問題を手作業で解いている人の頭の中の思考プロセスを解明することが、それらを思いつく一つの方法だからだ。私たちの脳は今でも最高のコンピューターなのだ¹。

順序よく探す

それを念頭に置いて、数独を解く人の思考プロセスを真似てみよう。一部だけ数字が埋まっている数独の盤面を考えてみよう。空いている列を見るか、4つの数字が並んでいる列を横切る5つの数字が並んでいる列を見るか。もちろん後者だ。数独を解くときは、ヒントがたくさんあるところ（つまり、ぬりつぶされたマス）を探すのが自然です。だから、コンピュータにもそうするように指示しよう！
CSP解法では、これを順序ヒューリスティックと呼ぶ。バックトラック・アルゴリズムについて説明したとき、アルゴリズムが選択を行う2つのケースについて（暗黙のうちに）言及した。どのように選択するのか？それは我々次第だ。私たちは、アルゴリズムが正しい判断を下すのを助けるヒューリスティックを実装することができる。ヒューリスティックは、有効な解がすぐに見つかることを保証するものではないことに注意してほしい。バックトラック・アルゴリズムは、すべての可能性を反復することを保証する。
数独の例は、最小残存値（LRV）ヒューリスティックのバリエーションと見なすことができる。これは、残存する有効な値の数が最小の変数に値を代入しようとするものである。
さて、今日は量子回路について説明していない。前回の記事で述べたように、Classiqエンジンは回路内の異なる機能にリソースを割り当てる。どのような順序でリソースを割り当てるのだろうか？1つの自然な答えは、回路のトポロジカルな順序である。つまり、ある関数が他の関数より先に適用されなければならない場合、その関数のリソースを先に割り当てるべきである。この順序でリソースを割り当てる必要はありませんが、制約が満たされなくなった状況をエンジンが特定しやすくなるため、良いヒューリスティックになります。
2つの関数がどちらの順序でも適用できる場合はどうなるでしょうか？ここでは、必ずしも自然な答えはありません。しかし、もう1つのよく使われるヒューリスティックを利用することができます：最制約変数（MCV）ヒューリスティックは、残りの変数に最も制約を課す変数を選択することを指示します。この場合、最もリソースを必要とする関数がそれにあたります。
値の順序を決めるのはどうでしょうか？そのための一般的な発見的手法として、最小制約値（LCV²）発見的手法があります。例えば、限られた数の量子ビットで回路を合成しようとする場合、まず関数に割り当てる量子ビットを少なくしようとします（次の関数がより多くの量子ビットを割り当てられるように）。繰り返しますが、これは私たちにとっては些細なことに聞こえるかもしれませんが、私たちが明示的に指示しなければ、アルゴリズムはその方法を知りません。

早起きは三文の得

先に、1つでも制約が満たされなくなったらすぐに探索を中止したいと述べた。この考えをさらに発展させることができる。例えば、ある列を1～8の数字で埋めたとき、最後に残ったマスの行にすでに9が入っている場合などです。ある列の残りのマスは3つだが、そのうちの2つは同じマスにあるはずだ。これはすぐには思いつかないが、十分に考えればこの制約が満足できないことがわかる。
このような考え方をCSP解法に実装する方法は様々ある。最初に説明するのは前方検査である。前方検査では、各変数に残っている有効な値を追跡します（これは、先に述べた順序ヒューリスティックの実装にも使用できることに注意してください）。もしあなたが数独を解くのに行き詰って、四角の隅にすべての可能な値を書き始めたことがあるとしたら、まさにそれです。
すべての代入の後、残りの有効な値を調べ、（関連する制約をチェックすることによって）もはや有効でない値を取り除きます。もし有効な値が残っていなければ、すぐに引き返すことができます - この代入は有効な解を導くことはできません。
しかし、この方法は上の例には十分ではありません - すべての正方形には少なくとも1つの有効な値があります。もっと洗練された方法が必要です。アーク一貫性が必要です。
アーク一貫性は、単一の変数ではなく、同じ制約の一部である変数のペアを見ます。ある値が有効であることを確認するために、共有された制約を満たすためにペアとなるもう1つの変数の有効な値があるかどうかをチェックします。もし見つからなければ、この値が無効であることは間違いない。もしその値を選ぶと、この共有制約を満たすことができない。
これは混乱してきましたね。頭の中でやっているような些細なことでも、アルゴリズムに置き換えるには多少の作業が必要になることがある。パスの一貫性は変数のトリプレットを見るのに対して、k-一貫性は変数のkタプルを見ます！これらは非常に複雑だが、前提は変わらない：この部分解が行き止まりであることを早く見つけるほど良いのだ。

その価値はいつあるのか？

これまで述べてきたすべての方法は、自明ではない計算を必要とする。すでに非常に長い探索の途中で、これらを繰り返し実行することは、実行時間の低下を引き起こすのだろうか？最悪の場合、答えはイエスだ。すべての計算が無駄になり、アルゴリズムがすべての可能な解をランダムな順序で試したのと同じようになるようなエッジケースを作ることはできるでしょう。しかし実際には、余分な計算を行うことはほとんど常に有益なのだ。CSP解法で扱う問題は、せいぜい指数関数的な大きさなので、探索する必要のない部分空間は大きな利点となる。もし計算が多項式であれば、より広範な探索を行うよりも、常に計算を行った方が良いだろう。

これでいいのか？

いや。

CSPソルバーに終わりはない。常に新しいヒューリスティックを見つけたり、実装を改良して実行時間を数パーセント短縮することができる。バックジャンプや制約学習のようなさらに複雑なテクニックもある。
Classiqエンジンがより複雑な回路をより高速に合成できるようにするための改良競争には終わりがありません。

‍

1 これは私がいつもプログラミング初心者の人たちに言っていることなんだけど、コンピュータはかなりバカで、言われたことをそのままやるだけなんだ。コンピュータを使う唯一の理由は、人間よりはるかに速く処理できるからだ。バックトラックはその好例だ。

²LRV、MCV、LCV。そう、コンピューター・サイエンスの略語は地獄のように混乱させることがある。