イージーソルバーの使用方法

イージーソルバーは、QUBO/HUBO式のためのヒューリスティックソルバーです。

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

イージーソルバー（または qbpp::easy_solver::EasySolver) オブジェクトを作成する。
ソルバーオブジェクトのメンバ関数を呼び出して探索オプションを設定する。
member関数を呼び出して解を検索する search() メンバー関数を呼び出して解を検索します。この関数は解（または qbpp::Solオブジェクトを返します。

Easy Solver オブジェクトの作成

イージーソルバーを使用するには、イージーソルバーオブジェクト（または qbpp::easy_solver::EasySolver)を構築します。 qbpp::Expr）オブジェクトを用いて以下のように構築します：

qbpp::easy_solver::EasySolver(const qbpp::Expr& f)

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

Easy Solver オプションの設定

作成されたイージーソルバーオブジェクトに対して、以下のメンバ関数を指定できます：

time_limit(double time): 秒単位の時間制限を指定します。経過時間が指定値に達すると、Easy Solver は探索を終了します。デフォルト値は 10.0 秒です。時間制限を 0 に設定した場合、時間制限による探索終了は発生しません。
target_energy(energy_t energy) 目標エネルギーを指定します。エネルギーが指定値以下となる解が見つかった場合、イージーソルバーは探索を終了します。
enable_default_callback() デフォルトのコールバック関数を有効化します。これにより、新たに得られた最良解が出力されます。

解の探索

Easy Solver は、Easy Solver オブジェクトsearch()のメンバ関数を呼び出すだけで解を検索します。

プログラム例

以下のプログラムは、イージーソルバーを用いて低自己相関二値列（LABS）問題の解を検索します：

#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"

int main() {
  size_t size = 100;
  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::easy_solver::EasySolver(f);
  solver.time_limit(5.0);
  solver.target_energy(900);
  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;
}

この例では、以下のオプションが設定されています：

5.0秒の時間制限、
目標エネルギー900、
デフォルトのコールバックを有効化。

したがって、ソルバーは経過時間が5.0秒に達したとき、またはエネルギー900以下の解が見つかったときに終了します。

例えば、このプログラムは以下の出力を生成します:

TTS = 0.000s Energy = 300162 thread = 0 Random
TTS = 0.000s Energy = 273350 thread = 0 Random(neighbor)
TTS = 0.000s Energy = 248706 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 226086 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 205274 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 186142 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 168442 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 152134 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 137162 thread = 0 Greedy(neighbor)
TTS = 0.000s Energy = 123374 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 110650 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 98990 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 88346 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 78678 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 69802 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 61798 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 54626 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 47982 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 42034 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 36598 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 31778 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 27446 thread = 0 Greedy(neighbor)
TTS = 0.001s Energy = 23658 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 20286 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 17250 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 14614 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 12306 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 10350 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 8682 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 7214 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 5994 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 4990 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 4130 thread = 0 Greedy(neighbor)
TTS = 0.002s Energy = 3478 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2882 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2414 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 2122 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1822 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1706 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1574 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1442 thread = 0 Greedy(neighbor)
TTS = 0.003s Energy = 1350 thread = 0 Greedy(neighbor)
TTS = 0.007s Energy = 1306 thread = 7 MoveTo
TTS = 0.008s Energy = 1274 thread = 12 Greedy
TTS = 0.008s Energy = 1262 thread = 12 Greedy(neighbor)
TTS = 0.008s Energy = 1202 thread = 12 Greedy(neighbor)
TTS = 0.016s Energy = 1170 thread = 20 PosMin
TTS = 0.018s Energy = 1166 thread = 23 PosMin
TTS = 0.018s Energy = 994 thread = 23 PosMin(neighbor)
TTS = 0.066s Energy = 986 thread = 7 Greedy
TTS = 0.066s Energy = 982 thread = 7 Greedy(neighbor)
TTS = 0.184s Energy = 954 thread = 10 PosMin
TTS = 0.371s Energy = 942 thread = 12 PosMin
TTS = 0.912s Energy = 930 thread = 4 PosMin
TTS = 0.913s Energy = 902 thread = 4 PosMin(neighbor)
TTS = 2.691s Energy = 898 thread = 15 PosMin
898: ++-++-----+--+--++++++---++-+-+--++-------++-++-+-+-+-+-++-++++-++-+++++-+-+--++++++---+++--+++---++

高度な使用法

複数トップk解の保持

Easy Solverは探索中に見つかった上位k解を複数保存できます。この機能を有効にするには、以下のメンバ関数を呼び出します:

enable_topk_sols(size_t topk_count): topk_count 個までの最良解を保存します。

この関数を有効にすると、 search() には保存された上位k解が含まれます。返されるオブジェクトsolsでは、保存された解にインデックスまたはイテレータのいずれかを使用してアクセスできます:

sols[i]: i-番目の qbpp::Sol 番目のオブジェクトを返します。
size(): 保存されたソリューションの数を返します。
begin(), end(), cbegin(), cend(): 範囲ベースの for ループで各解を順次アクセスできる反復子。

以下のプログラムは、Easy Solver を使用して低自己相関二進数列 (LABS) 問題を解きます。が呼び出されるenable_topk_sols(20)ため、ソルバーは上位 k 個の解を最大 20 個まで保持します。プログラムは範囲指定の for ループを使用して、保存された各解を出力します。

#include "qbpp.hpp"
#include "qbpp_easy_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::easy_solver::EasySolver(f);
  solver.time_limit(5.0);
  solver.enable_topk_sols(20);
  auto sols = solver.search();
  for (const auto& sol : sols) {
    std::cout << sol.energy() << ": ";
    for (auto val : sol(x)) {
      std::cout << (val == 0 ? "-" : "+");
    }
    std::cout << std::endl;
  }
}

このプログラムは以下の出力を表示します:

-----+-+++-+--+++--+
+--+++--+-+++-+-----
-+-+----+----++-++--
--++-++----+----+-+-
-++---++-+---+-+++++
---+++++-+++-++-+-++
+-+-+++++----++--++-
-+++++---+---+-+--+-
+++-----+---+--+-+--
--++--++-+--+-+-----
-+--+-+---+---+++++-
---+++-+-+----+--+--
-++-++-+-+---++-----
--++++--+-+--+---+--
-+-+---++------++-++
++++-++-+--+++-+---+
----+--+-++---+-+++-
-+++++++--++-+-+-++-
-+-+----+++++-++--++
++-----+---+--+-+--+

複数の最良エネルギー解の保持

イージーソルバーは、探索中に見つかった最良（最小）エネルギーを共有する複数の解を保存できます。この機能を有効にするには、次のメンバ関数を呼び出します：

enable_best_energy_sols(size_t best_sol_count): 最大 best_sol_count の最適エネルギー解を保存します。引数を省略した場合、保存される解の数に制限はありません。

使用方法は enable_topk_sols()と同じです。したがって、上記のQUBO++プログラムでこの機能を有効にするには、 enable_topk_sols(20) を以下のように置換します: enable_best_energy_sols(20) を以下のように置換します:

  solver.enable_best_energy_sols();

このオプションを有効にすると、ソルバーは見つかった最良エネルギー値と等しいエネルギーを持つ解のみを保存します。結果として生成されるプログラムは以下の解を産出し、いずれも最良エネルギー値26を持ちます：

+++++-+---+-++---++-
++--+--++++-++++-+-+
-+-+----+----++-++--
+-+-++++-++++--+--++
-++---++-+---+-+++++
--++-++----+----+-+-

最終更新日: 2026.01.04