網羅的ソルバーの使用方法

網羅的ソルバーは、QUBO/HUBO式に対する完全探索型ソルバーです。すべての可能な割り当てが検討されるため、解の最適性が保証されます。

網羅的ソルバーによる問題解決は、以下の3つのステップで構成されます：

網羅的ソルバー（または qbpp::exhaustive_solver::ExhaustiveSolver) オブジェクトを作成する。
ソルバーオブジェクトのメンバ関数を呼び出して検索オプションを設定する。
検索メンバー関数のいずれかを呼び出して解を検索する。

網羅的ソルバーオブジェクトの作成

網羅的ソルバーを使用するには、網羅的ソルバーオブジェクト（または qbpp::exhaustive_solver::ExhaustiveSolver)は、式 (or qbpp::Expr) オブジェクトを次のように構築します:

qbpp::exhaustive_solver::ExhaustiveSolver(const qbpp::Expr& f): ここで、 f は解くべき式である。事前に simplify_as_binary() 関数を呼び出して二項式として簡略化しておく必要がある。この関数は、与えられた式を f を内部形式に変換し、解の探索中に使用されます。

網羅的ソルバーオプションの設定

enable_default_callback() デフォルトのコールバック関数を有効化します。これにより新たに得られた最適解が出力されます。

解の探索

網羅的ソルバーは、ソルバーオブジェクトの以下のメンバ関数のいずれかを呼び出して解を検索します:

search(): 見つかった最初の最適解を返します。
search_optimal_solutions(): すべての最適解を含むベクトルを返します。
search_all_solutions(): エネルギーの昇順でソートされた全解を含むベクトルを返します。

プログラム例

以下のプログラムは、網羅的ソルバーを用いて 低自己相関二値列(LABS)問題の解を検索します:

#include "qbpp.hpp"
#include "qbpp_exhaustive_solver.hpp"

int main() {
  size_t size = 20;
  auto x = qbpp::var("x", size);
  auto f = qbpp::expr();
  for (size_t d = 1; d < size; ++d) {
    auto temp = qbpp::expr();
    for (size_t i = 0; i < size - d; ++i) {
      temp += (2 * x[i] - 1) * (2 * x[i + d] - 1);
    }
    f += qbpp::sqr(temp);
  }
  f.simplify_as_binary();

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  solver.enable_default_callback();
  auto sol = solver.search();
  std::cout << sol.energy() << ": ";
  for (auto val : sol(x)) {
    std::cout << (val == 0 ? "-" : "+");
  }
  std::cout << std::endl;
}

このプログラムの出力は以下の通りです:

TTS = 0.000s Energy = 1506
TTS = 0.000s Energy = 1030
TTS = 0.000s Energy = 502
TTS = 0.000s Energy = 446
TTS = 0.000s Energy = 234
TTS = 0.000s Energy = 110
TTS = 0.001s Energy = 106
TTS = 0.001s Energy = 74
TTS = 0.001s Energy = 66
TTS = 0.001s Energy = 42
TTS = 0.001s Energy = 34
TTS = 0.004s Energy = 26
26: --++-++----+----+-+-

すべての最適解は、以下の search_optimal_solutions()メンバー関数を呼び出すことで取得できます:

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  auto sols = solver.search_optimal_solutions();
  for (const auto& sol : sols) {
    std::cout << sol.energy() << ": ";
    for (auto val : sol(x)) {
      std::cout << (val == 0 ? "-" : "+");
    }
    std::cout << std::endl;
  }

出力は以下の通りです:

26: -----+-+++-+--+++--+
26: --++-++----+----+-+-
26: -+-+----+----++-++--
26: -++---++-+---+-+++++
26: +--+++--+-+++-+-----
26: +-+-++++-++++--+--++
26: ++--+--++++-++++-+-+

さらに、非最適解を含む全ての解は、以下のsearch_all_solutions()メンバー関数を呼び出すことで取得できます:

  auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f);
  solver.enable_default_callback();
  auto sols = solver.search_optimal_solutions();
  for (const auto& sol : sols) {
    std::cout << sol.energy() << ": ";
    for (auto val : sol(x)) {
      std::cout << (val == 0 ? "-" : "+");
    }
    std::cout << std::endl;
  }

このプログラムは、以下の通りエネルギーの昇順で全 $2^{20}$ 個の解を出力します:

26: -----+-+++-+--+++--+
26: --++-++----+----+-+-
26: -+-+----+----++-++--
26: -++---++-+---+-+++++
26: +--+++--+-+++-+-----
26: +-+-++++-++++--+--++
26: ++--+--++++-++++-+-+
26: +++++-+---+-++---++-
34: -----+-+--+-++--++--
34: ----+----++-++---+-+
34: ----+--+++--+-+++-+-
34: ---+++-+-+----+--+--
34: ---+++++-+++-++-+-++
34: --+--+----+-+-+++---
34: --+-+--+---+-----+++
34: --++--++-+--+-+-----
34: -+--+------+-+++---+
34: -+--+-+---+---+++++-
[omitted]

最終更新日: 2025.12.26