# Exhaustive Solverの使い方 :::{container} prog-cpp **Exhaustive Solver**はQUBO/HUBO式のための完全探索ソルバーです. すべての可能な割り当てが検査されるため,解の最適性が保証されます. 探索はCPUスレッドを使用して並列化され,CUDA GPUが利用可能な場合は,探索をさらに高速化するためにGPUアクセラレーションが自動的に有効になります. Exhaustive Solverを使って問題を解くには,以下の2つのステップで行います： 1. Exhaustive Solver（`qbpp::ExhaustiveSolver`）オブジェクトを作成します. 2. `search()` メンバ関数を呼び出します.パラメータは初期化子リストとして渡すことができます. ## Exhaustive Solverオブジェクトの作成 Exhaustive Solverを使用するには,式（`qbpp::Expr`）オブジェクトを引数としてExhaustive Solverオブジェクト（`qbpp::ExhaustiveSolver`）を以下のように構築します： - **`qbpp::ExhaustiveSolver(const qbpp::Expr& f)`**: ここで,`f` は解くべき式です. 事前に `simplify_as_binary()` 関数を呼び出してバイナリ式として簡約化しておく必要があります. この関数は与えられた式 `f` を解探索中に使用される内部フォーマットに変換します. ## パラメータの設定 探索パラメータは `search()` に初期化子リストとして直接渡します. 以下のパラメータが利用可能です： | パラメータ | 値 | 説明 | |---|---|---| | `target_energy` | エネルギー文字列 | 早期終了のためのターゲットエネルギー値を設定します.ソルバーがターゲット以下のエネルギーを持つ解を見つけると,探索は直ちに終了します. | | `verbose` | `"1"` or `"true"` | 探索の進捗をパーセンテージで表示します.総実行時間の推定に役立ちます. | | `enable_default_callback` | `"1"` or `"true"` | 新たに得られた最良解を出力するデフォルトコールバック関数を有効にします. | | `topk_sols` | 整数文字列 | 最小エネルギーのtop-k解を収集します. | | `best_energy_sols` | `"0"` | 最適解（最小エネルギーの解）を収集します.値は保持する最大数で,`0` は無制限（すべて収集）. | | `all_sols` | `"1"` or `"true"` | すべての $2^n$ 個の解を収集します. | ## 解の探索 - **`search()`**: 見つかった最良解を返します（パラメータなし）.CUDA GPUが利用可能な場合,CPUスレッドと並行してGPUを使用した探索の高速化が自動的に行われます. - **`search(params)`**: `Sol` オブジェクトを返します.`topk_sols`,`best_energy_sols`,`all_sols` が設定されている場合,収集された解は `sol.sols` でエネルギーの昇順にアクセスできます. # プログラム例 以下のプログラムは,Exhaustive Solverを使用して**Low Autocorrelation Binary Sequences (LABS)**問題の解を探索します： ```{literalinclude} /../programFiles/cppPrograms/solver/exhaustive-solver-usage-program1.cpp :language: cpp :caption: exhaustive-solver-usage-program1.cpp ``` このプログラムの出力は以下のとおりです： ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` すべての最適解は `best_energy_sols` を設定することで取得できます： ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 出力は以下のとおりです： ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 最小エネルギーのtop-k解は `topk_sols` を設定することで取得できます： ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 出力は以下のとおりです： ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` さらに,非最適解を含むすべての解は `all_sols` を設定することで取得できます. すべての $2^n$ 個の解をメモリに格納することに注意してください.ここで $n$ は変数の数です. 例えば,$n = 20$ の場合,100万個以上の解が格納され,メモリ使用量は $n$ に対して指数的に増加します. $n$ が十分小さい場合にのみ使用してください. ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 以下に示すように,すべての $2^{20}$ 個の解がエネルギーの昇順で出力されます： ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` ::: :::{container} prog-python **Exhaustive Solver**はQUBO/HUBO式のための完全探索ソルバーです. すべての可能な割り当てが検査されるため,解の最適性が保証されます. 探索はCPUスレッドを使用して並列化され,CUDA GPUが利用可能な場合は,探索をさらに高速化するためにGPUアクセラレーションが自動的に有効になります. Exhaustive Solverを使って問題を解くには,以下の2つのステップで行います: 1. Exhaustive Solver（`qbpp.ExhaustiveSolver`）オブジェクトを作成します. 2. `search()` メソッドを呼び出します.パラメータはキーワード引数として渡すことができます. ## Exhaustive Solverオブジェクトの作成 Exhaustive Solverを使用するには,式を引数としてExhaustive Solverオブジェクト（`qbpp.ExhaustiveSolver`）を以下のように構築します: - **`qbpp.ExhaustiveSolver(f)`** ここで,`f` は解くべき式です. 事前に `simplify_as_binary()` メソッドを呼び出してバイナリ式として簡約化しておく必要があります. コンストラクタは式をホストメモリにロードし,利用可能な GPU がある場合はデバイスメモリにも転送します.以降 `search()` を複数回呼び出してもこのロードは1度きりなので,同じ式に対して繰り返し探索する際のオーバーヘッドがありません. ## 探索パラメータの設定 探索パラメータは `search()` メソッドにキーワード引数として直接渡します. 以下のパラメータが利用可能です: | パラメータ | 型 | 説明 | デフォルト | |---|---|---|---| | `target_energy` | int | 早期終了のためのターゲットエネルギー値を設定します.ソルバーがこの値以下のエネルギーを持つ解を見つけると,探索は直ちに終了します. | (なし) | | `verbose` | int (0 または 1) | `1` に設定すると,探索の進捗をパーセンテージで表示します.総実行時間の推定に役立ちます. | `0` | | `enable_default_callback` | int (0 または 1) | `1` に設定すると,新たに得られた最良解のエネルギーと TTS を表示するデフォルトコールバック関数を有効にします. | `0` | | `topk_sols` | int | 最小エネルギーの top-k 解を収集します. | (無効) | | `best_energy_sols` | int | 最適解（最小エネルギーの解）を収集します.値は保持する最大数で,`0` は無制限（すべて収集）. | (無効) | | `all_sols` | int (0 または 1) | `1` に設定すると,すべての $2^n$ 個の解を収集します.メモリ使用量は変数数 `n` に対して指数的に増加するため,`n` が十分小さい場合にのみ使用してください. | (無効) | パラメータは `search()` にキーワード引数として渡します: ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 未知のパラメータキーを指定すると実行時エラーになります. ## 解の探索 Exhaustive Solver は **`search()`** メソッドを呼び出して解を探索します.パラメータはキーワード引数として渡せます. このメソッドは見つかった最良解を返します. CUDA GPU が利用可能な場合,CPU スレッドと並行して GPU を使用した探索の高速化が自動的に行われます. 返される解は `sol.energy`（エネルギー値）,`sol(x)`（変数値の取得）,`sol.info`（ソルバー情報の辞書）などを提供します.詳細は [QR_SOLUTION](../quickReference/qr-solution.md) を参照してください. `topk_sols`,`best_energy_sols`,`all_sols` が設定されている場合,`search()` が返す解には収集された解も含まれます. 以下のプロパティと操作で取得できます: - **`sol.sols`**: エネルギーの昇順にソートされた解のリスト. - **`sol.sols`**: 格納されている解のリスト（エネルギーの昇順）. - **`sol.sols[i]`**: `i` 番目の解を返します. - **`len(sol.sols)`**: 格納されている解の個数. ## プログラム例 以下のプログラムは,Exhaustive Solverを使用して**Low Autocorrelation Binary Sequences (LABS)**問題の解を探索します: ```{literalinclude} /../programFiles/pythonPrograms/solver/exhaustive-solver-usage-program1.py :language: python :caption: exhaustive-solver-usage-program1.py ``` このプログラムの出力は以下のとおりです: ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` すべての最適解は `best_energy_sols` を設定することで取得できます: ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 出力は以下のとおりです: ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 最小エネルギーのtop-k解は `topk_sols` を設定することで取得できます: ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 出力は以下のとおりです: ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` さらに,非最適解を含むすべての解は `all_sols` を設定することで取得できます. すべての $2^n$ 個の解をメモリに格納することに注意してください.ここで $n$ は変数の数です. 例えば,$n = 20$ の場合,100万個以上の解が格納され,メモリ使用量は $n$ に対して指数的に増加します. $n$ が十分小さい場合にのみ使用してください. ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` 以下に示すように,すべての $2^{20}$ 個の解がエネルギーの昇順で出力されます: ```{include} /../programFiles/markDown/solver/exhaustive-solver-usage.md :start-after: :end-before: ``` :::