数学問題: 3つの整数を求める¶
以下の数学問題をHi-QUBOを使って解くことができます.
問題
次の条件を満たす整数 \(x\), \(y\), \(z\) を求めよ:
Hi-QUBOプログラム
Hi-QUBOは多項式を扱えるため,まず制約を書き換えます. 最初の制約の両辺に \(xyz\) を掛けると:
狭義の不等式 \(x<y<z\) は次のように符号化できます:
以下のHi-QUBOプログラムは,これらの制約をHUBO式として定式化し,Exhaustive Solverを使って解きます:
#include <set>
#include <qbpp/qbpp.hpp>
#include <qbpp/exhaustive_solver.hpp>
int main() {
auto x = 1 <= qbpp::var_int("x") <= 10;
auto y = 1 <= qbpp::var_int("y") <= 10;
auto z = 1 <= qbpp::var_int("z") <= 10;
auto c1 = x * y + y * z + z * x - x * y * z == 0;
auto c2 = y - x >= 1;
auto c3 = z - y >= 1;
auto f = c1 + c2 + c3;
f.simplify_as_binary();
auto solver = qbpp::ExhaustiveSolver(f);
auto sols = solver.search({{"best_energy_sols", 0}});
std::set<std::tuple<qbpp::energy_t, qbpp::energy_t, qbpp::energy_t>> seen;
for (const auto& sol : sols) {
const auto key = std::make_tuple(x(sol), y(sol), z(sol));
if (seen.insert(key).second) {
auto [x_val, y_val, z_val] = key;
std::cout << "(x,y,z) = (" << x_val << ", " << y_val << ", " << z_val
<< ")\n";
}
}
}
3つの制約は c1,c2,c3 として符号化され,単一の目的関数 f にまとめられます.
Exhaustive Solverが f の最適解を探索し,得られた \((x,y,z)\) の組を出力します.
f はバイナリ簡約化の過程で補助変数を導入するため,同じ \((x,y,z)\) の割り当てが返される解集合に複数回現れる場合があります.
そのため,出力前に std::set を使って重複を除去しています.
このプログラムは以下の出力を生成します:
(x,y,z) = (2, 3, 6)
これは,探索範囲内でこの問題がちょうど1つの解 \((x,y,z)=(2,3,6)\) を持つことを示しています.
以下の数学問題をPyQBPPを用いて解くことができます.
問題
以下を満たす整数 \(x\),\(y\),\(z\) を求めてください：
PyQBPPプログラム
PyQBPPは多項式を扱えるため,まず制約を書き換えます. 最初の制約の両辺に \(xyz\) を掛けると：
狭義の不等式 \(x<y<z\) は以下のようにエンコードできます：
以下のPyQBPPプログラムは,これらの制約をHUBO式として定式化し,Exhaustive Solverを用いて解きます：
import pyqbpp as qbpp
x = qbpp.var("x", between=(1, 10))
y = qbpp.var("y", between=(1, 10))
z = qbpp.var("z", between=(1, 10))
c1 = (x * y + y * z + z * x - x * y * z == 0)
c2 = (1 <= y - x) & (qbpp.same <= 9)
c3 = (1 <= z - y) & (qbpp.same <= 9)
f = c1 + c2 + c3
f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
result = solver.search(best_energy_sols=0)
seen = set()
for sol in result.sols:
key = (sol(x), sol(y), sol(z))
if key not in seen:
seen.add(key)
xv, yv, zv = key
print(f"(x,y,z) = ({xv}, {yv}, {zv})")
3つの制約は c1,c2,c3 としてエンコードされ,単一の目的関数 f にまとめられます.
Exhaustive Solverが f の最適解を探索し,得られた \((x,y,z)\) のタプルを出力します.
f はバイナリ簡約化の際に補助変数を導入するため,同じ \((x,y,z)\) の割り当てが返される解集合に複数回現れる場合があります.
そのため,出力前に set を使って重複を除去しています.
このプログラムの出力は以下の通りです：
(x,y,z) = (2, 3, 6)
これは,探索範囲内でこの問題がちょうど1つの解 \((x,y,z)=(2,3,6)\) を持つことを示しています.